infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Septembrie 19, 2005, 22:59:33



Titlul: 113 Bile
Scris de: Mircea Pasoi din Septembrie 19, 2005, 22:59:33
Aici puteţi discuta despre problema Bile (http://infoarena.ro/problema/bile).


Titlul: 113 Bile
Scris de: Ovidiu Rosca din Noiembrie 16, 2005, 20:48:30
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?


Titlul: 113 Bile
Scris de: andreit1 din Noiembrie 16, 2005, 21:30:10
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.


Titlul: Răspuns: 113 Bile
Scris de: Adelina Spataru din Octombrie 05, 2009, 15:31:42
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


Titlul: Răspuns: 113 Bile
Scris de: Sherlock Holmes din Martie 16, 2010, 14:36:03
puteti da un exemplu mai mare ?


Titlul: Răspuns: 113 Bile
Scris de: Sfrent Andrei din Mai 05, 2010, 21:17:47
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


Titlul: Răspuns: 113 Bile
Scris de: Guianu Leon din Februarie 27, 2013, 11:52:25
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 (http://infoarena.ro/job_detail/895645)


Titlul: Răspuns: 113 Bile
Scris de: Avramescu Cristian din Iunie 06, 2013, 22:13:46
Buna seara,
 Ma chinui la problem asta de ceva timp si nu reuesesc sa trec de 90 :oops: ( TLE pe testul 8 ) . In principiu folosesc padurile . Ce ar trebuie sa fac sa iau si testul ala ?
Multumesc anticipat!


Titlul: Răspuns: 113 Bile
Scris de: Pirtoaca George Sebastian din Iunie 07, 2013, 13:59:58
Implementeaza padurile folosind cele 2 euristici: reuniunea dupa rang si compresia drumurilor.


Titlul: Răspuns: 113 Bile
Scris de: hiticasabel din Iunie 18, 2013, 12:36:22
Cum as putea folosi la problema asta padurile ? Chiar nu am nici o idee.


Titlul: Răspuns: 113 Bile
Scris de: Paul-Dan Baltescu din Iunie 18, 2013, 13:35:51
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.


Titlul: Răspuns: 113 Bile
Scris de: Marian Iacob din Noiembrie 06, 2013, 18:07:21
m-am uitat pe solutii oficiale, dar orcum nu inteleg ce trebuie sa fac...poate cineva sa mi dea un hint mai bun :oops:!


Titlul: Răspuns: 113 Bile
Scris de: Mihai Ionut Enache din Noiembrie 07, 2013, 00:00:14
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).


Titlul: Răspuns: 113 Bile
Scris de: Marian Iacob din Noiembrie 07, 2013, 17:12:46
mi-a esit! :yahoo: va multumesc mult narcis_vs si Mihai22e ! :)


Titlul: Răspuns: 113 Bile
Scris de: Paius Teodor din Noiembrie 12, 2013, 16:00:00
Ma poate ajuta si pe mine cineva? Iau 90 de puncte si nu inteleg de ce fix la ultimul test imi da incorect :x Ce-i diferit la el fata de celelalte? Si da am avut grija sa ma incadrez in limite


Titlul: Răspuns: 113 Bile
Scris de: Valeriu Motroi din August 10, 2014, 12:52:19
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!


Titlul: Răspuns: 113 Bile
Scris de: Popescu George din Octombrie 10, 2014, 15:13:17
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?


Titlul: Răspuns: 113 Bile
Scris de: Victor Popa din Mai 29, 2017, 14:46:39
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