•DITzoneC
|
|
« : Martie 25, 2007, 13:25:59 » |
|
Aici puteţi discuta despre problema Regiuni.
|
|
|
Memorat
|
|
|
|
•skyel
|
|
« Răspunde #1 : Martie 25, 2007, 13:35:21 » |
|
un O(n*m) intra in timp?
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Martie 25, 2007, 13:36:43 » |
|
Intra si O(N * M * log M)
|
|
|
Memorat
|
|
|
|
•skyel
|
|
« Răspunde #3 : Martie 25, 2007, 13:38:47 » |
|
clar ma arunc de pe bloc , si sper ca data viitoare sa gandesc si sa nu mai incerc cu structuri de date sinucigase
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #4 : Martie 25, 2007, 13:39:47 » |
|
eu am luat 70 cu o(m*log m * (n/30)). (am comprimat niste numere folosind baza 2)
|
|
|
Memorat
|
|
|
|
•skyel
|
|
« Răspunde #5 : Martie 25, 2007, 13:42:58 » |
|
si io tot folosind baza 2 am incercat...exprimam unicitatea unei regiuni in functie de cum era localizata fata de o dreapta.....da nu m-am gandit sa fac cu o matrice de char-uri si am transformat din nou in baza 10....(2.000.000.000 < 1<<1000 ) LE: asta pe langa faptul k puteam doar pana la 1 mil k aveam vectoru in care notam regiunile un int de 1 mil
|
|
« Ultima modificare: Martie 25, 2007, 13:47:03 de către Ghitulete Razvan »
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #6 : Martie 25, 2007, 13:51:48 » |
|
|
|
« Ultima modificare: Martie 25, 2007, 13:55:50 de către Savin Tiberiu »
|
Memorat
|
|
|
|
•skyel
|
|
« Răspunde #7 : Martie 25, 2007, 13:54:22 » |
|
poi km asa m-am gandit si eu da..... fara matrice
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #8 : Martie 25, 2007, 15:55:36 » |
|
Da, cred ca mergea fara matrice... Eu de fapt retineam doar linia curenta A[j] = de ce parte a semiplanului e pct j fata de dreapta i... apoi parcurgeam grupurile actuale si pt fiecare daca aveam si pct de o parte si pct de alta, atunci inseamna ca imparteam grupul in doua, si parcurgeam iar lista de pucnte ca sa ii atribui noul grup fiecarui punct "mutat"... iese O(N*M), in concurs am bagat g[ j ][...] in loc de g[ b [j] ][...] si s-a dus toata, ca luam 80 (2 wa) si prindeam finala Aia e, poate la anu... [LE] acu iau 100... mai gresisem si o limita a unui for
|
|
« Ultima modificare: Martie 25, 2007, 15:59:38 de către Sima Cotizo »
|
Memorat
|
|
|
|
•fireatmyself
|
|
« Răspunde #9 : Martie 25, 2007, 18:23:36 » |
|
DP[ i ][ j ] = semnul pe care il are expresia a[ j ]*x[ i ]+b[ j ]*y[ i ]+c[ j ]. (a[ j ], b[ j ], c[ j ] coeficentii dreptei j). Cu liniile acestei matrici se construia un trie. Raspusul cautat era numarul de frunze pe care il are arborele respectiv. Complexitate O(N*M), memorie O(N*M).
Ideea comprimarii acestei matrici (informatiile de pe linia i pentru primele 31 de drepte erau tinute pe primii 31 de biti ai lui DP[ i ][ 1 ], urmatoarele 31 de drepte pe bitii lui DP[ i ][ 2 ], etc.) si verificand in O( N*(N-1)/2 * M/31 ) daca oricare doua puncte au aceleasi semne fata de drepte, aducea tot 100 de puncte. Acest lucru se intampla din cauza faptului ca este destul de grea generarea unor teste care sa determinie algoritmul tau sa faca acel numar de operatii.
Anul trecut, la barajul pentru selectia lotului largit, problema 'Cifru' a intampinat aceesi dificultate in departajarea unor solutii optime de altele neoptime (neoptime cel putin teoretic).
|
|
« Ultima modificare: Martie 25, 2007, 18:36:12 de către Bogdan A. Stoica »
|
Memorat
|
Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
|
|
|
•devilkind
|
|
« Răspunde #10 : Martie 25, 2007, 19:25:36 » |
|
eu nu verificam in n^2, le sortam in n log n (bineinteles inmultite cu m/31 toate) si verificam numarul de secvente egale. Daca (,) calculezi complexitate pe testul maxim (n=1000, m=1000) vei vedea ca e mai mica decat n*m. 1000*10*35 < 1000*1000 Oricum poate ca e doar parerea mea, dar cred ca la clasa a X-a e cam mult trie.
|
|
« Ultima modificare: Martie 25, 2007, 19:28:50 de către Savin Tiberiu »
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #11 : Martie 25, 2007, 20:13:50 » |
|
Cel mai simplu poti sa consideri semnele ca fiind cifre iar sirul un numar in baza 2 (de exemplu semnul -1 corespunde lui 0 si +1 lui 1) si acum nu ai decat de facut un hash (rabin-karp), adica calculezi numarul asta % un numar prim mare. Daca esti paranoic poti considera mai multe numere prime mari si calculezi restul pentru toate
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #12 : Martie 25, 2007, 20:27:23 » |
|
m-am gandit si la asta dar nu am vrut sa ma mai complic cu alocare dinamica (nush hashing static) si mi s-a parut destul de usor de implementat asa, si dupa calculele mele intra in timp. De fapt a si intrat doar ca in concurs am spart linia de cache de prea multe ori (mergeam invers si nu mi-am dat seama si am pierdut 30 de pct din cauza asta). Oricum misto problema.
|
|
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #13 : Martie 25, 2007, 22:08:57 » |
|
La hash static aloci la inceput un tablou (cel putin asa inteleg eu sa faci hash static) Dar ce spuneam eu aici e ca nu ai nevoie de chestia asta, daca 2 elemente au aceleasi chei le consideri egale, adica consideri ca nu apar deloc coliziuni.
|
|
« Ultima modificare: Martie 25, 2007, 22:11:07 de către Airinei Adrian »
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #14 : Martie 25, 2007, 22:27:55 » |
|
nush mi se pare destul de riscant sa nu tratezi coliziunile. Adik dak ai o singura coliziune se duce tot rezultatu ptr ca ai vrut sa optimizezi o operatie acolo. Oricum cred ca mi-am dat seama cum as putea face hashing static cu probabilitate f mica de coliziune, dar nu cred ca poate fi redusa total acea probabilitate. Cred ca singura modalitate de a trata coliziunile 100% corect e cu alocare dinamica.
|
|
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #15 : Martie 26, 2007, 08:54:35 » |
|
Tocmai asta e principiul pe care se bazeaza rabin-karp, daca tu tot timpul o sa compari 2 siruri care au chei egale te duci in O(N^3).
|
|
|
Memorat
|
|
|
|
•Bluedrop_demon
Client obisnuit
Karma: -3
Deconectat
Mesaje: 66
|
|
« Răspunde #16 : Martie 26, 2007, 13:47:09 » |
|
Am pus o sursa care zic eu ca e super-ok si ar merita 100 de puncte. In afara de 30 de p nu pot insa obtine. La testele pe care nu le iau primesc "Non-zero exit status" (sursa e in free pascal) . In afara de faptul ca asta inseamna ca programul da eroare undeva, imi puteti spune mai multe detalii despre cum as putea afla de ce se intampla de fapt cand primesc un astfel de mesaj ? In caz ca ar fi o posibilitate, am verificat sa nu am nicaieri impartire la 0, deci nu e de aici.
|
|
|
Memorat
|
|
|
|
•skyel
|
|
« Răspunde #17 : Martie 26, 2007, 19:45:23 » |
|
Non-zero exit status: Programul tau a returnat o valoare diferita de 0. Cel mai probabil ai uitat return 0; sau ceva similar.
|
|
|
Memorat
|
|
|
|
•vlad_D
Client obisnuit
Karma: 32
Deconectat
Mesaje: 67
|
|
« Răspunde #18 : Martie 27, 2007, 02:12:54 » |
|
la regiuni nu era limita de memorie mai mare ?? (acu e Limita de memorie 128 kbytes)
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #19 : Martie 27, 2007, 06:46:08 » |
|
s-a schimbat deoarece intrau niste bulaneli. Insa oricum mi se pare cam drastic ptr ca multe solutii corecte au luat 0 (inclusiv a mea). Cred ca ar trebui facuta o alta schimbare ptr ca o solutie care este mentionata in articol ca fiind corecta nu ar trebui sa ia 0.
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #20 : Martie 27, 2007, 06:50:48 » |
|
Pai a fost corecta pentru concurs in arhiva e altceva .
|
|
|
Memorat
|
|
|
|
•gcosmin
|
|
« Răspunde #21 : Martie 27, 2007, 08:44:22 » |
|
eu am o(n) memorie si nu intra... intr-adevar constanta e cam de 9... dar totusi.... 128...
|
|
« Ultima modificare: Martie 27, 2007, 08:53:06 de către Gheorghe Cosmin »
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #22 : Martie 27, 2007, 08:44:56 » |
|
am un vector pe care vreau sa il sortez in N^2 for(i = 1; i <= N; i++) for(j = i+1; j <= N; j++) if(A[i] > A[j]) swap(A[i], A[j]);
Daca pun in comentariu cele 2 foruri care imi sorteaza vectorul memoria folosita maxim pe un test este 12kb. Daca trimit sursa cu tot cu for-uri iau memory limit exceeded pe 9 teste. Nu e totusi cam drastica limita?
|
|
|
Memorat
|
|
|
|
•gcosmin
|
|
« Răspunde #23 : Martie 27, 2007, 08:48:17 » |
|
eu am calculat ca (9 * 1010 * 4 + (ce o mai fi pe acolo)) / 1024 < 40... sigur e 128 kbytes memoria?
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #24 : Martie 27, 2007, 08:50:54 » |
|
eu am 11*1024 * 4 / 1024 = 44 KB si eu MLE pe 9 teste
|
|
|
Memorat
|
|
|
|
|