Blog infoarena

De ce sa participi la ACM ICPC

Cosmin
Cosmin Negruseri
22 octombrie 2007

Am incercat sa gasesc cateva motive pentru un student la informatica, care nu a avut contact cu olimpiadele in liceu, sa participe la concursurile ACM in timpul facultatii. Ce ar fi folositor pentru el in dorinta de a deveni un programator mai bun? Am ajuns la urmatoarea lista:

  • ca sa mai scrii o linie in CV
  • ca sa iti dai seama ca programezi foarte incet
  • ca sa vezi ce greu e sa lucrezi in echipa in conditii extreme
  • ca sa programezi ceva interesant
  • ca sa intelegi algoritmica si structurile de date la un nivel ce trece de superficialitate
  • ca sa cunosti alti oameni cu pasiune mare pentru programare
  • ca sa ti se para banale intrebarile de coding de la interviurile microsoft sau google
  • ca sa inveti chestii mai importante decat ultima tehnologie la moda, cum ar fi identificarea rapida a bugurilor, claritatea codului, proiectarea programului inainte de implementare sau metode de optimizare a timpului si memoriei
  • ca sa rezolvi o problema complet a carei solutie merge pe toate cazurile
  • ca sa inveti ca nu orice problema se rezolva cu "metoda backtracking"
  • ca sa poti scrie un post pe blog

Ce motive aveti voi pentru a participa sau pentru a nu participa la acest concurs?

 Comentarii (15)

Categorii: concursuri

Alta problema misto - solutie

Cosmin
Cosmin Negruseri
22 octombrie 2007

Problema cu lanternele a fost rezolvata de Radu Cebanu, Dumitru Daniliuc, Stefan Istrate , Catalin Francu si Stefan Ciobaca.

Va prezint in continuare solutiile. Este interesant de urmarit cum sunt gandite solutiile, care desi sunt echivalente sunt prezentate putin diferit.

Stefan Ciobaca generalizeaza problema:
Eu as fi propus generalizarea: ai 2^n triedre drepte in n dimensiuni.

Rezolvarea prin divide et impera: iei cele 2^n puncte si le separi printr-un hiperplan astfel incat jumate sa fie de-o parte, jumate de cealalta parte s.a.m.d., avand in vedere ca toate hiperplanele sa fie perpendiculare intre ele. Evident, chestia asta se poate. Apoi, fiecare triedru il orientezi spre semisemisemi...semi spatiul total opus si cu marginile paralele cu axele de coordonate q.e.d.
Imi place cum se vede defectul profesional de programator citind demonstratia.

Solutia lui Radu:

Rezolvam prin inductie dupa nr de dimensiuni.

In primul rand: fixezi o directie pt primul plan, il muti paralelel cu el insusi astfel incat sa separe punctele in 2 parti egale, 4 de o parte, 4 de alta (daca stau mai multe pe planul ala exact,nu conteaza, alegi cateva si le declari de o parte, sa fie 4 si restul de cealalta).
Apoi sa zicem ca le luam pe alea de deasupra:
proiectiile lor pe planul respectiv sunt 4 puncte care conform inductiei (pt doua dimensiuni) acopera planul. Cu diedrele din plan faci triedre cu a 3-a dreapta in jos ca sa acopere semispatiul inferior. La fel pt alea de sub plan, pui dreapta a 3-a din triedru in sus ca sa acopere semispatiul superior.
Radu a lasat demonstratia putin incompleta avand incredere ca ma prind singur de cazul 2d si 1d.

Solutia lui Catalin:
Ideea mea e sa gasesc o solutie in care triedrele au laturile orientate paralel cu axele, pentru simplitate.

- Rotim sistemul astfel incat sa nu existe doua lanterne cu coordonate X, Y sau Z egale (pentru a scapa de cazuri particulare).

- Parcurgem lanternele in ordine crescatoare a coordonatei x. Pe primele 4 le marcam cu X+, pe ultimele 4 cu X-.

- Parcurgem cele patru lanterne X+ in ordine crescatoare a coordonatei y. Pe primele doua le marcam cu Y+, pe celelalte doua cu Y-. La fel si
pentru cele patru lanterne X-.

