Problema Race de la IOI 2011

[•Cosmin]

Comentarii la http://infoarena.ro/blog/problema-de-ioi

[•mpatrascu]

Pe toate 5

Să știi că 3-ul din lista ta nu prea seamănă cu cea de la IOI, deși pare. Multă lume a luat-o în direcții foarte greșite la IOI.

[•Mishu91]

La primele 3 se cere O(N) "pur"? Pentru ca imi vin in minte niste solutii cu hashuri.

[•MciprianM]

La prima, nu trebuie cumva sirul sa fie sortat ca sa iasa O (n) ?
L.E.: De fapt la primele 2?

[•Magnus]

merg cu hashuri in O(n) fara sortare 

[•MciprianM]

Eu ma gandeam la O(n) worst-case, si nu expected !

[•cr1st18]

Sunt de acord cu Daniel, la primele doua probleme merge o rezolvare in O(n) cu hash-uri ...

[•crushack]

Da, se pot face cu hash-uri, dar nu numai, daca nu vrei sa ai expected O(n) atunci poti sa faci cu radix-sort si cu o constanta frumusica (+ O(N) memorie ), la 3 n-am gasit solutie decat cu hashing , la 4 e dinamica si 5... ma gandesc

[•Cosmin]

@mpatrascu, da, ai nevoie doar de 1 si 4 ca sa rezolvi 5, dar 2 si 3 sunt dragute ca tema de gandire

[•klamathix]

Da, se pot face cu hash-uri, dar nu numai, daca nu vrei sa ai expected O(n) atunci poti sa faci cu radix-sort si cu o constanta frumusica (+ O(N) memorie ), la 3 n-am gasit solutie decat cu hashing , la 4 e dinamica si 5... ma gandesc

Ma cam indoiesc ca poti caracteriza radix sort-ul ca fiind O(n) cu o constanta frumusica. Radix sort-ul e O(n * r) unde r e numarul de radix-uri.. care nu prea stiu cum sa-l iei astfel incat sa fie constant relativ la n si la magnitudinea numerelor. Daca iei dupa cifre de exemplu e O( N lg MAX ).

In schimb, cand vine vorba de suffix arrays zice lumea ca e O(n) radix-ul. Nu stiu cum se accepta in general. Poate ne lumineaza cineva cu ocazia asta .

[•crushack]

La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2³¹ Lmax=31, deci complexitatea e O(N*31) => O(N)

[•Mishu91]

La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2³¹ Lmax=31, deci complexitatea e O(N*31) => O(N)

Dupa rationamentul de mai sus, complexitatea O(NlogN) este acelasi lucru cu O(N), pentru orice N <= 2³¹

[•klamathix]

La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2³¹ Lmax=31, deci complexitatea e O(N*31) => O(N)

Din cate stiu eu, cand descrii un algoritm nu prea ai voie sa faci aproximari de genul. Complexitatea trebuie sa fie valabila pentru orice input, orice restrictii, orice instanta a problemei. Aici nici nu iti garanteaza nimeni ca numerele sunt pe 32 de biti.

Despre complexitatea padurilor de multimi disjuncte, de exemplu, poti spune ca 'pentru orice valori fezabile din punct de vedere tehnic se poate aproxima cu O(1)' , dar nu ca este O(1). E O(log*) toata ziua. Asa stiam eu cel putin.

[•devilkind]

In cazul radixsortului poti sa zici ca e O(N) deoarece numarul de operatii e "egal" cu volumul inputului. Mai exact, daca tu ai urmatoarea problema:
Se citesc N caractere de la tastatura. Fiecare caracter este ori un numar de la 0-9 sau spatiu. Se cere sa sa spargi sirul de caractere dupa spatiu, sa iei numerele rezultate si sa le sortezi. Care e complexitatea daca folosesti radixsort?

E o confuzie care se face destul de mult in practica, si anume sa adaugi in complexitate valori date in enuntul problemei, pentru ca ai anumite constrangerii care iti spun ca valorea respectiva nu va depasi o constanta. Totusi in teorie astfel de constrangerii nu exista si de aceea cand se spune O(N), N este considerat ca fiind volumul datelor de intrare. Exemplu: Daca o sa luati cormenul la mana o sa observati ca problema rucsacului e clasificata ca fiind NP. De ce? Deoarece in analiza complexitatii intra in calcul valoarea maxima a numerelor, care creste exponential in raport cu numarul de caractere al datelor de intrare.

[•Vman]

e O(N) pt ca numarul de bucketuri e constant si atunci cand calculezi complexitatea nu iei in calcul constantele, dat fiind ca daca N tinde la infinit constantele astea devin mult prea mici sa mai conteze. In practica in schimb daca ai o constanta maricica ar cam trebui sa incerci sa o reduci, un O(N^2) cu constanta 1/2 poate fi o solutie mai buna decat un O(NlogN) cu constanta mare atunci cand introduci constrangeri pt N