Algoritmiada 2013, Runda 2

[•visanr]

Mi se pare cam mica limita de timp la mergesort. Solutia mea(corecta), desi are O(N) complexitatea, ia TLE-uri pe aproape jumate de teste.

Si eu am tot O(N) si am luat 100, ultimele 2 teste au 92 ms. 

[•freak93]

Eu am 48 de ms. Limita a fost stransa pentru a departaja O(N)-urile de O(N log N).
Avem o sursa in N log N care merge mai repede ca a ta Cosmin.

Observatia cheie e ca iti trebuiau doar factorialele, dupa complexitatea devenea log^2.

[•SpiderMan]

Pana la urma, cu 2stacks ce faceti ?

[•repp4radu]

Pana la urma, cu 2stacks ce faceti ?

Avand in vedere dificultatile intampinate in rezolvarea situatiei de la problema 2stacks, am decis sa o scoatem din concurs.

[•PlayLikeNeverB4]

El intreba daca se refac testele si se pune problema in arhiva 

[•SpiderMan]

Am inteles chestia asta si faptul ca complexitatea dorita era de N², chiar daca nu s-a gasit una mai buna ca N³, dar am intrebat pentru ca eram curios daca o s-o refaca, sau .... nu.
[LE] Merci George, mi-ai luat-o inainte.

[•mihaipopa12]

Revin cu parerea ca este nedrept updateul ratingului la runda aceasta, cel putin la clasele 11-12 si 5-9 unde a fost data problema 2stacks.
Am inteles ca problema a fost scoasa din concurs dar cred ca intelegeti cat de frustrant este pentru concurentii care au avut "ghinionul" sa se apuce de ea si sa isi risipeasca timp considerabil pentru a o rezolva.

Nu vreau sa para ca ratingul este scopul activitatii mele pe infoarena, dar de exemplu nu inteleg de ce ati judecat acum situatia diferit de runda 6 de monthly, unde nu l-ati actualizat pentru ca in primele minute au fost niste teste gresite la feedbackul unei probleme.

In rest, sincere felicitari pentru probleme pentru ca au fost foarte reusite.

[•S7012MY]

Revin cu parerea ca este nedrept updateul ratingului la runda aceasta, cel putin la clasele 11-12 si 5-9 unde a fost data problema 2stacks.
Am inteles ca problema a fost scoasa din concurs dar cred ca intelegeti cat de frustrant este pentru concurentii care au avut "ghinionul" sa se apuce de ea si sa isi risipeasca timp considerabil pentru a o rezolva.

Nu vreau sa para ca ratingul este scopul activitatii mele pe infoarena, dar de exemplu nu inteleg de ce ati judecat acum situatia diferit de runda 6 de monthly, unde nu l-ati actualizat pentru ca in primele minute au fost niste teste gresite la feedbackul unei probleme.

In rest, sincere felicitari pentru probleme pentru ca au fost foarte reusite.

+1

[•Challenge]

Revin cu parerea ca este nedrept updateul ratingului la runda aceasta, cel putin la clasele 11-12 si 5-9 unde a fost data problema 2stacks.
Am inteles ca problema a fost scoasa din concurs dar cred ca intelegeti cat de frustrant este pentru concurentii care au avut "ghinionul" sa se apuce de ea si sa isi risipeasca timp considerabil pentru a o rezolva.

Nu vreau sa para ca ratingul este scopul activitatii mele pe infoarena, dar de exemplu nu inteleg de ce ati judecat acum situatia diferit de runda 6 de monthly, unde nu l-ati actualizat pentru ca in primele minute au fost niste teste gresite la feedbackul unei probleme.

In rest, sincere felicitari pentru probleme pentru ca au fost foarte reusite.

Eu as vrea sa continui ideea si sa reamintesc echipei Infoarena ca daca pana acum la celelalte concursuri s-au mai strecurat greseli, aici este vorba totusi de cel mai important concurs al acestei comunitati, Algoritmiada, si macar aceasta sa tinda catre 0 greseli. Personal cred, ca aceasta runda ar trebuii sa nu mai conteze de loc la clasamentul pentru Algoritmiada si sa aiba loc alta runda.

[•repp4radu]

Eu personal, nu sunt de acord cu ceea ce propuneti. Intr-adevar, a fost o problema care s-a eliminat, insa a fost eliminata pentru toata lumea, deci nu s-au produs discriminari.

In al doilea rand, ar fi nedrept pentru cei care au obtinut un punctaj ok la celelalte doua probleme. In concurs, conteaza si impartirea timpului intre probleme si chiar daca s-ar putea ca feedback-ul sa va fi indus in eroare, nu va oprea nimeni sa treceti la alta problema.

[•eudanip]

Eu personal, nu sunt de acord cu ceea ce propuneti. Intr-adevar, a fost o problema care s-a eliminat, insa a fost eliminata pentru toata lumea, deci nu s-au produs discriminari.