- Parcurgem cele doua lanterne X+Y+ in ordine crescatoare a coordonatei z. Pe prima o marcam cu Z+, pe a doua cu Z-. La fel si pentru celelalte 6 lanterne marcate cu X+Y-, X-Y+, X-Y-.

Avem opt lanterne marcate cu X+Y+Z+, X+Y+Z-, pana la X-Y-Z-. Acum le pozitionam paralel cu axele Ox, Oy, Oz si in sensurile indicate de semne. De exemplu, lanterna X+Y-Z-

va lumina catre sensul pozitiv al axei Ox si catre sensurile negative ale axelor Oy si Oz; cu alte cuvinte, ea va lumina punctul de coordonate (+inf, -inf, -inf).

Dandu-se un punct P(x,y,z), trebuie demonstrat ca exista o lanterna care il lumineaza. Analizam coordonata x. Datorita constructiei, x va fi fie mai mare decat toate coordonatele x ale lanternelor marcate cu X+, fie mai mic decat toate coordonatele x ale lanternelor marcate cu X- (fie ambele, daca x este situat intre cele doua grupuri de 4 lanterne). Alegem acel set de 4 lanterne si reluam rationamentul pe axele Oy si Oz. in final, obtinem minim o lanterna care lumineaza punctul P.

Si la Catalin se vede programatorul din spatele solutiei. Se observa cum structura rezolvarii este bazata pe vectorii de cate 3 elemente in baza 2.

Stefan Istrate are o solutie foarte misto, cu desene dragute, pe care o gasiti pe forum . Merita sa o cititi!

Solutia lui Dumitru nu o am scrisa.

La solutia lui Stefan Ciobaca si cea a lui Catalin Francu nu e demonstrata ipoteza ca putem gasi un sistem de coordonate in care toate punctele au coordonatele x1, x2, .. respectiv diferite . Va incurajez sa va incercati puterile pe aceasta subproblema in sectiunea de comentarii

O problema similara a fost propusa la un ACM in regiunea din Nord Estul Europei: Se cere iluminarea planului cu n lanterne (n <= 30) de coordonate date, ce pot fi rotite, al caror fascicul emite lumina sub un unghi de marime 2pi/n. Pentru fiecare lanterna trebuie returnata orientarea ei. La aceasta problema, pe langa solutia ei, e interesant si algoritmul folosit pentru evaluarea corectitudinii unui rezultat.

Pentru mai multe probleme interesante cu lanterne puteti citi urmatoarele lucrari:

Bose, J., L. Guibas, A. Lubiw, M. Overmars, D. Souvaine and J. Urrutia, "The floodlight illumination problem"
Czyzowicz, J., E. Rivera-Campo and J. Urrutia, "Optimal floodlight illumination of stages"

 Comentarii (0)

Categorii: potw probleme

Se apropie ACMul

Cosmin
Cosmin Negruseri
21 octombrie 2007

Pe 25-28 Octombrie se va desfasura la Universitatea Politehnica din Bucuresti faza pe sud estul Europei a concursului ICPC organizat de ACM. Acest concurs este unul in care echipe de trei studenti, fiecare echipa lucrand pe un singur calculator, se infrunta pe parcursul a cinci ore sa rezolve cat mai repede intre sapte si noua probleme.

Solutia unei probleme se ruleaza pe o suita de teste si este considerata corecta doar daca obtine rezultate corecte pentru toate testele. Daca au rezolvat corect o problema, echipa primeste um balon cu culoarea corespunzatoare problemei, daca nu se primesc niste mesaje ca 'Raspuns Gresit', 'Timp de executie expriat', 'Limita de memorie depasita' etc Astfel este usor de a vedea clasamentul sau cea mai simpla problema pe care echipa ta nu a rezolvat-o inca, daca te uiti prin sala la baloanele celorlaltor echipe. Punctajul este alcatuit din suma timpilor trecuti de la inceputul concursului pana la rezolvarea corecta fiecarei probleme, la care se adauga cate 20 de minute penalizare pentru incercarile esuate de a trece testele. Aceasta modalitate de acordare a punctajelor face ca strategia cea mai buna sa fie rezolvarea problemelor simple la inceput. De obicei problemele sunt calibrate cam o treime simple, o treime medii si o treime mai grele, si se urmareste ca fiecare problema sa fie rezolvata de cel putin o echipa, dar sa nu fie o echipa care sa rezolve toate problemele.

