272 Bridge

[•lucian666]

 :Dsalutare.sunt nou in programarea dinamica
In legatura cu problema aceasta.Mi-am dat seama de recurenta ,dar cu ce ar trebui sa initializez matricea la inceput:? adica pt scandurile de tip 0,1,3 sa pun 1?
intreb asta deoarece daca nu pun nimic in matrice la inceput ,dupa ce fac dinamica matricea are doar 0 in ea(si e normal neavand nici o valoare de inceput);
Multumesc Anticipat!!!

[•valentina506]

Tot timpul in casuta 1 1 vei avea valoarea 1 deoarece poti ajunge pe prima scandura intrun singur mod, pasind pe ea din afara podului. Trebuie sa verifici si daca poti sari pe scandura 2.

[•tzipleatud]

Nu reusesc sa trec de 90 de puncte, iau TLE pe ultimul test. Se mai poate optimiza ceva sau ar trebui marita limita de timp? Si ar putea cineva sa imi explice de ce e gresita dinamica "inapoi"? Multumesc anticipat!

[•klamathix]

Intr-adevar, nu avea nimeni 100 de cand s-a schimbat evalul. Am marit la 0.35 si ai 100.
Off-topic: Daca tot ti-am vazut avatarul, ai idee cand se lanseaza The Dark Knight Rises la noi? ) Vorba era ca pe 20.

[•Steve]

Am vazut ca doar 2 persoane au luat AC la problema asta pe noul eval, chiar si cu schimbarea limitei. No offence, dar mi se pare destul de aiurea sa fie nevoie de parsare pentru suta. Am optimizat codul de dinamica, parsare pentru vectorul de scanduri si iau in continuare TLE pe T10.

[•ctlin04]

Nu trebuie parsare pentru a lua 100, eu am luat 308 ms, fara parsare, chiar folosind % in loc de -

[•Steve]

Hmm...inseamna ca algoritmul meu e retardat...
Am facut o dinamica de precalculare de 4000 x N (de sus in jos), apoi raspund pe query in O(1). Not sure ce e gresit.

[•lucian666]

Hmm...inseamna ca algoritmul meu e retardat...
Am facut o dinamica de precalculare de 4000 x N (de sus in jos), apoi raspund pe query in O(1). Not sure ce e gresit.

explica cum ai facut dinamica... :Dai verificat daca poti sari pe a 2 scandura?

[•Steve]

Am schimbat algoritmul de dinamica din K * N in N * K si a intrat, mai chinuita, ce-i drept
Mersi oricum!

[•SebiSebi]

Care sunt cele 3 modalitati pentru al doilea query din exemplu? Multumesc!

[•tzipleatud]

Salut!

Daca nu ma insel posibilitatile sunt:

1) pasesc pe 1, stationez, pasesc pe 2
2) pasesc pe 1, pasesc pe 2, stationez
3) sar pe 2, stationez, stationez

Bafta!

[•stardust]

Mi se pare limita destul de stransa la problema asta. Iau 90 cu TLE pe ultimul. E sigur din cauza operatiei modulo pentru ca daca o elimin imi intra in timp. Totusi am vazut ca sunt multi cu 100 dar am incercat si prin scaderi si sa parsez si tot nu imi iese. Vreun sfat cum as putea sa trec ultimul test ?

P.S. Stie cineva cu ce problema de la un fost OJI se aseamna bridge ?

[•SebiSebi]

Uite aici problema de la OJI : http://infoarena.ro/problema/scara3

[•stardust]

Nu mi se par a avea ceva in comun )

[•SebiSebi]

Ambele se rezolva folosind metoda programarii dinamice inainte.  

[•stardust]

Puteti totusi sa va uitati peste problema asta. Stiu ca s-a luat 100 dar eu nu reusesc nicicum sa trec de 90. Chiar cred ca ar trebui marita putin limita

[•Steve]

Puteti totusi sa va uitati peste problema asta. Stiu ca s-a luat 100 dar eu nu reusesc nicicum sa trec de 90. Chiar cred ca ar trebui marita putin limita

N-ar strica...Si eu m-am chinuit un pic. Incearca sa inversezi ordinea forurilor, sa faci dinamica invers, mie numai asa mi-a intrat.

[•klamathix]

Puteti folosi O(n) memorie.

[•Detrol2k]

http://www.infoarena.ro/job_detail/999245?action=view-source

Se poate uita cineva peste sursa mea, care a facut aceasta problema? Desi am avut grija sa initializez matricea pe pozitia M[1][1] cu 1 si la fel pentru scandura 2 (daca se poate) M[1][2] = 1, imi da 0 0 0 la testul dat in exemplu.

[•SebiSebi]

Fa un debug È™i vezi unde e problema. E mult mai folositor pentru tine sa faci asta. 

[•Deaconu_Andrei]

Atunci de ce ai submitat la problema asta ? Daca tu nu ai inteles nici enuntul ?  

L.E. Cosmin Rusu de ce ti-ai sters commentul imediat dupa postul meu ? Poate cineva te putea ajuta . Eu doar am pus o intrebare , nu am rezolvat problema , eram si eu curios .

[•DorelBarbu]

Are cineva vreo idee care m-ar putea sa trec si eu de 30 de puncte? Am WA pe al 4-lea test si TLE pe restul. De TLE-uri voi incerca sa rezolv cu unele metode specificate pe aici. Dar acel WA ce poate fi? Toate testele pe care le-am gasit in comentarii au dat raspunsurile corecte. Am avut grija sa calculez si modulo 66013. Putin ajutor, va rog? 

[•Smit]

Pentru testul din exemplu:
5 3
0 0 3 1 2
4
4 4
2 3
3 2
care este raspunsul pentru intrebarile:
3 1
3 3

[•hasmasandragos]

pentru

bridge.in

Cod:

5 2
0 0 3 1 2
4
3 1
3 3

o sa iti afiseze
bridge.out

Cod:

0
0

Gandeste-te daca este posibil ca Fat-Frumos sa ajunga si sa ramana pe o scandura teleportatoare.