113 Bile

[•domino]

Aici puteţi discuta despre problema Bile.

[•junior]

Initial, problema asta mi se parea foarte simpla... Totusi am ajuns la concluzia ca nu-i chiar asa... (cel putin pentru nivelul meu). Am incercat o rezolvare cu graf si comp conexe pe care am luat 20... Apoi am optimizat la greu si am ajuns la 30. Alta varianta a fost sa incerc o rezolvare cu alg "fill". Tot 30 ia si asta....
Nu prea mai stiu ce sa-i fac. Are cineva vreo sugestie?

[andreit1]

Puteai sa faci si tu un calcul al complexitatii inainte sa zici ca e asa de simpla...
O abordare care ar putea aduce 100 de puncte ar fi sa pornesti de la coada si sa tot unesti componente conexe. Adica sa incepi cu n*n componente( bile) si orice eliminare a unei bine va fi acum considerata unirea unor componente( una sau mai multe). Daca utilizezi o structura de date convenabila poti sa obti logN pentru fiecare operatie. Adica o complexitate totala O(N^2*logN). Spor la tastat.

[•adelinas]

Ma chinui la aceasta problema de cateva zile si nu-mi iese. Problema este ca nu stiu ce nu imi da bine, pe exemplele mele imi iese. Imi poate trimite un administrator un mesaj privat cu cateva teste din cele de la 2 la 10? Multumesc anticipat

[•s_holmes]

puteti da un exemplu mai mare ?

[•andrei.sfrent]

bile.in

Cod:

4
1 3
2 1
1 1
2 4
1 4
4 4
4 2
4 1
3 3
3 1
4 3
2 2
3 2
3 4
2 3
1 2

bile.out

Cod:

15
14
13
11
11
10
9
8
5
4
4
1
1
1
1
0

[•Detrol2k]

Iau doar 80 de puncte. Imi da bine si pe exemplul de mai sus. Imi poate spune cineva ce cazuri nu acopar?
http://infoarena.ro/job_detail/895645

[•superman_01]

Buna seara,
 Ma chinui la problem asta de ceva timp si nu reuesesc sa trec de 90 ( TLE pe testul 8 ) . In principiu folosesc padurile . Ce ar trebuie sa fac sa iau si testul ala ?
Multumesc anticipat!

[•SebiSebi]

Implementeaza padurile folosind cele 2 euristici: reuniunea dupa rang si compresia drumurilor.

[•hiticas_abel]

Cum as putea folosi la problema asta padurile ? Chiar nu am nici o idee.

[•pauldb]

Gandeste-te cum ar fi daca ai construi solutia de la final spre inceput, iar fiecare celula a matricii ar fi un nod intr-un graf.

[•mvcl3]

m-am uitat pe solutii oficiale, dar orcum nu inteleg ce trebuie sa fac...poate cineva sa mi dea un hint mai bun !

[•Mihai22e]

Incearca sa refaci solutia pornind de la final (cand matricea este goala); gandeste-te ce se intampla cand asezi o bila pe tabla (daca se unesc componente conexe).

[•mvcl3]

mi-a esit! va multumesc mult narcis_vs si Mihai22e !

[•TeodorPaius]

Ma poate ajuta si pe mine cineva? Iau 90 de puncte si nu inteleg de ce fix la ultimul test imi da incorect Ce-i diferit la el fata de celelalte? Si da am avut grija sa ma incadrez in limite

[•Djok]

Teodor, nu m-am uitat prin sursa ta, dar aveam aceeași problemă ca și tine, nu luam ultimul test, și după ce m-am gândit un pic, am mărit limitele la toți vectorii cu ~250 de elemente(pe testul maxim poate vreo condiție să întreacă N*N), încearcă și tu, poate îți iese. SPOR!

[•gapdan]

Are cineva idee care e problema cu testul 8? Eu obtin TLE pe el. Din cate am observat in general la testul 8 se obtine acelasi timp ca la testul 9, iar pe testul 9 am timp 52ms... Are cineva vreun indiciu?

[•victore]

Stiu ca spun asta tarziu, dar daca mai ia 90 de puncte cineva din cauza timpului pe ultimul test, aveti grija cum si de cate ori folositi FindSet