Vor mai urma saptamana aceasta cateva posturi legate de ACM ICPC in curand.

 Comentarii (0)

Categorii: concursuri

Alta problema misto

Cosmin
Cosmin Negruseri
20 octombrie 2007

Cum v-a placut prima problema, voi continua sa postez din cand in cand probleme interesante. Din cate imi amintesc, cred ca urmatoarea este de la olimpiadele rusesti ca si prima de altfel. Rusii au pe la concursuri tot felul de probleme cretze care par simple dupa ce le vezi solutia.

Avem opt lanterne ce emit lumina in forma unor triedre drepte. Sa se demonstreze ca oricare ar fi pozitia lanternelor in spatiu (consideram lanternele ca niste puncte), exista o orientare a triedrelor de lumina astfel ca oricare punct din spatiu sa fie luminat de cel putin o lanterna.

Discutati problema la sectiunea de comentarii. In doua zile voi publica solutia mea, daca nu apare aceeasi solutie pe forum.

 Comentarii (9)

Categorii: potw probleme

Interviu cu Mihai Patrascu

wickedman
Cristian Strat
19 octombrie 2007

Cosmin a publicat un interviu cu Mihai Patrascu pe blog-ul infoarena.

Mihai Patrascu are printre cele mai bune rezultate la olimpiadele internationale la informatica dintre romani. A luat premiul I la Olimpiada nationala de informatica din clasa a 4a (concurand la clasa a 5a) pana intr-a 12a. La olimpiada internationala la de informatica a luat doua medalii de aur si una de argint (in 2001 a fost locul doi la internationala).

In 2005 a luat premiul Outstanding Male Undergraduate Award pe Statele Unite si Canada.

Citeste interviul acum:

 Comentarii ()

Categorii: stiri

Interviu cu Mihai Patrascu - partea a doua

Cosmin
Cosmin Negruseri
19 octombrie 2007

Acum zece zile am publicat prima parte a interviului cu Mihai Patrascu . A venit timpul sa publicam si partea a doua. In ea Mihai ne vorbeste de olimpiade, de modul lui de lucru si de interese in afara programarii:

Cum ai recomanda cuiva sa se antreneze pentru concursuri sau sa se pregateasca pentru cercetare?

Cred ca cel mai eficient e sa ajungi sa programezi suficient de bine, si apoi sa te concentrezi pe gandirea teoretica la probleme. De prin clasa a 10a nu programam decat cateva zile inainte de olimpiada sa-mi intru in mana. Restul doar ma gandeam dar nu implementam (economiseste mult timp la pregatire).

Din cauza asta nu am fost niciodata un programator prea rapid... In plus capacitatea mea de debug este aproape nula, asa ca preferam sa scriu foarte incet si fara buguri. N-as avea niciodata sanse la un concurs ca ACM sau top coder :)

Care e secretul reusitei la concursuri sau in cercetare? caracteristicile native, educatia profunda, munca depusa?

Clar ca fara inteligenta nu se poate :), dar toti oamenii care ajung sa faca ceva la olimpiade sunt foarte inteligenti. Cred ca ce face diferenta la un nivel inalt e atitudinea personala. In mod constant erau oameni in lot pe care ii consideram mai destepti decat mine, dar eu eram mai hotarat sa castig, lucram mai mult cand trebuia sa lucrez, ma relaxam mai mult cand trebuia sa ma relaxez etc. Nici ceilalti concurenti, nici comisia nu sunt cu un cap mai sus ca tine -- daca tu ai incredere ca esti tare, atunci chiar esti mai tare.

Cum abordezi o problema, ai o reteta standard (generalizare, simplificare, trecerea prin o lista de tehnici) sau ai cate un "aha" moment?

Nu, simt ca intotdeauna imi vin idei dubioase si fara explicatie. Problemele la care ma prindeam cel mai greu erau chestii clasice ca flux, cuplaj, etc -- pana sa ma gandesc ca de fapt poate se foloseste ceva standard imi lua ceva timp.

Cum se compune o problema de olimpiada?

