043 Boom

[•domino]

Aici puteţi discuta despre problema Boom.

[•ParrAzitU]

Asi avea si eu o problema la probl. Am facut o rezolvare care cred ca e buna, dar nu obtin doar 90   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

[•domino]

Asi avea si eu o problema la probl. Am facut o rezolvare care cred ca e buna, dar nu obtin doar 90   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:

Cod:

boom.in
5 5
777 1 1
1325 1 2
4431 1 3
9774 1 4
7086 1 5

Cod:

boom.out
31060
6
2
3
4
2
3
4

[•teplesnescdenutevezi]

imi da si mie cineva o idee la problema asta ?

[•Cosmin]

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.

[•teplesnescdenutevezi]

da...ar fi ceva. multumesc mult.

[•gogu]

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

[•silviug]

Voi ati bagat jumatate din teste de dimensiune maxima?

NU.

Bagati teste mai echilibrate

 

[•gogu]

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.

[•silviug]

Urmeaza Q numere (Q nu este mai mare decat 4) reprezentand camerele gazate.

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.

[VladS]

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.

[•domino]

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)

[VladS]

Fac nod & sarja

Cod:

int nod=(c<<1)|(c>>1);
if (nod>=(1<<n)) nod-=1<<n;
nod&=sarje[i];
}

[•domino]

Cod:

      int nod=(c<<1)|(c>>1); 
      if (nod>=(1<<n)) nod-=1<<n; 
      nod&=sarje[i]; 

Fa operatiile in ordine inversa aici.

[VladS]

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.

[•Marius]

Pentru

Cod:

5 5 
777 1 1 
1325 3 2 3 4
4431 2 3 1
9774 2 4 5
7086 1 5

da cumva

Cod:

13843
7
2
1
1
2
1
3
3

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

[•bogdan2412]

Cod:

2650
2
2
2

[•otilia_s]

     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.

[•Bit_Master]

"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.

[•mihai995]

iau 80 de pct cu TLE si nu stiu de ce .

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

[•S7012MY]

2^21 cred

[•valentin.harsan]

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

[•S7012MY]

E prea mica limita de timp

[•PetcuIoan]

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.

[•assa98]

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.