Cum se face?

Care e ideea la problema Divizori2? Pare o problema destul de "generalizata" si complicata.

De la inceput fixam marimea la blocuri ca sqrt N dupa aia am inceput sa ma joc cu constantele. Acus incerc.

Pentru problema Cu mainele curate, care e complexitatea pe query/update in solutia oficiala? Incercarea mea cu O(sqrtNlogN) per update/query da tle pe cateva teste, anume in acelea in care sunt multe queryuri si putine updateuri.

Urasc sa fiu din nou acela care spune ca lipseste articolul cu solutii, dar chiar ar fine bine sa fie postat in intregime.
Cel putin runda trecuta s-au postat. 

Se adauga sau nu problemele in arhiva?

Inteleg ca e mult lucru sa scrii o solutie bine explicata, dar totusi ar fi bine ca dupa fiecare concurs sa fie cel putin postate niste indicii care sa elucideze rezolvarea problemei.(vreo 4-5 randuri)

Ar fi bine daca s-ar posta solutiile, va rog.   

Ar trebuie o solutie in O(4^M*N) sa mearga? Eu am facut o dinamica cu back pe fiecare linie, si tineam starea liniei anterioare. Ce-i drept, am facut-o intr-un mod mai "destept", facand dinamica "inainte", un fel de parcurgere BFS. A trecut cu 24 de ms pe ultimul test, cu mult mai repede decat solutiile in O(2^N*N*M). Totusi ma intreb care e logica solutiei oficiale optime?

Edit: Dupa o analiza mai atenta, am observat ca complexitatea algoritmului e mai apropiata de O(2^M*fib(M)*N).

Ar trebui marita memoria. Imi iese din limite chiar daca folosesc citirea din C si am 4 variabile.

Am completat articolul. Spor la invatat.

Multumesc mult!  
Deasemeni vreau sa mentionez ca la solutia la problema Suma5, ati scris "unirea a doua noduri a si b intr-un singur nod c", dar in codul prezentat este realizata unirea a nodurilor b si c in nodul a. (o greseala de notatie presupun eu).

Problemele din aceasta runda sunt interesante chiar daca nu am reusit sa particip, dar totusi putin ma irita cand sunt postate solutiile doar partial, iar apoi autorii uita sa completeze.
Nu vreau sa fiu pretentios, dar ar putea cineva macar sa descrie concis solutia pentru problema cu becuri?
Mersi mult.

Oh, in loc la generarea numerelor ternare, eu ma gandeam la generarea combinarilor 
Mersi, am inteles abordarea ta.

Cam inteleg ceea ce ai invedere, dar nu exista oare mai multe moduri de distribuire a elementelor din aceeasi submultime astfel incat suma pentru ambele sa fie >=p? Cum tratez aceasta problema?

Cum s-ar putea de redus complexitatea algoritmului pentru aceasta problema:
http://i.imgur.com/P0eanFd.jpg

E evidenta o solutie O(3^N) si alta O(N^3*P^2), dar cea din urma necesita prea multa memorie. E posibil cumva de redus complexitatea dinamicii? Sau in acest caz e mai bine de facut optimizari pentru backtrack?

O runda cu probleme super frumoase ! Big up comisiei !   Apropo,imi poate da si mie cineva o indicatie la problema Super Mario ? M am chinuit o ora din concurs sa o dovedesc,dar nu prea a fost cu succes  

Sunt doua solutii oficiale. In continuare voi prezenta una dintre acestea.

Vom defini o functie recursiva, Solve(left, right), care returneaza numarul minim de mutari necesare pentru a distruge toate testoasele din intervalul [left, right], folosind numai testoase din acest interval. Raspunsul va fi dat de Solve(1, N), iar cazurile de baza Solve(i, i) sunt triviale (raspunsul e mereu 1).
Intr-o solutie optima, testoasele vor fi distruse in ordine descrescatoare dupa valori. Astfel, vom incerca sa facem prima mutare in Solve(left, right). Fie pos pozitia pe care se afla testoasa de valoare maxima din intervalul [left, right]. Putem sa o lovim spre stanga sau spre dreapta, iar noi vom alege varianta optima. Astfel, Solve(left, right) va returna min(Solve(left, pos - 1), Solve(pos + 1, right)) + 1. Pentru a determina eficient pos, putem folosi o structura de date precum arborii de intervale. Complexitatea este O(N * logN).

Cealalta solutie oficiala se bazeaza pe programare dinamica si are complexitate liniara.

Mi-a venit si mie fix aceeasi idee cu Divide et Impera, dar cum pot sa demonstrez corectitudinea algoritmului? In special afirmatia ca cel mai optim mod este sa distrugem testoasele in ordine descrescatoare dupa P[ i ].
Intuitiv inteleg de ce e asa, dar cum as proceda daca as vrea sa fac o demonstratie matematica consistenta? Presupun ca aici trebuie folosita reducerea la absurd dar nu imi vine in cap cum sa construiesc argumentul.

Aproape intotdeauna cand tie iti da bine local si evaluatorului ii da prost e din cauza faptului ca accesezi memorie aiurea. Calculatorul tau te iarta, din diverse motive, dar evalul nu . Dupa o privire fugitiva, probabil la tine e vorba de vectorul sol.

Oh, am si uitat ca daca declari un vector se aloca intervalul [0,N-1] 
Mersi pentru ajutor.

Am descarcat ultimul test pe care imi arata raspuns gresit, dar in realitate programul da raspunsul corect. Poate fi vreo problema cu evaluatorul? Am incercat sa pun new line la sfarsit dar tot nu merge.

În principiu simulezi căutarea binară pe arbore. Dacă tu vrei să obții suma A, iar fiul stâng al rădăcinii are suma B >= A te duci în fiul stâng și continui căutarea, altfel o continui în fiul din dreapta pentru valoarea A - B.

Înțeleg că răspunsul pe care l-ai primit anterior nu te-a ajutat (deși tehnic ți s-a răspuns la întrebare), dar încearcă să fii mai politicos. Nu are niciun sens să fii sarcastic când ceri ajutor.

Thanks. Cam problematica aceasta operatie.

Da.

Extrem de informativ. Un indiciu macar?
Scap de cautare binara sau gasesc suma 1..i in O(1)?

E posibil de facut operatia de tipul 2 cu arbori de intervale in O(log n)?