Foarte greu... Am un dispret pentru problemele bazate pe materie avansata. Ne trebuie probleme noi, cu o rezolvare elementara, nu bazate pe ceva care inveti la facultate. Problemele trebuie sa fie cu adevarat concurs de perspicacitate, si ar trebui sa fie la fel de grele pentru un concurent din liceu si pentru un prof care studiaza algoritmi de 50 de ani... Din pacate, e greu de gasit astfel de probleme, si nu am propus prea multe probleme.

De ce nu ai continuat cu concursurile de programare in timpul facultatii?

Concursurile mi se par prin definitie ceva pentru liceu. La nivelul ala inca inveti, si e bine ca ceva sa te motiveze sa inveti, in timp ce iti ascuti inteligenta in domeniu. La facultate stii mai multe, si pot sa faci alte chestii mai important pentru tine si pentru omenire... Poti sa te angajezi, sa lucrezi in cercetare, etc. Poti sa-ti faci un renume la inceput cu IOI, dar pana la urma succesul in viata depinde de alte chestii.

Asta gandeam inca din liceu, asa ca mi-a fost usor sa renunt. In treacat fie spus, am fost de 2 ori la ACM din inertie, o data cu Craiova, si o data la MIT. Amandoua esecuri lamentabile :) Cu echipa din Craiova problema era ca nimeni nu programa suficient de repede (in frunte cu mine). Cu MIT problema a fost interactiunea mea cu autoritatea :) -- am iesit primul la concursul individual, dar echipa s-a format din locurile 2,3,4 la decizia profilor coordonatori.
Razbunarea mea a fost ca anul ala MIT-ul nu s-a calificat la regionala ;)

La ce alte proiecte software ai lucrat?

Singurul proiect mai mare care l-am facut a fost evaluatorul pentru olimpiade (nu stiu daca se mai foloseste, dar s-a folosit la BOI la Iasi si la cateva nationale). Restul totul au fost programe mici pt olimpiade. Si cand am lucrat pentru companii, am lucrat pe directii de cercetare unde nu trebuie decat programe mici prototip care sa testeze o idee.

Ai vreo metoda dupa care iti imparti timpul sau lucrezi cand si cum ai chef?

Eu profit de libertatea din cercetare pana la punctul unde enervez pe toata lumea :) Daca n-am chef sa fac nimic saptamana asta, nu fac nimic saptamana asta. Ma duc la munte, citesc ceva, nu conteaza. Cand lumea munceste la o lucrare (care implica finalizat tot felul de detalii si scrisul propriu-zis), eu de obicei fac misto de ei :) De obicei nu reusesc nici macar sa scriu pe hartie niste calcule.

Dar daca am o idee de rezolvare in cap si vreau sa scriu o lucrare pentru o conferinta, am o reteta standard. Cu 2-3 zile inainte de deadline, imi iau periuta de dinti, 10-15 sticle de Pepsi Diet, cateva kg de prajituri, si ma duc in birou. Si acolo petrec cele 2-3 zile lucrand (am determinat ca rata optima de somn in birou e cam 2h pe zi). Adrenalina e foarte interesanta.

Citesti bloguri/frecventezi forumuri? Spune-ne cateva exemple.

Chiar am si eu un blog la http://infoweekly.blogspot.com/, in care discut probleme de cercetare in algoritmi. Cred ca unele chestii ar putea fi interesante pentru studentii la olimpiade in ani mai mari, care vor sa se decida ce vor sa faca in viitor. Pot sa vada cateva probleme si sa vada daca ii tenteaza teoria.

De citit, citesc cateva bloguri din teorie, dar nu cu prea multa pasiune (doar ca e util sa te tii la curent). La forumuri nu particip.

Ce interese, hobbyuri, pasiuni care nu sunt legate de programare ai?

A, multe... Desi intotdeauna stau rau cu timpul, asa ca fac mai putine decat as vrea. Imi place foarte mult sa calatoresc, si acum pot sa fac asta cu toate conferintele la care ma duc (am ajuns in 28 de tari pana acum). Imi place sa vorbesc cu lumea, sa descopar culturi noi, si imi place sa citesc mult despre istorie.

