Blog infoarena

Problema saptamanii (solutie)

Cosmin
Cosmin Negruseri
16 februarie 2008

Am luat o pauza destul de lunga cu problema saptamanii. La ultima problema am primit doar doua solutii si am uitat de la cine (amintiti-mi si va trec ca rezolvitori). Gasiti textul aici .

Solutia problemei e destul de misto: Ne gandim la spatiul starilor problemei ca un patratul unitate din planul cartezian cu originea in (0, 0) si cu punctul diagonal opus in (1, 1). Abscisa unui punct din patratul acesta reprezinta pozitia normalizata pe intervalul [0, 1] a unui mobil sau un robot pe unul dintre cele doua drumuri de la A la B, iar ordonata punctului va reprezenta pozitia normalizata a celuilalt mobil respectiv robot pe al doilea drum de la A la B. Acum pentru ca ambele mobile pleaca din A si ajung in B, punctele asociate pozitiilor lor ne vor da o curba pornind din punctul (0, 0) si ajungand in punctul (1, 1). Iar punctele ce reprezinta miscarea celor doi roboti, care unul pleaca din A si ajunge in B si celalalt pleaca din B si ajunge in A, ne descriu o curba ce pleaca din punctul (0, 1) in (1, 0). Cele doua curbe trebuie sa se intersecteze si de aici rezulta ca orice doua drumuri am forma intre orasele A si B si orice itinerariu ar avea robotii, daca doua mobile pot ajunge de la A la B fiind legate cu o sfoara de lungime 10 m, atunci robotii nu pot ajunge unul din A in B si celalat din B in A fara sa se atinga.

 Comentarii (0)

Categorii: potw probleme

Problema saptamanii

Cosmin
Cosmin Negruseri
11 noiembrie 2007

A venit din nou timpul pentru problema saptamanii. Va propun o problema interesanta ce mi-a zis-o colegul meu de clasa Radu Cebanu acum vreo trei ani.

Se dau doua puncte A si B. Exista doua drumuri(curbe infinit de subtiri) intre ele si aceste drumuri au proprietatea ca doua mobile punctiforme legate cu o sfoara de lungime 10 m pleaca din A si ajung in B fara a rupe sfoara. Nu exista vreo restrictie asupra miscarii mobilelor, decat ca ele se deplaseaza fiecare pe unul din drumuri. De exemplu viteza lor poate fi diferita, ele pot sa se miste chiar in sensul opus de la B la A, sau un mobil poate sta pe loc in timp ce al doilea se misca. Avem doi roboti in forma de discuri de raza 5 metri, unul cu centrul in A si celalalt cu centrul in B. Intrebarea este daca acesti roboti pot folosi cele doua drumuri pentru a ajunge din A in B si respectiv din B in A, fara a se ciocni. Robotii se misca fiecare cu centrul discului pe unul din drumuri.

Va reamintesc ca puteti folosi formul pentru clarificari ale enuntului, si mesajele private pentru solutii complete. Have fun!

 Comentarii (0)

Categorii: potw probleme

Intrebare scurta

Cosmin
Cosmin Negruseri
04 noiembrie 2007

Cat e complexitatea ca timp a Ciurului lui Erastotene? Motivati raspunsul.

Update: E interesant ca nu stim complexitatea unui algoritm pe care il invatam in clasa a 5-a. Ne gandim mai intai ca algoritmul trebuie sa fie mai rapid decat O(n^2), pentru ca facem n pasi si fiecare pas e mai eficient decat o parcurgere a celor n numere. Daca ne uitam mai atent, numerele sunt parcurse pe sarite si numarul de operatii e n/2 + n/3 + n/4 + ... + n/n = n(1/2 + 1/3 + ... + 1/n). Sirul 1 + 1/2 + ... + 1/n - log\ n este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat O(n\ log\ n). Nu am folosit faptul ca in algoritm noi vom marca doar pornind de la valori prime, sarind peste multe valori, astfel numarul de operatii al algoritmului e n (1/2 + 1/3 + 1/5 + ... + 1/pk) unde pk e cel mai mare numar prim mai mic decat n. Sirul 1 + 1/2 + 1/3 + 1/5 + ... + 1/pk - ln\ ln\ n e convergent dupa cum putem citi aici . Astfel complexitatea algoritmului Ciurul lui Erstotene este O(n\ log\ log\ n).

Am o alta intrebare pentru voi: Stiti cat e complexitatea algoritmului lui Euclid?

 Comentarii (7)

Categorii: potw probleme

Problema saptamanii (Solutie)

Cosmin
Cosmin Negruseri
04 noiembrie 2007

Problema a fost rezolvata de Mihai Patrascu, Radu Cebanu, Adrian Vladu, Marius Buzea, Marius Andrei, Adrian Carcu, Giurgea Mihnea, Liviu Ciortea, Adrian Sandor, Razvan Alecsandrescu, Igor Naverniouk si Csaba Patcas.

La prima vedere pare nerezolvabila, dar de fapt are o solutie destul de simpla. Ea se bazeaza pe faptul ca multimea ZxZ e numarabila. Putem verifica in fiecare secunda T cate o coordonata X0 + Y * T, parcurgand perechile (X0, Y) in spirala. Vom ajunge la un T1 pentru care teroristul este la locatia X0 + Y * T1. Inca nu am rezolvat problema, pentru ca pot exista mai multe perechi de numere pentru care teroristul sa fie la locatia X0 + Y * T1 in momentul T1. Prin faptul ca am gasit pozitia teroristului la un moment fixat T1, am redus problema la una noua determinata de parametrii X0', Y' in care in care nu il stim pe Y dar X0' = X0 + Y * T1. Aceasta subproblema se poate rezolva usor.

Alta problema cu teroristi ce mie imi place foarte mult este Lesbulan , ca dovada am si propus-o la concursul Bursele Agora.

Probleme cu tema similara sunt si Soarecele si pisica (medie ca dificultate, de pe Lista lu' Francu), Tom & Jerry (grea, nu a facut-o nimeni din cate stiu eu cand a propus-o Mugurel la lot) si tunnels (foarte grea, nu a facut-o nici o echipa in finala ACM ICPC 2006), smuggler (de pe rec.puzzles.org cu solutie). Daca sunteti curiosi de rezolvari, putem sa le discutam pe forum.

 Comentarii (3)

Categorii: potw probleme

Problema saptamanii

Cosmin
Cosmin Negruseri
30 octombrie 2007

Dupa feedbackul pozitiv de la primele doua probleme, m-am decis sa postez cate o problema draguta cam la doua saptamani.

Problema curenta: Un terorist se afla pe o axa infinita la pozitia X0 in momentul T = 0. La fiecare secunda teroristul se muta la dreapta cu Y unitati (Y poate fi si negativ). X0 si Y sunt numere intregi fixate pe care noi nu le stim. La fiecare secunda putem verifica exact o coordonata de pe axa si vom afla daca teroristul e sau nu acolo. Se cere determinarea unei modalitati de a il descoperi pe terorist si de a ii putea prezice pozitiile urmatoare.

Pentru intrebari referitoare la enunt folositi sectiunea de comentarii. Solutiile complete trimiteti-mi-le ca mesaj privat.

 Comentarii (7)

Categorii: potw probleme

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

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

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

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: 1  (9 rezultate)