Pagini: 1 2 3 [4]   În jos
  Imprimă  
Ajutor Subiect: Algoritmiada 2013, Runda 2  (Citit de 24522 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #75 : Ianuarie 22, 2013, 11:07:05 »

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.  Think
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #76 : Ianuarie 22, 2013, 11:35:28 »

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.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #77 : Ianuarie 22, 2013, 14:55:40 »

Pana la urma, cu 2stacks ce faceti ?
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #78 : Ianuarie 22, 2013, 15:11:01 »

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.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #79 : Ianuarie 22, 2013, 15:16:25 »

El intreba daca se refac testele si se pune problema in arhiva  Smile
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #80 : Ianuarie 22, 2013, 15:16:33 »

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

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #81 : Ianuarie 22, 2013, 15:59:26 »

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.

Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #82 : Ianuarie 22, 2013, 16:57:35 »

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
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #83 : Ianuarie 22, 2013, 17:29:59 »

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.
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #84 : Ianuarie 22, 2013, 17:55:09 »

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.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #85 : Ianuarie 22, 2013, 18:46:20 »

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).
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #86 : Ianuarie 22, 2013, 19:06:09 »

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.
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #87 : Ianuarie 22, 2013, 19:13:59 »

Insemnat sau ne insemnat, a fost variabil de la un concurent la altul, in consecinta a facut diferenta (fie ea cat de mica)!
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #88 : Ianuarie 22, 2013, 20:36:21 »

Asta imi aminteste de:

Citat
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.
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #89 : Ianuarie 22, 2013, 21:14:43 »

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 Smile) ( 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.
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #90 : Ianuarie 22, 2013, 22:22:19 »

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 Smile) ( 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.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #91 : Ianuarie 22, 2013, 22:40:21 »

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.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #92 : Ianuarie 23, 2013, 00:00:36 »

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

Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #93 : Ianuarie 23, 2013, 12:54:07 »

Rewind infoarena style  Very Happy

Apropo, si mie mi-a crescut in mod misterios ratingul cu un punct  Huh. Am vazut ca a mai pomenit cineva de asta.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #94 : Ianuarie 23, 2013, 19:37:10 »

Probabil e de la erorile de precizie.
Memorat
crushack
De-al casei
***

Karma: 23
Deconectat Deconectat

Mesaje: 108



Vezi Profilul
« Răspunde #95 : Ianuarie 23, 2013, 19:48:58 »

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.
Memorat
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« Răspunde #96 : Ianuarie 24, 2013, 01:05:48 »

Din cauza acestei fraze:
Citat
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.

Memorat
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #97 : Ianuarie 28, 2013, 03:25:15 »

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).
Memorat
Pagini: 1 2 3 [4]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines