Parb

[•dushmi]

Aici se pot pune întrebări legate de problema Parb de la Runda Finala a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•scipianus]

Raspunsul cu un singur caracter (pentru un apel Parb(x,x)) este valid?

[•eudanip]

DA

[•raulstoin]

Un sir x, care are o lungime mai mica decat un sir y, si x nu este prefix a lui y, se considera mai mic lexicografic?

[•eudanip]

Am modificat enuntul.

[•veleandu]

Nodul x este stramos al nodului y daca apare mai repede in arbore, nu?

[•raulstoin]

E ceva mai special la testele 4, 7 si 9? Iau TLE orice fac...

[•visanr]

Ce complexitate ai? Eu am luat TLE pe aceleasi teste in concurs, complexitatea parea ok, dar nu era.

[•raulstoin]

N+M in cel mai rau caz... http://www.infoarena.ro/job_detail/960525 Dupa cum se vede, merge ok pt restul testelor

[•visanr]

Esti sigur ca merge in O(N + M) worst case? Ce solutie ai?
Dupa cum se vede, si sursa mea merge bine pe restul testelor, doar ca pe cele bune merge foarte prost.  

[•klamathix]

Daca vedeti teste grupate, ganditi-va ca de regula fiecare test dintr-o grupa e facut sa combata o anumita bulaneala/o solutie ineficienta. In conditiile astea, nu e foarte relevant ca pici putine teste, fiindca puteau fi date toate 10 dupa structura respectiva .

[•visanr]

S-au schimbat testele la aceasta problema in timpul concursului / dupa concurs?
In aceasta poza (este pe facebook, pe pagina infoarena), din cate vad, sunt multe punctaje de 90 la parb...


LE: Mda, au fost schimbate pe 8 iunie.

[•klamathix]

In realitate, nici nu aveam pretentia ca testele initiale sa fie finale . Nu am putut produce teste suficient de bune pana in ziua concursului asa ca am decis sa lasam niste teste dummy, printre care unul rezonabil de mare pentru feedback, iar apoi sa le schimbam. Testul de feedback a ramas acelasi, iar celelalte au fost facute dupa ideile initiale (dar pe care nu am apucat sa le implementam cu succes pana la concurs). Subliniez ca testele n-au fost facute pe baza surselor implementate in concurs, pe care de-altfel nici nu le-am citit.

Erau multe punctaje de 90 fiindca aveam teste de jucarie. Suntem constienti ca a fost o miscare mai neortodoxa, dar din punctul nostru de vedere concurentii n-au fost afectati deloc, iar testele in final au iesit bine. In orice caz, vom incerca sa nu ajungem intr-o asemenea situatie in viitor.

[•visanr]

In realitate, nici nu aveam pretentia ca testele initiale sa fie finale . Nu am putut produce teste suficient de bune pana in ziua concursului asa ca am decis sa lasam niste teste dummy, printre care unul rezonabil de mare pentru feedback, iar apoi sa le schimbam. Testul de feedback a ramas acelasi, iar celelalte au fost facute dupa ideile initiale (dar pe care nu am apucat sa le implementam cu succes pana la concurs). Subliniez ca testele n-au fost facute pe baza surselor implementate in concurs, pe care de-altfel nici nu le-am citit.

Erau multe punctaje de 90 fiindca aveam teste de jucarie. Suntem constienti ca a fost o miscare mai neortodoxa, dar din punctul nostru de vedere concurentii n-au fost afectati deloc, iar testele in final au iesit bine. In orice caz, vom incerca sa nu ajungem intr-o asemenea situatie in viitor.

Ok

[•crushack]

In realitate, nici nu aveam pretentia ca testele initiale sa fie finale . Nu am putut produce teste suficient de bune pana in ziua concursului asa ca am decis sa lasam niste teste dummy, printre care unul rezonabil de mare pentru feedback, iar apoi sa le schimbam. Testul de feedback a ramas acelasi, iar celelalte au fost facute dupa ideile initiale (dar pe care nu am apucat sa le implementam cu succes pana la concurs). Subliniez ca testele n-au fost facute pe baza surselor implementate in concurs, pe care de-altfel nici nu le-am citit.

Erau multe punctaje de 90 fiindca aveam teste de jucarie. Suntem constienti ca a fost o miscare mai neortodoxa, dar din punctul nostru de vedere concurentii n-au fost afectati deloc, iar testele in final au iesit bine. In orice caz, vom incerca sa nu ajungem intr-o asemenea situatie in viitor.

Poi unii membrii ai comisiei, daca nu toti, au aflat de la concurenti solutia care lua 90p. Cum puteti explica ca testele au fost facute in mod obiectiv dupa ce comisia stia deja ce fel de algoritmi aveau concurentii?

Mie tot nu mi se pare ok schimbarea testelor...

[•wefgef]

In realitate, nici nu aveam pretentia ca testele initiale sa fie finale . Nu am putut produce teste suficient de bune pana in ziua concursului asa ca am decis sa lasam niste teste dummy, printre care unul rezonabil de mare pentru feedback, iar apoi sa le schimbam. Testul de feedback a ramas acelasi, iar celelalte au fost facute dupa ideile initiale (dar pe care nu am apucat sa le implementam cu succes pana la concurs). Subliniez ca testele n-au fost facute pe baza surselor implementate in concurs, pe care de-altfel nici nu le-am citit.

Erau multe punctaje de 90 fiindca aveam teste de jucarie. Suntem constienti ca a fost o miscare mai neortodoxa, dar din punctul nostru de vedere concurentii n-au fost afectati deloc, iar testele in final au iesit bine. In orice caz, vom incerca sa nu ajungem intr-o asemenea situatie in viitor.

Poi unii membrii ai comisiei, daca nu toti, au aflat de la concurenti solutia care lua 90p. Cum puteti explica ca testele au fost facute in mod obiectiv dupa ce comisia stia deja ce fel de algoritmi aveau concurentii?

Mie tot nu mi se pare ok schimbarea testelor...

Nu exista o solutie a concurentilor care lua 90 de puncte. Solutiile voastre erau diferite intre ele si in plus, aproape niciuna nu era corecta. Noi am generat testele astfel incat brute-urile noastre, pe care le-am scris inainte de proba, sa obtina punctejele pe care le doream.

Schimbarea testelor nu a avut loc pentru ca au luat unele solutii proaste punctaj mare. Pur si simplu aveam 10 teste generate pseudo-random astfel incat sa putem da drumul la runda. Planul nostru era sa terminam generatorul bun si sa ne testam pe propriile surse, ceea ce s-a si intamplat.

Cum explicam faptul ca am generat teste obiectiv? Uita-te pe clasament.

[•ctlin04]

Care este specificul testelor 2 si 6, iau incorect pe ele, dar nu pot gasi nicidecum teste pe care sa obtin raspuns gresit