infoarena

Runda 3 tocmai s-a încheiat. Felicitări câștigătorilor (http://www.infoarena.ro/algoritmiada-2014/runda-3/clasament/5-8)! Așteptăm feedback-ul și părerile voastre.

O runda cu probleme foarte frumoase!Felicitari tuturor participantilor!  :D

Runda mi s-a parut interesanta. Problemele, mai grele decat de obicei au fost probabil menite sa departajeze participantii pentru runda finala. Limitele au fost cam mari pentru gustul meu (adica nu stiam daca o sa-mi intre nici una dintre probleme, caci stiam ca set-ul e O(log) cu o constanta de ~4). La problema cu subsecventa comuna solutia oficiala e tot hash? Caci vad ca nu mi-a intrat in timp pe 2 teste. Ar mai merge marita limita de timp putin la problema aia. Problema reborn nu am reusit sa o finalizez (nici macar brutul de ordin 2 (adica inbunatatit nitel)), dar mi s-a parut o problema grea de departajare (spre deosebire de celelalte nu avea limitele mari, ci era greu de bagat si greu de vizualizat). Oricum  :thumbup: pentru runda.
Andrei

Solutia oficiala la Potriveala este O(N + M) si nu foloseste hash-uri.

Foarte frumoase problemele, o runda reusita dupa parerea mea. As fi si eu curios de ideea de rezolvare de la Reborn pana apare articolul cu solutii. Felicitari castigatorilor!

Problemele au fost reusite si variate. A meritat asteptarea. Cand se va anunta cati vor merge mai departe la fiecare grupa de varsta ?

Felicitari pentru runda! Care e complexitatea oficiala la Reborn? Ca eu am facut (N+Q)sqrt(N) si a intrat lejer, desi stiu ca se poate si (N+Q)log(N). Pe langa asta, ne puteti oferi detalii cu privire la calificarea la runda finala?

Brute force ia 70 la Potriveala :)

Dinamica de la rmq ca sa afli cat poti merge la dreapta cu 2^k arme. Apoi cauti binar numarul minim de arme.

George, ce magie de optimizare ai facut sa-ti mearga de 70 cu brute, eu am luat 70 cu O(n+m) cu hash-uri?  :-k

Care brut ia 70?

Anyway frumoasa runda :)

Am luat toate pozitiile pentru care A[i] == B[0] si am verificat cat pot merge in stanga si in dreapta lor  8) Am trimis la disperare si se pare ca am avut noroc.

Eu bagasem NlogN dar probabil cu constanta prea mare (60 de puncte)

Inainte sa apara articolul cu solutii, voi posta aici o scurta descriere a acestora:

Sliding Window
Parcurgem numerele si retinem ultimele D + 1 intr-un multiset. Cand inseram o valoare noua, cautam care e cea mai mare valoare mai mica sau egala cu ea si cea mai mica valoare mai mare ca ea. Astfel, putem actualiza raspunsul la fiecare inserare.
Complexitatea este O(N * logD).

Progresii2
Putem numara usor progresiile cu o ratie R fixata, intrucat avand primul termen fixat, restul termenilor sunt unic determinati. Astfel, pentru a determina numarul tuturor progresiilor, trebuie sa calculam suma expresiilor obtinute si o prelucrare atenta a termenilor duce la o formula ce poate fi calculata in timp constant.
Complexitatea este O(T).

Perioada2
O observatie esentiala este aceea ca orice perioada a sirului este formata prin concatenarea celei mai mici perioade a sirului. Astfel, problema se rezuma la a determina cea mai scurta perioada (se poate folosi KMP) si a vedea cati multipli ai lungimii perioadei sunt divizori ai lungimii sirului.
Complexitatea este O(N).

Reborn
Putem utiliza o structura de date (de exemplu, arbore de intervale sau set) pentru a determina pentru fiecare casa care e cea mai din dreapta pozitie unde poate fi reinviat Tsuna folosind o singura arma. Apoi, putem folosi o dinamica de tip RMQ si sa cautam binar raspunsul la fiecare query.
Complexitatea este O(N * logN + Q * logN).