Periodic descopar pasiuni pt un nou sport. In liceu mergeam pe munte si jucam badmington, apoi am facut alergari (era o vreme cand alergam 16km pe seara), am jucat rugby (in Divizia 3 din State), mai recent climbing si sailing.

Pe ce te concentrezi acum?

Anul asta voi termina doctoratul... Trebuie sa scriu o teza si sa aplic pentru joburi (in pricipal, o sa aplic pentru joburi de prof la universitati). Asta ia destul de mult timp. In rest, mai lucrez la cercetare, si mai calatoresc.

Cum tii pasul cu cercetarea curenta? Sunt conferintele importante si discutiile cu ceilalti cercetatori (comunitatea din care faci parte), sau e deajuns sa citesti research paperurile ce apar?

Sunt cateva conferinte importante la care ma duc intotdeauna. Problema e ca nu pot sa stau intr-o sala si sa ascult o prezentare (lipsa de concentrare). Asa ca in timpul conferintei ma intalnesc cu prieteni vechi care de asemenea nu vor sa fie prezenti, si mergem la bere sa mai discutam probleme. Ca sa aflu ce se intampla citesc lucrari pe Net.

Cum te vezi in 5-10 ani?

Sper ca cu un job :) Planul este sa lucrez in continuare in domeniu si sa mai rezolv cateva probleme importante. Apoi as vrea sa incerc si sa fondez o companie cu o idee trasnet. Avem multe rezultate valoroase in teorie, care nu se aplica pentru ca lumea nu se gandeste suficient la impactul mai larg si nu gaseste aplicatiile bune. Daca imi vine vreo idee buna la capitolul asta nu voi ezita sa incerc o companie, in paralel cu jobul de prof.

Vrei sa le transmiti ceva celor ce acum incep cu viata competitionala?

E sansa voastra sa aratati lumii ce tari sunteti, si sa deveniti si mai tari pe parcurs. E un drum bun in viata.

Ii multumim lui Mihai pentru un interviu foarte interesant.

 Comentarii (4)

Categorii: concursuri interviu

Olimpiada Internationala de Informatica 2007 - jurnal de bord

Cosmin
Cosmin Negruseri
17 octombrie 2007

L-am rugat pe Andrei Grigorean sa ne scrie un jurnal despre experienta lui la Olimpiada Interantionala de Informatica. Initial ma gandeam ca ar fi misto sa ne zica aproape live ce s-a intamplat in fiecare zi :), dar asta ar fi adaugat la stresul competitiei. Astfel am fost bucuros cand s-a oferit sa faca un rezumat dupa concurs, apoi am fost si mai bucuros cand l-a terminat. Multumim Andrei! Acum puteti sa il cititi si voi:

IOI 2007

In perioada 15-22 august 2007 am avut ocazia de a participa la cea de a XIX-a editie a Olimpiadei Internationale de Informatica , desfasurata in capitala Croatiei, Zagreb. Ceilalti trei membri ai lotului Romaniei au fost: Cosmin Gheorghe, Bogdan Tataroiu si Adrian Airinei. Am fost insotiti de prof. Emanuela Cerchez (Team Leader) si de Mugurel Ionut Andreica (Deputy Leader).

Acomodarea

In data de 15 august, la ora 4:30 dimineata, ne-am intalnit cu totii la aeroportul international "Henri Coanda" din Otopeni. Am zburat pana in Budapesta, unde am schimbat avionul pentru a ajunge in Zagreb. Am aterizat in Croatia pe la amiaza si am fost una din primele delegatii sosite. Un autocar ne astepta in fata aeroportului si am fost dusi in complexul unde am fost cazati si unde am luat masa timp de o saptamana. Am stat cate doi in camera, eu impreuna cu Cosmin, respectiv Bogdan cu Adrian, si imparteam aceeasi baie. Conditiile nu erau extraordinare, insa nici nu ne puteam plange - erau totusi camine studentesti. In privinta mancarii insa, am doar cuvinte de lauda. Puteam servi oricat doream din mese diverse, foarte gustoase. Am mancat foarte mult la IOI, mai ales eu si Cosmin :P.

Competitia

