014 Secventa

[•fluffy]

Aici puteţi discuta despre problema Secventa.

[•cristy]

La problema asta, datele de test de la aceasta problema au "k"-ul peste 32000?? :lol:

[•cristy]

Scuze pentru repetitia din mesaju de mai sus da am fost neatent(oricum romana nu este printre punctele mele forte)

[•dinu]

Am o rezolvare in o(NlogK) care are 2 teste cu timp limita depasit.
Folosesc un algoritm cu min-heap-uri. Ce sa fac?
Pot sa scot o solutie in o(n), si daca da, are cineva o idee de postat?

[•domino]

Am o rezolvare in o(NlogK) care are 2 teste cu timp limita depasit.
Folosesc un algoritm cu min-heap-uri. Ce sa fac?
Pot sa scot o solutie in o(n), si daca da, are cineva o idee de postat?

Poti sa scoti o solutie O(N) (care este necesara pentru punctaj maxim). Daca pornesti de la solutia cu heap-uri, se poate observa ca odata ce inserezi un element in heap, o parte din elemente care existau inainte nu te mai ajuta cu nimic, deci poti inlocui heap-ul cu o alta structura, si cu un pic de analiza amortizata poti sa obtii un algoritm O(N). Acelasi truc a fost anul acesta la baraj la problema "Trans".  

[•dinu]

Am fost si eu la baraj si in prima zi am facut la celelalte 2 probleme.
La trans, singurul lucru care l-am scis in cod a fost un banc cu Bula
la prezicator. Cine vrea sa-l auda, sa-mi zica. E super. Chiar, despre ce structura vorbeai ?

[•domino]

Am fost si eu la baraj si in prima zi am facut la celelalte 2 probleme.
La trans, singurul lucru care l-am scis in cod a fost un banc cu Bula
la prezicator. Cine vrea sa-l auda, sa-mi zica. E super. Chiar, despre ce structura vorbeai ?

Structura este o stiva.   Pentru mai multe detalii, uita-te pe solutia oficiala de la "trans". Intre timp, zi bancu!

[•vladcyb1]

Am incercat sa fac si eu problema asta dar imi iese din timp pe ultimile 3 teste. Am rezolvat-o cu stiva de la trans. Am bagat in stiva primele k elemente din sir, le-am sortat qsort si dupa aia am aplicat ideea cu stiva.
 Unde as putea sa optimizez?    

[•domino]

Am incercat sa fac si eu problema asta dar imi iese din timp pe ultimile 3 teste. Am rezolvat-o cu stiva de la trans. Am bagat in stiva primele k elemente din sir, le-am sortat qsort si dupa aia am aplicat ideea cu stiva.
 Unde as putea sa optimizez?    

Pai dupa ce bagi primele k elemente in stiva nu faci nici o sortare..daca le inserezi cum trebuie , stiva trebuie sa ramana sortata in orice moment.

[•vladcyb1]

Nu cred ca m-ai inteles.
 La pasul unu am introdus primele k elemente si le-am sortat.
 Mai departe pentru restul elementelor am aplicat kestia de la stiva. Am luat-o de la coada si am eliminat toate elementele mai mari ca noul numar. (am inserat si binar si tot iese din timp). Minimul l-am scos din capul stivei.

[andreit1]

Daca sortezi la pasul unu stiva( qsort, heap-sort...) ai complexitatea O(N*logN) care nu este suficienta pentru a lua 100p. Incearca sa introduci elementele astfel incat stiva sa fie sortata de la inceput.

[•vladcyb1]

Le-am introdus in stiva cu countsort-ul, dar am pus timer pe fiecare procedure in parte si citirea imi ia 0.33 s (pe PIV 2,4Ghz) pt n=500.000.
 Tot TLE iau. Se poate sa fie de la Pascal?

[andreit1]

Eu am luat 100 in Pascal folosind countsort in tot programul. M-am chinuit mult sa trec de la 90 la 100, dar se poate.

[•vladcyb1]

Cum ai facut citirea? Pur si simplu citirea imi mananca tot timpul. Restul programului merge O(n). Exista alta modalitate de citire in afara de read ? Yo iau 70 de puncte,nu 90.    

[andreit1]

Nu cred ca exista alta modalitate mai rapida de a citi decat read. Eu asa luasem 100. Ciudat e ca acum iau din nou 90 pe sursa aia

[•Dorin]

imi da cineva un test in care pf - pi >= k
pf = pozitzia finala
pi = pozitzia intitiala

[andreit1]

Ce rost ar avea?

[•Dorin]

pai as vrea sa imi verifi problema pe testul acela
sau daca nu un test oarecare shi rezultatul  

[andreit1]

Poate m-am exprimat prost... Tinand cont de conditiile din problema ce rost ar avea sa luam o secventa de lungime mai mare de k?
Cat despre teste si rezultate se pot face cu un BF in O(N^2)

[cristi8]

imi da cineva un test in care pf - pi >= k
pf = pozitzia finala
pi = pozitzia intitiala

..pai nu prea are cum, ca iti cere "pf" minim (in caz de egalitate la poz. initiala)
..si daca solutia ta ar fi cu pf - pi + 1 > k, atunci ai putea sa micsorezi pf astfel incat pf - pi + 1 = k, si baza nu are cum sa scada (nu introduci elemente care sunt mai mici decat baza deja stabilita (defapt nu introduci elemente deloc))

[•Dorin]

m-am gandit shi io la asta da am vrut sa ma asigur fara sa inttreb direct  

[•Dorin]

nu va suparati ca intreb dar scrie la inceputul problemei timpul minim de executie este de 18 sec. eu iau pe un test 27 sec. shi nu da timp depasit pe cand la un test cu 31 sec. am luat TLE

deci timpul de executie minim care este in cele din urma

[•vladcyb1]

Cod:

raport evaluator

ATENTIE! Timpii de executie prezentati aici sunt orientativi! Evaluatorul foloseste un alt timer (mult mai exact) pentru a cronometra sursele compilate. Timpii reali pe configuratia curenta difera in medie cu ~0.015s fata de cei raportati aici. In plus, diferenta de timp nu este constanta pe toate testele. Conform timpilor exprimati aici este chiar posibil ca un test sa depaseasca timpul admis si sa obtina puncte in timp ce alt test ce a rulat mai repede sa obtina TLE. 

Timpul de executie minim al problemei este 0.18 secunde cum scrie in enunt !

[•Dorin]

asta am citit si eu dar de unde pana unde

0.31 - 0.015 ~ 0,18

[•Dorin]

si am uitat...
cu prima rezolvare am luat puncte pe un test cu timpul de executie 0.28
si pe a doua rezolvare cu timpul de executie 0.20 am luat TLE