Potriveala
Restrictia esentiala care permite rezolvarea problemei in timp liniar este faptul ca raspunsul este cel putin M. Astfel, subsecventa comuna de lungime maxima va arata astfel: (sufix al lui B) + (B + B + B + ... + B) (de K >= 0 ori) + (prefix al lui B). Pentru a nu avea probleme cu periodicitatea, putem sa concatenam sirul B la el insusi, pana cand lungimea acestuia devine cel putin egala cu lungimea lui A. Astfel, ramane de calculat cel mai lung prefix comun pentru noul sir B si fiecare pozitie din A, respectiv, cel mai lung sufix comun pentru noul sir B si fiecare pozitie din A. Acest lucru se poate realiza folosind Z-Algorithm.
Complexitatea este O(N + M).

Marsmusic
Solutia oficiala este o dinamica de tip rucsac care foloseste timp O(N * M^2) si memorie O(N * M).
Vom incerca sa calculam DP[time] = probabilitatea ca o melodie oarecare sa inceapa la momentul time. Pentru aceasta, vom folosi o dinamica auxiliara, DP2[n][count][time] = probabilitatea ca din primele n melodii, o melodie oarecare sa inceapa la momentul t, stiind ca au fost difuzate exact count melodii inaintea ei. In recurenta trebuie analizate doua cazuri: melodia n va fi difuzata dupa cele count melodii (si astfel DP2[n][count][time] depinde de DP2[n - 1][count][time] cu probabilitate (n - count) / n), sau va fi difuzata inaintea lor (si DP2[n][count][time] depinde de DP2[n - 1][count - 1][time - Durata[n]] cu probabilitate count / n).
Acum vom incerca sa determinam pentru fiecare melodie timpul mediu de intersectie pe cele doua posturi utilizand dinamica mentionata anterior (din care vom "scoate" melodia curenta, intrucat aceasta nu poate fi folosita) si sume partiale.

Asa am facut si eu, doar ca nu am stiut cum sa "scot" melodia curenta. Deci, am refacut dinamica pentru fiecare melodie si a devenit N * M^3. Poti detalia?

In loc sa refaci dinamica de fiecare data poti sa faci o singura dinamica la inceput (cu toate M) si la fiecare pas sa incerci sa obtii dinamica fara un element din aceasta. E un fel de rucsac inapoi :-)

Runda a fost interesanta. Eu a problema "potrivireala" am facut pur si simplu un KMP si verifcam care este cea mai lunga subsecventa intreaga si dupa vedeam cu cat te extinzi in stanga si in dreapta. Complexitatea este tot O(N + M) amortizat. La problema "sliding windows" am facut doar un set cu lower_bound si aparent am luat 100(prima data am luat 100 dupa am crezut ca nu intra in timp fara parsare si am luat MLE). La problema "reborn" am incercat sa fac un fel de brut cu cautare binara dar nu a mers si inca sunt curios de ce nu merge ca iau TLE pe toate testele. Felicitari comisiei pentru aceasta runda!

Am si eu o mica sesizare de facut.La problema potriveala unele surse de 100 pica pe urmatorul test:

BCABCABC
ABCABC

Un exemplu ar fi aceasta sursa, desi nu stiu daca este singura
http://www.infoarena.ro/job_detail/1195730

"Fie un sir de caractere simplu A de N caractere si unul periodic si infinit B cu perioada de M caractere."

Sirul din testul tau are perioada M / 2, nu M.

