049 Barbar

[•Andrei1998]

Poate cineva sa imi spuna ce mai poate insemna SIGSEGV? Caci nu imi pot da seama de ce il primesc pe atat de multe teste.  Nu cred ca ies din memorie, dar cine stie? Sursa este job #847696.

Foarte multe multumiri.

PS: Nici testul 3 nu stiu ce are mai special. Toate testele postate aici merg.

[•deneo]

SIGSEGV primesti atunci cand ai probleme cu memoria. Deobicei e vorba ca ai iesit din limitele unui vector etc.

[•Andrei1998]

Asta deja stiam. Doar ca nu ies din vector. Din acest motiv am postat si numarul sursei.

[•PlayLikeNeverB4]

Iti iese din coada fiindca e posibil sa bagi de mai multe ori aceeasi celula. Problema e ca tu marchezi celula ca vizitata doar cand ai ajuns la ea cu capul si ar trebui sa o marchezi imediat dupa ce o bagi in coada. Gandeste-te ce se intampla daca ai in coada (1,2) si (2,1). De la amandoua vei baga in coada (2,2).

[•Andrei1998]

Multumesc foarte mult lui George Marcus , chiar am invatat ceva din asta. (sa marchez nodul imediat ce a ajuns in coada). Acum insa, ce o avea testul 3 mai special, ca am facut teste mai speciale si merge programul pe ele. In plus oare iau TLE de la citirea caracter cu caracter?
Noua sursa este #847853.

Andrei

[•PlayLikeNeverB4]

Incearca cu citirea din C (fgets).
P.S.: Nu are rost sa pui id-ul sursei fiindca nu ne ajuta cu nimic. Mai bine pui tot linkul de la sursa. Eu personal am intrat pe profilul tau si m-am uitat la ultima problema trimisa.

[•Andrei1998]

O sa incerc. Insa ceea ce chiar ma preocupa este de ce nu merge testul 3?

[•PlayLikeNeverB4]

Un alt lucru ce poate fi imbunatatit este prima parcurgere. Tu faci cate o parcurgere pentru fiecare dragon, insa e mai bine sa faci parcurgerea incepand paralel din toti dragonii (ii bagi in coada). Testul 3 nu stiu de ce il cazi, e un bug. Verifica atent codul.

[•Andrei1998]

Fac mai multe parcurgeri doar ca un dragon faca update si continua parcurgerea numai daca are rost (ar da  pericole mai mici).

[•PlayLikeNeverB4]

Gandeste-te ca ai un dragon la (1,1) si unul la (1000,1000). Faci parcurgerea din primul pe toata harta. Apoi vei face si din al doilea pana la jumatatea hartii. Daca mai ai doi dragoni in celelalte colturi vei mai face inca doua sferturi de harta. Si tot asa

[•sebinechita]

Imi pica testul 3....cu Killed by signal....nu am folosit memorie prea putina ca i-am dat limitele matricei si la 2000 ...nu stiu ce ar putea merge gresit pt ca imi merge pe toate celelalte...90 de puncte ...stie careva ce ar trebui sa modific?

[•vladm97]

Cred ca am o problema cu interpretarea enuntului. In exemplu, daca el tb sa o ia "astfel incat minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim" de ce o ia la dreapta? celula din stanga si de deasupra nu sunt la o dist mai mare?

[•harababurel]

Pentru fiecare drum posibil de la sursa la destinatie, se ia in considerare punctul de pe traseu in care distanta dintre barbar si un dragon oarecare este minima.
Trebuie gasit un drum care maximizeaza distanta asta.

Pentru exemplu, chiar daca la inceput mergi in stanga sau in sus, oricum ai continua traseul pana la destinatie, tot te apropii la cel putin 2 unitati fata de un dragon.

Nu exista niciun drum in care sa fii permanent la o distanta >= 3 fata de orice dragon, deci solutia optima e 2.

[•vladm97]

Gata, am priceput. Dar nu vad cum m-ar ajuta cautarea binara.

[•harababurel]

Presupune prin absurd ca tu cunosti deja solutia ca fiind X, si vrei sa o verifici (adica sa faci o explorare a hartii astfel incat sa nu te apropii niciodata la o distanta mai mica de X, fata de vreun dragon).

Odata ce gasesti o modalitate de a verifica un anumit X si de a afla astfel daca valoarea respectiva poate fi solutie sau nu, tot ce iti ramane de facut e sa *cauti* cel mai mare X care verifica conditia.

Cautarea binara e corecta pentru ca functia f(x) = {1 daca x e solutie, 0 daca x nu e solutie) este monotona.
Cu alte cuvinte, exista un X maxim care poate fi solutie, astfel incat valorele {1, 2, ..., X-1, X} sunt si ele solutii valide (adica exista cel putin un traseu bun de la sursa la destinatie pentru fiecare valoare din lista) si pentru nicio valoare mai mare decat X nu exista niciun traseu.
Practic, distantele minime valide pe care le poti alege se termina brusc.

[•vladm97]

Mersi.

[•PTAdrian64]

Distanta minima din fiecare celula se refera la minima dintre axele de coordonate , sau la distanta dintre cel mai apropiat balaur si celula ?

[•tziplea_stefan]

Am o nelamurire in legatura cu problema aceasta, stau de ceva timp pe ea si unele raspunsuri ale testelor din comentarii chiar nu le inteleg si ma deruteaza si mai tare. Deci, un dragon arunca flacarile doar in sus, jos, dreapta si stanga? Daca da, este suficienta verificarea ca Paftenie sa nu treaca niciodata intr-o celula care este acoperita de foc, pentru a considera traseul valid?

LE: Am rezolvat pana la urma, nu era asa cum credeam initial 

[•Andrei-27]

In articolul cu solutii apare complexitatea O( r*c * lg ( r * c ) ) .
este O( r*c * lg ( r + c ) ) .