310 Secventa 5

[•DITzoneC]

Aici puteţi discuta despre problema Secventa 5.

[•bigsarpe]

 exista sursa de 100 in pascal?

[•devilkind]

imi poate spune si mie cineva cat da pe testu

Cod:

20 5 15
10
11
8
7
7
20
11
9
9
6
10
8
11
20
9
7
5
5
11
10

mie imi da 123 atat cu solutia in n^2 cat si cu solutia in o(n). Ciudat insa ca pe infoarena amandoua iau 0 puncte. Si toate testele care le-am dat eu au mers (alea care le-am putut testa pe foaie).
PS: sper ca putem folosi map pe infoarena (chiar daca tre sa fac pana la urma hashingu de mana ca sa iau 100).

[•domino]

Ai avut grija sa citesti numerele pe unsigned?

[•devilkind]

 
damn it asta era, ms mircea akuma iau 60, cu TLE pe restu (probabil din cauza ca am le-am long long pe toate ptr a rezolva situatia mai repede si din cauza ca folosesc map).

[•filipb]

Tipul long long e de 4 ori mai incet decat int, asa ca incearca cu unsigned.

[•devilkind]

si cu unsigned long int (formatul la citire am inteles ca e %lu) iau tot 60. Sa vad ce se intampla dupa ce implementez hashingu la mana, ptr ca pe map complexitatea e tot N log N.

[later edit] : am luat 90 cu hashingu de mana. ce functie de hashing ati folosit ptr 100??

[•astronomy]

Aloci static tabela de hash? Mie mi-a mers cu cheia in jur de 200.000. (Poti folosi pentru mai multa eficienta 2 tabele de hash)

[•devilkind]

nu mai conteaza am luat 100 inlocuind instructiunea :

Cod:

for (i=1;i<=n;i++)
     v[i]=0;

cu

Cod:

memset(v,0,sizeof(v));

si a intrat de 100. Hashingu il aloc dinamic si folosesc constanta 666013 (am eu o placere ptr numaru asta )

Multumesc tuturor ptr ajutor.

[•Tabara]

constanta 666013 (am eu o placere ptr numaru asta )

Iti mai spun eu vreo 10 oameni care au pasiune pentru numarul asta 

 

[•mocke]

am o nelamurire: de ce merge mai repede scanf("%s", s) decat scanf("%d", &d) ??
pt trecerea de la 80 (in caz ca faci hash iar ultimele 2 teste iau cam ~1.530 ms) la 100 am parsat citirea dar nu am folosit gets() pt ca luam WA pe ult 2 teste (nush de ce??  ) si am folosit scanf("%s", s) , iar spre uimirea mea a intrat in timp! ceva opinii?   

[•devilkind]

la problema asta citirea dureaza 1.3-1.4 secunde . Ptr ca un algoritm de complexitate o(n) ptr n - 1 milion merge cam in 0.1 hai sa zicem 0.2. dar tot mi se pare cam mult 1.3 ptr a citi 1 milion de numere :-/

[•wefgef]

cum anume citesti?

[•devilkind]

scanf/printf dar oricum limita de timp e de 1.5 secunde si din cate am vazut in monitorul de evaluare nu sunt singurul care s-a chinuit sa incadreze 1 milion de operatii in acest timp.

[•wefgef]

Incearca sa parsezi citirea, s-ar putea sa mearga mai bine.

[•devilkind]

am incercat sa citesc cu fgets dar luam WA pe niste teste nu inteleg de ce. Ce intelegi prin parsarea citirii - citirea linie cu linie?? dak asta e atunci diferenta nu cred ca e asa mare ptr ca numerele sunt date cate unul pe linie. deci tre sa citesti 1 milion de stringuri si tot cam pe acolo iesi cred. sper sa nu ma insel

[•astronomy]

Se simte diferenta chiar daca citesti linie cu linie folosind fgets.

[•Marius]

Sau citesti totul intr-un sir de caractere si extragi datele din sir. Merge simtitor mai repede pe site-uri ca www.spoj.pl dar nu si pe infoarena. La secv5 am castigat 0.3 s cu parsarea asta.

[•bogdan2412]

0.3 s e foarte mult de fapt. Probleme gen color nu prea se pot face fara parsarea citirii. La asta se poate lua 100 puncte cu putin noroc fara sa parsezi citirea..

[•an_drey_curent]

Imi poate da cineva o indicatie pentru 100 la problema aceasta? Iau 70.

Determin numarul de secvente care au cel mult U,respectiv L-1 elemente distincte. Folosesc un hash de pairs in care memorez numarul,respectiv numarul lui de aparitii in secventa actuala. Actualizez de fiecare data cand modific secventa numarul de aparitii. Parsez citirea... ce as mai putea face?

[•pauldb]

Am facut accesul la sursele de la problema asta liber. Si pe mine m-a frustrat o gramada si am luat 100 abia dupa ce am intrat in echipa si m-am uitat la altii cum optimizeaza. Presupun ca e ceva de invatat aici...

[•an_drey_curent]

  

[•scipianus]

Am trimis destul de multe surse (http://infoarena.ro/monitor?task=secv5&user=scipianus) cu mai toate optimizarile la care m-am putut gandi (ba cu normalizare cu sortare,ba cu hash,ba cu map) si mereu ia cel mult 80pct cu TLE. Ce mai pot optimiza? Vad ca ultima sursa de 100pct e prin august deci ar trebui ca inca sa se mai poata lua 100pct pe limita actuala,desi n-ar strica sa fie marita putin...

[•pauldb]

Am crescut limita de timp pentru ca sursa mea de 100 nu intra in timp.

Ca sa iau o 100 de puncte eu am folosit un hash de mana mai dubios. Am adaugat de la inceput toate elementele in hash si apoi cresteam/decrementam nr. de aparitii fara sa mai fac operatii de inserare sau stergere.

[•claudiumihail]

Salut,

La problema asta am trimis la surse de mi s-a acrit, cu toate optimziarile la care m-am putut gandi:

- Algoritm O(n) (varianta cu determinat subsecventele de lungime L-1 si U) - bifat
- Citire parsata - bifat
- Hash de mana care e vizibil mult mai bun decat unoprdered_map/hash_map etc - bifat (desi sunt gata sa accept ca aici e posibil sa fie buba)

Recunosc ca deja a devenit extrem de frustranta problema asta. Am vazut ca multa lume s-a tot chinuit sa treaca de 80pct. Am vazut de asemenea ca s-a mentionat ca accesul la surse era la un moment dat liber. Daca nu mai e cazul, e dispus cineva sa-mi dea un hint despre cum se poate face problema asta de 100? Chiar am ajuns intr-un punct mort si as fi extrem de recunoscator pentru putin ajutor.

Claudiu