Inainte cu o zi de a incepe competitia a avut loc sesiunea de pregatire. Scopul acestui eveniment este familiarizarea cu sistemul folosit in concursul real si oarecum o usoara "incalzire" a concurentilor. Am avut posibilitatea de a implementa si submita timp de doua ore cele trei probleme afisate pe site-ul olimpiadei cu trei saptamani inainte. Totul a decurs bine, cu exceptia catorva probleme cu Rhide-ul.

Apoi a venit prima zi de concurs. Eu personal ma asteptam sa fie probleme interesante si asa a si fost. Am primit doua batch-uri si o problema interactiva. Dupa o scurta trecere in revista, am decis sa aboredez mai intai problemele sails si flood. Dupa doua ore si jumatate nu gasisesm nicio rezolvare, moment in care m-am hotarat sa incerc aliens. Dupa aproximativ o jumatate de ora gasisesm rezolvarea si am inceput sa implementez. Pana la sfarsitul concursului nu am mai reusit sa gasesc solutiile optime la sails sau la floodm asa ca am trimis rezolvari brute-force (la flood am terminat de implementat cu 5 minute inainte de final). Rezultatele din prima zi au fost conform asteptarilor: Cosmin - 235 pct (a facut sails de 100), Bogdan - 172 pct, eu - 145 pct si Adrian - 120 pct. Dupa estimarile mele aveam un aur, un argint si doua medalii de bronz cu aceste punctaje. Nu am reusit niciunul sa rezolvam problema flood, desi dupa ce am auzit solutia mi se parea mai simpla decat estimasem initial. Si punctajele obtinute de ceilalti concurenti aratau ca sails fusese cea mai grea din prima zi, nu flood.

A doua zi de concurs a fost putin diferita de prima. Am primit trei batch-uri, de dificultate variata. Miners era clar problema simpla, imediat cum am citit-o am si implementat-o. S-a dovedit ca peste 100 de concurenti au luat maxim la ea. Pairs era de fapt compusa din trei subprobleme independente - am gasit rezolvarea in timp util la toate, insa trebuia sa implementez arbori de intervale 2D, asa ca am decis sa o las la urma si sa incerc sa rezolv training. Aceasta a fost cea mai grea problema din concurs, cu doar 3 punctaje maxime :). Nu am reusit sa gasesc solutia optima, asa ca dupa ce am implementat o sursa care lua 30 de puncte, m-am intors la pairs. Faptul ca nu am implementat pana la urma ultima subproblema, si ca am uitat sa pun un -1, au facut ca punctajul meu in a doua zi sa fie de 172 de puncte. Adrian si Bogdan au luat 200, iar Cosmin 150.

Excursii

Dupa fiecare zi de concurs, organizatorii ne-au dus in doua excursii care mie mi-au placut foarte mult. Prima din ele a fost la un lac unde se pregateau sportivii croati pentru diferite sporturi pe apa (gen canoe). Acolo ne-am petrecut jumate de zi. Eu si Adrian, impreuna cu 3 bulgari, am jucat fotbal cu rusii, care aveau o mare vedeta in echipa - Petr Mitrichev. Daca la informatica nu am fost mai buni, macar la fotbal i-am batut... de doua ori :D. Se mai putea juca badminton, tenis de masa - a fost un fel de picnic cu vreo 400 de persoane.
A doua excursie a durat o zi intreaga. Am vizitat Lacurile Plitvice si casa memoriala Nikola Tesla. Puteti vedea cateva poze aici. Peisajele erau superbe, aratau mai bine in realitate decat in poze. Am fost la cea mai mare cascada din Croatia (din pacate nu apare in album), iar dupa masa am ajuns la casa memoriala a faimosului om de stiinta - pe mine nu m-a impresionat prea tare, nu aveau o modalitate atractiva de a prezenta informatia.

Sfarsit de poveste

Cu punctajele noastre am obtinut pana la urma cu totii medalii de argint, sa speram ca in anii urmatori Cosmin si Bogdan, impreuna cu ceilalti participanti la IOI, vor face mai bine decat am facut noi anul acesta. Ne-am intors acasa pe data de 22 august pe aeroportul "Henri Coanda", unde ne asteptau parinti, profesori, reprezentanti Intel si presa. Si-am incalecat pe-o sa, si v-am spus povestea asa.

