infoarena

Aici puteţi discuta despre problema Boom (http://infoarena.ro/problema/boom).

Asi avea si eu o problema la probl. Am facut o rezolvare care cred ca e buna, dar nu obtin doar 90  :shock: pe ea. Testul 2 nu merge nicicum. Imi scapa ceva minor si ma chinui de mult sa-mi dau seama. Dc poate cineva sa-mi dea ceva indicii referitor la ce ar avea testul 2 in particular. mersi

Testul 2:

imi da si mie cineva o idee la problema asta ?

Vezi aici: http://info.devnet.ro/articole.php?page=art&art=25&artpage=1 . Ar fi bine sa va mai uitati pe articolele de pe site, poate gasiti ceva interesant.

da...ar fi ceva. multumesc mult.

Voi ati bagat jumatate din teste de dimensiune maxima?
Initial luam 50 din cauza TLE, si dupa ce am omorat dikjstra cand am in varful heap-ului nodul terminal, am luat 100.
Bagati teste mai echilibrate

NU.



 =D>

Sorry atunci. Doar ca pe un test maxim care sa fie facut cat mai defavorabil, cred ca programul ar sta cateva secunde bune. Torusi, e O(2^N*N*M) pentru n=20 si M=50, cateva miliarde de operatii.
Sau poate se gaseste foarte repede solutia pe teste random.
E ceva demonstrat in sensul asta?
Oricum, interesanta problema.

Citatul este din problema. Graful nu va arata foarte urat din acest motiv (am intuit eu).

Trebuie sa fii de acord ca este supraestimata complexitatea. Solutia mea, spre exemplu, utilizeaza o prepocesare care reduce numarul de noduri din graful respectiv prin considerarea configuratiilor in care se poate ajunge. Parca numarul maxim de noduri era ~ 30,000

Si, in final, au existat solutii care au complexitatea maxima (chiar si pe testele mele pentru ca nu tin cont de faptul ca ele sunt relativ particulare) si care au rulat foarte rapid. Aceastea au folosit arbori de intervale in locul heapurilor in algoritmul Dijkstra.

Tot iau TLE pe ultimele doua teste. Am cateva optimizari dar nu cred ca sunt suficiente: fac BFS din nodul 1<<n - 1 si introduc in heap doar nodurile accesibile. Totul este intr-o singura functie. Si pentru aplicarea unei sarje folosesc operatii pe biti. Mai stiti optimizari care m-ar putea ajuta.

Cand  aplici o sarja cum faci pe biti mai exact? Eu aveam doua operatii pentru a obtine noua configuratie si luam 80p; cand am inversat ordinea in care faceam operatiile am luat 100p (se pare ca asa ajunge mai repede la destinatie)

Fac nod & sarja

Fa operatiile in ordine inversa aici.

10x domino. Acum a rulat super repede 0.1 sec cel mai mult. De fapt asta si era si ordinea: intii petrica aplica sarja si apoi sobolanul se muta.

Pentru

da cumva

Am "You spent to much!" pe ultimele 8 teste...  :(

2650
2
2
2

     Stiti sa imi spuneti si mie de la ce as putea avea eroarea "Incompatible output!"? Sursa mea ia 80 puncte, cu eroarea acesta pe testele 6 si 9. Am vazut erori de genul ,,The rat is still alive!" sau  ,,You have spent too much!", dar in acest caz nu reusesc sa imi dau seama de unde ar putea fi.

"Daca acesta este intr-una din camerele gazate moare pe loc; daca nu, camera nu pateste nimic si sobolanul poate circula prin ea imediat dupa detonarea bombei."

Cred ca e un pic mai clar asa.

iau 80 de pct cu TLE si nu stiu de ce :-k.

Ca idee, cat de mare poate fi costul unei sarje?

2^21 cred

cred ca ar mai trebui marita un pic limita de timp  :-' :-'
cu o sursa de o(2^20 * m) cu optimizarile pe biti nu iau decat 90 :(

E prea mica limita de timp

Limita e buna am luat 100 cu priority queue din stl, ar trebui chiar micsorata pentru a lua 100 numai cu heap-uri de mana.

Am "You have spent too much!" pe ultimele 8 teste, si totusi imi merg toate testele date pe forum. Poate sa mai imi dea si mie cineva un test? Multumesc.

De ce nu generezi tu testele si sa ne ceri doar rezultatul corect? E tare neconvenabil sa ne gandim noi ce ai fi putut tu gresi si sa generam teste cu astfel de exemple.

ok. Imi cer scuze. Pentru

e bun:

??

Iti da bine.

Am si eu o nelamurire despre cum se formeaza graful. Eu am incercat sa parcurg toate nodurile de la 0->2ⁿ-1 si pentru fiecare nod aflu vecini are cam asa:
Problema este ca atunci cand fac Dijkstra de la 0 la 2ⁿ-1, pe exemplu imi da 3(de la nodul 0 folosind sarja 1 merge in 5 si din 5 folosind sarja 2 merge in 7). Am gresit modul de constructie al grafului sau imi scapa altceva...?

Salut. Am facut problema de 100 dar am o nelamurire. :D Am doua surse care iau 100, una cu heapuri de mana optimizate pe biti si cealalta care foloseste priority_queue din STL. 8) Siiii spre surprinderea mea sursa cu heapuri merge muuult mai greu decat aia cu PQ...ca sa nu mai vorbim de memorie care ii dubla. Memoria sa zicem ca o inteleg deoarece presupun ca o sa am pe teste random, relativ putine noduri in heap la un moment dat. Dar heapurile de mana nu ar trebui sa mearga mai rapid?!? ](*,)  ???