376 Regiuni

[•DITzoneC]

Aici puteţi discuta despre problema Regiuni.

[•skyel]

un O(n*m) intra in timp?

[•bogdan2412]

Intra si O(N * M * log M)

[•skyel]

clar ma arunc de pe bloc  , si sper ca data viitoare sa gandesc si sa nu mai incerc cu structuri de date sinucigase

[•devilkind]

eu am luat 70 cu o(m*log m * (n/30)). (am comprimat niste numere folosind baza 2)

[•skyel]

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

[•devilkind]

nu prea aveai nevoie de asa ceva. Eu am folosit o matrice A[ i ][j] - semiplanul in care se afla punctul i fata de dreapta j.

[Later edit] am luat 100 in arhiva  trebuia sa construiesc matricea invers. In concurs am mers in principal pe coloane si apoi pe linii, akuma am inversat si am luat 100 

[•skyel]

poi km asa m-am gandit si eu da..... fara matrice

[•sima_cotizo]

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 

[•fireatmyself]

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

[•devilkind]

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.

[•astronomy]

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

[•devilkind]

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.

[•astronomy]

La hash static aloci la inceput un tablou

Cod:

H[max_key][max_elems]

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

[•devilkind]

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.

[•astronomy]

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

[•Bluedrop_demon]

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.

[•skyel]

Non-zero exit status: Programul tau a returnat o valoare diferita de 0. Cel mai probabil ai uitat return 0; sau ceva similar.

[•vlad_D]

la regiuni nu era limita de memorie mai mare ?? (acu e    Limita de memorie   128 kbytes)

[•devilkind]

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.

[•Cosmin]

Pai a fost corecta pentru concurs in arhiva e altceva .

[•gcosmin]

eu am o(n) memorie si nu intra... intr-adevar constanta e cam de 9... dar totusi.... 128...

[•astronomy]

am un vector

Cod:

int A[1024]

pe care vreau sa il sortez in N^2

Cod:

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?

[•gcosmin]

eu am calculat ca (9 * 1010 * 4 + (ce o mai fi pe acolo)) / 1024 < 40... sigur e 128 kbytes memoria?

[•devilkind]

eu am 11*1024 * 4 / 1024 = 44 KB si eu MLE pe 9 teste