Felicitam echipa Romaniei inca o data pentru rezultatul obtinut si mentionam ca dupa olimpiada, cei doi seniori ai echipei (Andrei Grigorean si Adrian Airinei ) s-au alaturat echipei infoarena .

 Comentarii (2)

Categorii: concursuri

O problema misto - solutie

Cosmin
Cosmin Negruseri
16 octombrie 2007

Din dorinta de a face enuntul problemei cat mai simplu am lasat cateva cerinte ale problemei nespecificate. De aici au aparut si cele trei updateuri la text.

Cei care au rezolvat problema sunt: Teodorescu Andrei-Marius , Adrian Sandor si Radu Cebanu.

V-am promis si o solutie:
Impartim planul in patrate de latura unu. Suprapunem toate patratele unul peste celalalt, si cum aria totala a petelor este strict mai mica ca unu rezulta ca va exista un punct care nu este acoperit de vreo pata. Marcam acest punct in toate patratele. Cand le punem inapoi in plan, punctul marcat se transforma in o grila de puncte. Acum putem selecta ca origine oricare dintre aceste puncte si ca axe dreptele paralele cu abscisa respectiv ordonata din sistemul initial, care trec prin punctul ales ca origine.

Sper ca v-a placut, chiar daca e o problema de mate.

 Comentarii (2)

Categorii: probleme

preONI 2008 - in cautare de sigla

Cosmin
Cosmin Negruseri
15 octombrie 2007

Scoala a inceput de ceva vreme si se apropie perioada concursurilor online. Ca in fiecare an, din 2004 incoace, echipa infoarena va pregateste o noua editie a concursului preONI. Primul pas ar fi gasirea unui logo pentru concurs, si aici avem nevoie de ajutorul vostru.

Majoritatea logourilor folosite pe site au fost facute cu ajutorul userilor. Sa vedem cum au aratat siglele de-a lungul timpului.

La inceput infoarena.devnet.ro avea acest logo:

Cand s-a facut trecerea la a doua versiune a siteului pe domeniul infoarena.ro, Dan Burzo ne-a facut o sigla simpatica, in care mascota siteului are ochelari, ca orice geek respectabil, dar poarta un coif pentu ca e gata de lupta in arena.

Logoul pentru preONI 2006 a fost realizat tot de Dan Burzo.

Iar logourile pentru fiecare runda de Cristina Stancu Mara

Urmatoarele doua logouri au fost facute pentru preONI 2007. Al doilea nu a fost folosit.

autor Radu Lupaescu

autor Alexandru Marinescu

Le multumim inca o data celor ce ne-au ajutat si vrem sa va cerem ajutorul in realizarea unui logo pentru preONI 2008. O sugestie ar fi pentru culorile alese sa se integreze bine cu cele ale siteului.

 Comentarii (13)

O problema misto

Cosmin
Cosmin Negruseri
12 octombrie 2007

Dumitru Daniliuc mi-a zis o problema simpatica de pe vremea cand se antrena in liceu pentru olimpiadele de matematica, pe care acum vreau sa v-o zic si voua.

Problema suna asa: Se da o multime S, de puncte in plan. Aria ocupata de puncte e strict mai mica decat unu. Se cere sa se gaseasca un sistem de coordonate astfel ca punctele de coordonate intregi din acest sistem de coordonate sa nu se suprapuna peste nici un punct din multimea S.

Va rog, daca aveti solutii, sa nu le publicati pe forum ci sa mi le trimiteti ca mesaj privat. In doua zile voi publica o solutie si numele celor ce au rezolvat corect problema.

Update: Multimea S poate contine o infinitate de puncte. De exemplu S e formata din cateva pete si o dreapta. Aria dreptei e 0 si suma ariilor petelor e mai mica ca 1.

Update2: Pentru a nu complica problema si definitia a ce inseamna arie, impunem restrictia ca multimea S este formata din un numar finit de pete, fiecare avand o arie. Deci S nu va contine drepte, spirale sau mai stiu eu ce.

Update3: Sistemul de coordonate trebuie sa fie ortonormat si sa pastreze dimensiunile initiale.

 Comentarii (1)

Categorii: probleme
Vezi pagina: 12345... 282930313233 34353637383940 (393 rezultate)