In al doilea rand, ar fi nedrept pentru cei care au obtinut un punctaj ok la celelalte doua probleme. In concurs, conteaza si impartirea timpului intre probleme si chiar daca s-ar putea ca feedback-ul sa va fi indus in eroare, nu va oprea nimeni sa treceti la alta problema.

Nu e chiar asa. Gandestete ca daca ai fi fost in locul lor, te-ai fi ofticat si tu. Desigur ca strategia de concurs e buna si cateodata trebuie sa mai schimbi problemele dar e o strategie si sa consideri ca problema la care lucrezi e buna. Imagineazati ca primesti o problema pe care esti la fel de sigur ca la problema A+B si nu vrei sa o lasi pana nu iti iese si sa fie defapt problema busita. Sunt de acord cu Mihai Popa (rating-ul sa nu se schimbe) dar nu si cu Murtaza (doar daca era zi de ONI sau lot atunci ar trebui eliminata runda).

[•repp4radu]

Eu personal, nu sunt de acord cu ceea ce propuneti. Intr-adevar, a fost o problema care s-a eliminat, insa a fost eliminata pentru toata lumea, deci nu s-au produs discriminari.

In al doilea rand, ar fi nedrept pentru cei care au obtinut un punctaj ok la celelalte doua probleme. In concurs, conteaza si impartirea timpului intre probleme si chiar daca s-ar putea ca feedback-ul sa va fi indus in eroare, nu va oprea nimeni sa treceti la alta problema.

Nu e chiar asa. Gandestete ca daca ai fi fost in locul lor, te-ai fi ofticat si tu. Desigur ca strategia de concurs e buna si cateodata trebuie sa mai schimbi problemele dar e o strategie si sa consideri ca problema la care lucrezi e buna. Imagineazati ca primesti o problema pe care esti la fel de sigur ca la problema A+B si nu vrei sa o lasi pana nu iti iese si sa fie defapt problema busita. Sunt de acord cu Mihai Popa (rating-ul sa nu se schimbe) dar nu si cu Murtaza (doar daca era zi de ONI sau lot atunci ar trebui eliminata runda).

Trebuie sa recunosc ca imi vine greu sa cred ca timpul alocat problemei de catre unii concurenti a fost atat de insemnat incat sa justifice refacerea/anularea rundei(chiar si la nivel de rating).

A nu se intelege ca nu cred ca s-a pierdut timp cu 2stacks, in conditiile in care si eu am pierdut aprox 2 ore incercand sa o rezolv.

[•Challenge]

Insemnat sau ne insemnat, a fost variabil de la un concurent la altul, in consecinta a facut diferenta (fie ea cat de mica)!

[•Cristy94]

Asta imi aminteste de:

Un Rabin, vestit pentru înţelepciunea sa, este pus în situaţia de a împărţi dreptatea între doi împricinaţi.
Îl ascultă cu atenţie pe primul şi spune: „Ai dreptate".
Îl ascultă şi pe cel de-al doilea, iar răspunsul este identic: „Şi tu ai dreptate".
Aflat de faţă, Iţic îl întreabă, nedumerit, pe rabin: „Păi, cum vine asta, Rabi? Nu se poate să aibă amândoi dreptate!".Iar rabinul cel înţelept îi răspunde: „Şi tu ai dreptate!"

Cred ca cel mai bine ar fi sa nu se afecteze rating-ul la clasele ce au avut aceasta problema, insa runda sa conteze la clasamentul final al Algoritmiadei.

[•vendetta]

Bun. In primul rand suntem subiectivi; fiecare isi urmareste propriul scop. In al doilea rand propunerea cu anularea rundei e exagerata; ca si argument sunt de acord cu ce a zis eudanip anterior. Iar despre rating din cate vad s-a updatat si da as vrea sa ramana cum e ) ( cel putin mie ). Si sunt de acord cu Szasz Radu, mai exact nimeni nu va oprit sa incercati celelalte probleme. Aceleasi conditii le-am avut toti.
Pt Popa Mihai : Defapt cred ca era runda a 4-a. Iar apoi structura concursului Monthly e diferita de Algoritmiada.

[•mihaipopa12]

Trebuie sa recunosc ca imi vine greu sa cred ca timpul alocat problemei de catre unii concurenti a fost atat de insemnat incat sa justifice refacerea/anularea rundei(chiar si la nivel de rating).

A nu se intelege ca nu cred ca s-a pierdut timp cu 2stacks, in conditiile in care si eu am pierdut aprox 2 ore incercand sa o rezolv.

Personal, am petrecut cam 3,5 ore pe 2stacks. Sunt sigur ca nu am fost singurul caruia i-a trecut prin cap ca aceasta va fi o problema accesibila. Am avut senzatia asta pe tot parcursul rundei si mi se pare normal ca am actionat in consecinta.

Nu am spus ca imi doresc sa se refaca runda (stiu ca presupune foarte multa munca si ar fi nedrept pentru cei care au facut bine acum) dar neactualizarea ratingului mi se pare un lucru simbolic care se impune.

