869 Reinvent

[•DITzoneC]

Aici puteţi discuta despre problema Reinvent.

[•Jordica]

Are cineva un algoritm eficient pentru aceasta problema. Eu am rezolvat-o,dar cu un algoritm greoi care scoate doar 30 de puncte.algoritmul meu ia practica fiecare nod din cartier, face un BF si verifica daca nod ul accesat recent este sau nu din cartier.daca este, atunci ii determina distanta si se opreste.apoi ia celalt nod din cartier s.a.m.d.Are cineva o rezolvare mai isteata?nu ca ar fi greu sa o depaseasca pe a mea

[•stocarul]

Păi faci tot un BellmanFord, doar că inițial pui în coadă toate nodurile din cartier.
Apoi, pentru fiecare nod, vei calcula distanța minimă față de cele mai apropiate două noduri din cartier.
Ca să afli soluția minimă, treci pe la fiecare nod, și vezi suma distanțelor către cele mai apropiate două noduri din cartier (cele calculate cu BF-ul).

[•chibicitiberiu]

O idee mai isteata

Pui in coada toate casele din cartier, si te opresti cand se intersecteaza drumurile... distanta va fi drumul pana la nodul de la intersectie dintr-o directie + distanta din cealalta directie.

Am luat 100 pe solutia asta.

[•darkseeker]

Ar trebui marita limita de timp la aceasta problema . Am trimis o sursa in complexitate O(N) si ia 60 de puncte .

[•lucian666]

ar trebui un pic marita limita de timp aceasta sursa am trimis-o si pe campion si am luat 100:D...lucru foarte interesant ,in urma cu 1 luna am trimis sursa pe infoarena si am luat 90 si acum cu aceeasi sursa iau 60 pct .aveti idee ce s-a intamplat?

[•tzipleatud]

Incearca sa parsezi citirea. Eu doar asa am reusit sa iau 100, si peste cate surse de 100 p m-am uitat, toti au parsat citirea. Bafta!

[•soriyn]

Eu n-am parsat citirea dar ca sa sar de la 90 la 100 a fost nevoie sa fac coada "de mana".

[•lucian666]

Eu n-am parsat citirea dar ca sa sar de la 90 la 100 a fost nevoie sa fac coada "de mana".

am facut coada de mana ....tot 60 pct

Incearca sa parsezi citirea. Eu doar asa am reusit sa iau 100, si peste cate surse de 100 p m-am uitat, toti au parsat citirea. Bafta!

care este faza cu parsatul citirii?imi poate da cineva un exemplu
Multumesc!!!

[•SebiSebi]

Pai in loc sa citesti numar cu numar citesti blocuri de caractere folosind functia fread.
Mai multe detalii aici : http://infoarena.ro/parsarea-numerelor

[•klamathix]

Am marit limita. Inainte sa parsati, anuntati va rog pe forum daca aveti motive bune sa credeti ca limita e prea mica  . Noi nu avem nicio intentie sa diferentiem sursele cu parsare de celelalte. 

[•thesilverhand13]

Poate ca ma trezesc cam tarziu,dar eu unul am luat 100 pe ea cu vechea limita de timp si fara citire parsata....

[•Iustin_Bulimar]

Testele nu acoperă un caz, dacă exista un drum direct intre doua sate dar primele băgate în coada de intersectează înainte de a ajunge la ele, atunci rezolvarea pe care au aplicat-o majoritatea va afisa 2 în loc de 1 dar ia tot 100 de puncte

[•mouse_wireless]

O idee "interesanta" pt aceasta problema.

Imparti nodurile de interes random in doua multimi A si B. Faci un BFS pornind simultan din toate nodurile din A iar raspunsul furnizat este cel distanta cea mai scurta catre un nod din B.

Hai sa analizam un pic rezolvarea aceasta. Daca nodurile care dau distanta optima sunt x si y, atunci daca la imparteala noastra random nodurile x si y sunt in multimi diferite, rezultatul furnizat de solutia noastra este chiar raspunsul la problema. Probabilitatea ca x si y sa fie in multimi diferite este evident 1/2. Asadar, algoritmul nostru are probabilitate de esec de 1/2. Cu alte cuvinte, daca repetam algoritmul de P ori, probabilitatea de esec este (1/2)^P. Ca punct de reper, asta inseamna de exemplu ca pentru P = 10, algoritmul esueaza doar o data din 1024 de incercari.

Cum pe infoarena sunt ~10 teste, P=4 sau P=5 ar trebui sa asigure 100 de puncte in majoritatea cazurilor. Eu am trimis cu P=7 to make sure si a intrat
Complexitatea este evident O(P * (M + N)) pentru ca realizam P BFS-uri, dar trebuie tinut cont ca constanta acestui algoritm este in general mai mica decat o rezolvare "normala", asa ca in practica acest algoritm scoate timpi comparabili cu rezolvarea optima.