[concurs] Facebook Hacker Cup Round 1A

[•CezarMocan]

Sambata, 22 Ianuarie 2011, de la ora 20:00, va avea loc Facebook Hacker Cup Round 1A .

[•DraStiK]

Dintre cei care ați participat, și ați rezolvat problema a doua, îmi spuneți va rog și mie o idee?

Mulțumesc anticipat.

[•MciprianM]

O incercare de explicatie a solutiei se gaseste aici si mai jos in acelasi topic. De asemenea gasesti cod postat intr-un thread Topcoder aici , iar codul din thread se gaseste la adresele Cod1 si Cod2. Eu nu am rezolvat acea problema si nici nu am inteles solutia inca. Sper sa te ajute link-urile astea!

[•filipb]

Ideea era ca daca aveai o secventa bitonica (almost-monotonic) v0 v2 ... vK, atunci pentru a afla diversitatea ei sortai numerele si raspunsul era x0 * (x1-1) * ... (xK-K), unde (xi) reprezinta secventa (vi) sortata. De exemplu, diversitatea pentru (1 7 4 2) este 1 * (2-1) * (4-2) * (7-3).
Acum intr-un subsir bitonic voiai sa bagi numerele in ordine crescatoare tocmai pentru a putea controla proprietatea de mai sus, si faceai dinamica D(p)(i)(j) = suma diversitatilor daca am ales secvente de lungime exact p, partea crescatoare se termina in i (deci are elemente din 1...i), si partea descrescatoare incepe de la j (deci are elemente in j+1...N).
Cand inserezi un nou element intre i si j ai grija sa fie mai mare decat capetele (element >= v(i) && element >= v(j)) si te uiti sa nu mai fie elemente egale cu el intre (i+1, pozitie-1) si (pozitie+1,j-1).

[•DraStiK]

Multumesc mult. Foarte tare idea.

[•costyv87]

Cum stii cand te-ai calificat ? Si apropo , trebuia neaparat sa am fisiere input si output ? Si daca da , cum trebuia sa se numeasca...

[•PlayLikeNeverB4]

Te-ai calificat daca ai cel putin o problema rezolvata corect. Te uiti la "View my score".

[•costyv87]

Si daca e bifat  inseamna ca e corect sau inseamna doar ca e trimisa , pentru ca nu prea imi dau seama )

[•PlayLikeNeverB4]

Eu presupun ca inseamna ca e corecta. Dar oricum, dupa ce expira cele 72 de ore primesti un mail cu rezultatul. (ori cu regrete, ori cu felicitari )

[•klamathix]

Puteti vorbi pe topicul din anul asta.