Bun. In primul rand suntem subiectivi; fiecare isi urmareste propriul scop. In al doilea rand propunerea cu anularea rundei e exagerata; ca si argument sunt de acord cu ce a zis eudanip anterior. Iar despre rating din cate vad s-a updatat si da as vrea sa ramana cum e ) ( cel putin mie ). Si sunt de acord cu Szasz Radu, mai exact nimeni nu va oprit sa incercati celelalte probleme. Aceleasi conditii le-am avut toti.
Pt Popa Mihai : Defapt cred ca era runda a 4-a. Iar apoi structura concursului Monthly e diferita de Algoritmiada.

Nimeni nu ne-a oprit sa incercam celelalte probleme dar in departajarea concurentilor a intervenit sansa, ceea ce nu mi se pare ok, mai ales in vederea calficarii la finala.
Nu are nicio relevanta structura diferita a concursului Monthly fata de Algoritmiada (ar fi avut doar daca problema ar fi fost corectata/reevaluata/macar anuntata drept gresita in timpul probei).
Din contra, mi se pare mai grava situatia de acum; Algoritmiada are doar 3 sau 4 runde, fata de 12 si, de asemenea, o miza mai mare.

[•klamathix]

Vina ne apartine doar noua. Fiecare poate aborda concursul in maniera in care doreste, rezolvand orice problema doreste. Nu ar trebui sa fie necesar pentru nimeni sa-si adapteze strategia pentru a suplini neajunsurile comisiei. Vom face runda unrated, dar din pacate mai mult de atat nu putem face. Ne cerem scuze din nou.

[•klamathix]

Am dat rewind la rating pentru cei de la clasele 5 - 9 si 11 - 12 .

[•PlayLikeNeverB4]

Rewind infoarena style 

Apropo, si mie mi-a crescut in mod misterios ratingul cu un punct  . Am vazut ca a mai pomenit cineva de asta.

[•klamathix]

Probabil e de la erorile de precizie.

[•crushack]

Eu nu ma prind de ce 2stacks nu se putea face in O(N^2)
ca pe dinamica de la cel mai lung subsir comun (T[ i ][j]) bagai o dinamica gen

d[ i ][j]=nr de moduri de a pune numerele in stive astfel incat sa-ti dea doua stringuri egale cu lungimea T[ i ][j]

d[ i ][j]+= d[i-1][j-1] , daca A[ i ]==B[j]
d[ i ][j]+= d[i ][j-1]    , daca T[ i ][j]==T[ i ][j-1]
d[ i ][j]+= d[i-1][j]    , daca T[ i ][j]==T[i-1][j]

e ca si cum ai parcurge matricea astfel incat sa mergi de nr T[N][N] ori pe diagonala.
De fiecare data cand mergi in dreapta sau in jos simulezi o introducere in stiva.

[•dushmi]

Din cauza acestei fraze:

Un set se considera valid daca pentru orice 2 operatii consecutive din acest set, fie acestea i si i + 1, v(i) ≤ v(i + 1), unde v(i) si v(i + 1) sunt numerele introduse in stive la operatiile respective.

Ce zici tu este fix solutia oficiala intiala, dar ea nu respecta restrictia de mai sus. Adica, iti garanteaza ca in stive sunt in ordine crescatoare, dar nu iti garanteaza si ca daca interclasezi operatiile, ele sunt in ordine crescatoare in continuare.

[•mugurelionut]

Mie mi se pare ca singura dificultate a problemei apare atunci cand aceeasi pozitie trebuie eliminata din ambele siruri (pt ca ai 2 variante de a ordona cele 2 operatii pt pozitia comuna). Altfel, daca din cele 2 siruri s-ar elimina seturi de pozitii distincte, ar fi un mod unic de a le interclasa pt a iesi in ordine crescatoare (si, astfel, raspunsul ar fi egal chiar cu numarul de subsiruri comune de lungime maxima, diferite doar ca seturi de pozitii, ceea ce se poate calcula usor extinzand un pic dinamica standard).

Mai exact, daca exista K pozitii eliminate din sirul 1 comune cu pozitiile eliminate din sirul 2 (pt a obtine dupa eliminare un subsir comun maxim), atunci pt acest subsir comun maxim trebuie adunata la rezultat valoarea 2^K  (pt ca pt fiecare pozitie comuna poti elimina ori mai intai pozitia din primul sir, ori pe cea din al doilea sir, dar in afara de asta, pozitiile pot fi interclasate intr-un singur fel).

Insa nu imi dau seama daca s-ar putea modifica cumva dinamica standard pt subsir comun de lungime maxima pt a "prinde" in solutii cazurile cand aceeasi pozitie i este eliminata din ambele siruri (ea "prinde" fara probleme cazurile cand aceeasi pozitie i este pastrata din ambele siruri, dar noua nu asta ne trebuie).