037 Atac

[•fluffy]

Aici puteţi discuta despre problema Atac.

[•greco]

...

[•gogu]

Pentru cei in pascal:
Cred ca am trimis de peste 10 ori sursa si de fiecare data lua 0 p. Si era ciudat, fiindca la mine mergea pe orice test ca si un brute force care lua 40 p.
Pana la urma am setat un vector care era declarat array[1..max] sa fie
array[0..max] si am luat 100.
In windows merge, insa in linux face figuri, asa ca aveti grija la oni, daca lucrati in free pascal de windows sa nu aveti neplaceri dupa

[•filipb]

Si eu am luat 0 la asta(WA la toate).. sunt de abia la prima postare si am cam postat-o pe NV (am dat doar testul din exemplu si inca un test al meu tricky... ). Pentru doua noduri aflam LCA in logN, si apoi pt. fiecare din cele 2 lanturi (de la X la LCA si de la Y la LCA) aflam tot in logN care este minimul pe lantul respectiv cu un algoritm gen cel de la "stramosi", cu intoarcere la descendenti cu puteri de 2. Deci in total pe query imi dadea in final logN ( cu o constanta maricica, e adevarat ).
  Pe langa WA, la testul 10 imi da TLE! Exista si un algoritm mai simplu pt. problema asta?

[•silviug]

Solutia mea e cea descrisa de tine. Acum s-ar putea sa fie diferente la implementare (de exemplu poti face LCA in O(1), etc). Stiu ca am pus limita relativ larga (cred ca sursa mea merge in jumatate din timp) deci, in mod normal, nu ar trebui sa fie probleme cu o sursa relativ ingrijit implementata.

Incearca sa o faci sa mearga si apoi mai bagi mici optimizari.

Spor!

Silviu

[•filipb]

Am o nelamurire la problema asta: noi trebuie sa afisam "numarul minim pentru... ultimele P perechi ". Primul numar afisat va fi cel pt. cea de a (M-P+1)-a pereche sau pentru cea de a M-a pereche?
  Adica rasp. pt. perechi se afiseaza in ordinea: (M-P+1), (M-P+2).. M, sau in ordinea M, M-1... (M-P+1) ( incepand cu ultima pereche)?

  bubbleSORT

[•cyron]

poate ca sunt eu batut in cap...dar    exemplu din felu in care am inteles eu problema nu e corect:-/
x=6;y=7;a,b,c,d=1
7-5-1-2-3
...|.....|
...6....4
drum intr 6..7 cica e 6..5+5..7=2+3 nuh?
x:=(6+7)mod 7 +1=7 nuh?
y:=(7+5)mod 7 +1=6 nuh?
drum intre 7..6 acelsi
x:=(7+6)mod 7+1=7 nuh?
y:=(6+5)mod 7+1=5 nuh? =>tre scris 5
drum  intre7..5=2             =>tre scris 2


deci unde nu am inteles bine?

[VladS]

Pentru a izola nodurile 7 si 6 costul este 2( blochezi muchia dintre 5 si 7), nu 5.

[•cyron]

ah..deci cum ar veni muchia minima de pe drumu ala? hmm ... tre sa rescriu sursa  :cry:  

[•sarabogdan]

Cum pot sa calculez muchia de cost minim de pe un lant in timp logaritmic ? Need some help pls !!

[u-92]

folosind ideea de la stramosi, de altfel este si un post mai sus in care este mentionata chestia asta

[•sakka]

            Imi da si mie cineva un test mai smecher.Habar n-am de ce nu iese.

[•Marker]

Se poate raspunde cumva in O(1)? 

[•theprdv]

ori este gresit enuntul ori gresesc eu : in testul din enunt trebuia ca pe linia 5 V-ul sa fie 1 (costul de la 1 la 5 sa fie 1) ca sa dea acele rezultate