Citez din pagina cu intrebari destinata problemei "potriveala" (http://www.infoarena.ro/forum/index.php?topic=9987.0) intrebarea:
si raspunsul:

De asemenea, sursa de 100 a lui Matei Paun din concurs pica pe testul:

BCAB
ABC

In fine nu vreau sa zic ca au fost teste gresite, ci doar ca unele cazuri nu au fost tratate, cazuri care nu sunt chiar asa evidente ce-i drept...

Ca intotdeauna, nu ne putem astepta la orice greseli din partea participantilor. Din pacate au intrat solutii de 100 la mai multe probleme, solutii care nu erau chiar de 100.

Mai avem si problema in comisie ca nu putem face optimizari magice si sa ne bazam ca veti face si voi asta, desi ar reduce timpii de 4-5 ori pe cand participantii le pot folosi astfel incat sa le intre solutii cu complexitate mai proasta (nu ma refer la problema potriveala).
 Testele au fost facute in principiu sa pice KMP-ul si alte bulaneli (de acolo toate punctajele de 70 de puncte).

Da,sunt de acord cu ce zici.Eu nu zic ca ar trebui modificate testele sau ceva, mai mult as vrea sa vada o parte din cei ce au luat 100 ca solutia lor nu e tocmai legit.

Nu chiar toate solutiile de 70p sunt bulaneli. Unele sunt doar mai proaste din punctul de vedere al constantei (hash-uri).

Total de acord. Daca ar fi mai mult timp poate ar trebui sa facem o arhiva cu problemele corectate, adica:

1) Optimizat pe cat posibil, parsare tot, despre care se spune in enunt pentru ca nu asta sa conteze ci complexitatea
2) Mult mai multe teste si grupate, sa fie 0 sau 100.

Nu la asta ma refeream. :peacefingers: Eu voiam doar sa subliniez faptul ca nu toate solutiile care au luat 70 sunt bulaneli, unele sunt doar putin mai incete din cauza constantei. :thumbup:

Se poate rezolva etapa asta mai simplu dpdv. al implementarii, aplicand o interclasare a intervalelor in sir:

De mentionat ca problema admite si o solutie O(N) O(NlogK) teoretic. Dau o bere sau 5GB pe Dropbox cui o scoate  :wink:

Daca D = N atunci problema se reduce la distanta minima intre doua elemente ale sirului. Problema asta nu se poate rezolva mai rapid de O(N log N), deci faci ceva presupunere gresita Vlad.

Ai dreptate Cosmin, ceea ce vreau eu e de fapt o rezolvare O(N) pentru un K fixat. Deci O(NlogK) per total :)

Zi enuntul problemei pe care o vrei tu in O(n). Ca pot vedea mai multe interpretari.

pentru K fixat determinati daca exista 2 pozitii i, j (i < j) a.i.

| Ai - Aj | ≤ K
j - i ≤ D

spoiler alert (selectati textul pentru rezolvare):

se pot asocia elementelor x chei cu valoarea [x / k], dupaia folosim un hash table si rezolvam in O(n):
daca exista mai multe valori cu aceeasi cheie problema e rezolvata,
daca nu putem verifica pt fiecare i cheile [x/k] + 1 si [x/k] - 1. (evident, acestea vor contine cel mult un element)

Dau berea cu prima ocazie  =D&gt;

O sa iti schimb culoarea textului in alb, poate mai sunt utilizatori care vor sa se gandeasca la solutie.

Andrei, la problema Marsmusic faci practic pt fiecare melodie suma modurilor in care se suprapun in toate cazurile?
Daca da .. faci pe numere mari si imparti la m!
Si in cazul asta, se poate sa fac fara numere mari (aceeasi rezolvare) doar cu double?

In solutia noastra, nu este nevoie nici de numere mari si nici de calcularea lui M!.
Avand dinamica DP[song][time] = probabilitatea ca melodia song sa inceapa la momentul time, putem calcula suma din DP[song][t1] * DP[song][t2] * Intersection([t1, t1 + Duration[song] - 1], [t2, t2 + Duration[song] - 1]) cu ajutorul unor sume partiale. Rezultatul cumulat al acestor sume pentru fiecare melodie va constitui raspunsul.
Pentru a calcula DP[song][time], putem folosi dinamica auxiliara pe care am descris-o anterior: DP2[n][count][time] = probabilitatea ca melodia n sa inceapa la momentul t, stiind ca au fost difuzate exact count melodii dintre primele n - 1 inaintea ei. Recurenta este DP2[n][count][time] = DP2[n - 1][count][t] * (n - count) / n + DP2[n - 1][count - 1][t - Duration[n]] * count / n.

Cand se vor mai putea trimite solutii la probleme ?

Imediat ce vor fi puse în arhiva de probleme. Nu ar trebui sa mai dureze mult.  :ok:

Cand faceti update la rating?

Pai cred ca mai dureaza ceva din moment ce nici la ONIS nu s-a facut update.(iar ONIS a fost mai devreme ca Monthly)