272 Bridge

[•filipb]

Aici puteţi discuta despre problema Bridge.

[•cos_min]

am nedumerire ... deci folosim:
m[j] numarul de moduri ( modulo 666013 ) de a ajunge in i pasi pe scandura j din pozitia initiala
shi la un moment dat scrie in articol : daca scandura i este lipsa atunci m[j] = 0, daca scandura i este teleportoare incrementam M[i+1][unde[j]] cu m[j] 
nu trebuia scandura j sau nu am inteles eu

[•pauldb]

Ba da, asa e...se mai intampla.

[•filipb]

Mie mi se pare bine cum e formulat in articol, nici macar nu am inteles unde vrea sa zica cos_min ca e gresit...

[•cos_min]

am vrut sa zik k i tine minte pasii . nu scandura . nu ?

[•filipb]

true, greseala de indici Am modificat

[•mocke]

am si eu o nedumerire!??!?!  complexitatea oficiala e O(M+N*K), unde K presupun ca e maximul de pasi din lista de query-uri. Eu aveam o complexitate care ajungea maxim la O(4001*4001) pe fiecare test...si luam TLE la ultimele 6 teste . Bun. Am optimizat in O(M+N*K), memorie dinamica,etc. tot iau TLE la aceleasi teste. Poate cineva sa-mi dea o alta idee de optimizare. Totusi mi se pare cam ciudat ca O(16 mil) nu intra in 1s?! 

[•filipb]

La problema asta trebuie mare atentie cu memoria folosita. Memoria dinamica e , consuma timp la greu. Eu am folosit o singura matrice 4002*4002, si vreo doi vectori suplimentari. In plus, si operatia mod e , incearca sa te gandesti cum sa introduci -. Si mai trebuie avut grija sa fie dinamica inainte ca sa mearga teleportarile mai repede. Cu toate astea, ar trebui sa iei 100 fara probleme.

[•pauldb]

Mocke: Eu nu inteleg o chestie la rezolvarea ta: cum ai redus memoria la dinamica fara sa sortezi? Sau ce intelegi tu prin faptul ca"ai optimizat memoria la dinamica"?

[•Marius]

Mocke: scapa de % si vei obtine 70-80.

[•mocke]

foloseam dinamica inainte dar m-am prins de niste chesti care imi buseau matricea respectiva si am mai si optimizat....am inlocuit modulo cu scadere (e mult mai rapid in cazul acesta) si desi am folosit memorie dinamica a fost ok  !  mersi oricum pt sfaturi guys !

PaulDB:
Mocke: Eu nu inteleg o chestie la rezolvarea ta: cum ai redus memoria la dinamica fara sa sortezi? Sau ce intelegi tu prin faptul ca"ai optimizat memoria la dinamica"?

RE:am optimizat folosind memorie dinamica....nu memoria la dinamica! 

Pt filipb: ai dreptate cu dinamica inainte asa si facusem ... dak faceai dinamica inapoi foloseai mai multa memorie iar complexitatea putea sa ajunga si la n^2*(nr de scanduri teleportatoare) care nu se prea amortiza

[•devilkind]

ideea initiala a problemei a fost de fapt chiar acea dinamica inapoi care cum zici tu iesea n^2*nr de pasi. Si ideea era sa folosesti o lista de adiacenta ptr fiecare scandura (cu scandurile de pe care se poate ajunge pe ea) si astfel ajungem la acelasi n*nr de pasi. Intre timp mi-am dat seama ca o dinamica inainte merge mai repede, insa sursa mea folosind rezolvarea de mai sus a mers in 0.6 .

[•cos_min]

cat va da pt :

7 4
0 3 0 2 3 1 0
4 7
2 1
7 8
3 2
7 6

?

[•devilkind]

0
15
1
6

[•cos_min]

oh greseam la o chestie pe care o citisem gresit ... da totusi iau 90 pcte ... WA pe ultimul test [daca fac cu scadere] si TLE (tot pe testu asta) [daca fac cu %]

[•cristy]

scuze...am o problema aici...sunt ceva cazuri mai speciale?...iau 20 de pct...restu WA...la ce ar trebui sa fiu atent?.. ma chinui la ea ce ceva vreme...si e demoralizant...ca ies toate cazurile mele

[•filipb]

Incearca urmatorul test:

Cod:

6 5
3 0 3 3 1 2
2
5
6
1 1
2 1
2 4000
5 4000
6 4000

Contine niste cazuri particulare pe care poate nu le-ai tratat. Trebuie sa iti dea:

Cod:

1
1
2
0
0

[•cristy]

atata imi da si mie...

[•pauldb]

Incearca testul asta:

8 1
0 0 3 0 1 0 2 0
8
8 5

Pe mine m-a ajutat.

[•devilkind]

dak iei 20 de puncte e posibil sa fie din cauza ca nu ai calculezi modulo 666013

[•cristy]

1. Pt PaulDB: mie mi-a dat 15, cred ca atat trebuie sa dea...
2. Pt devilkind: calculez modulo 666013, pt testul

Cod:

11 1
0 0 0 0 0 0 0 0 0 0 0
11 16

imi da:

Cod:

172253

si...calculez peste tot...modulo...
3. Pt amandoi: ms mult...sper sa gasesc gresala...

[•devilkind]

sunt bune ambele rezultate si 15 si 172253

[•cos_min]

ai grija la : "Numarul de moduri de a ajunge pe o scandura lipsa sau pe o scandura teleportoare care are ca destinatie o scandura lipsa sau subreda este 0" . Eu aici greseam si luam 20 pcte.

[•cristy]

pt cazul:

Cod:

2 6
3 0
2
1 1
1 2
1 3
2 1
2 2
2 3

e bun rezultatul:

Cod:

1
0
0
1
2
2

?

[•cos_min]

ii bine