|
Titlul: 291 Roy-Floyd Scris de: ditzone din Octombrie 15, 2006, 21:38:57 Aici puteţi discuta despre problema Roy-Floyd (http://infoarena.ro/problema/rf).
Titlul: Raspuns: 291 Roy-Floyd Scris de: Rus Cristian din Octombrie 16, 2006, 21:09:29 la problema roy-floyd
1. a ramas limita de 1 secunda, pe cand in concurs era 0.4 secunde 2. cred ca nu am inteles bine problema(desi e una arhicunoscuta): am v[j] dist minima intre i si j d[j] numarul maxim de drumuri intre i si j am inlocuit v[j] si d[j] daca: dist gasita e mai mica decat cea curenta intre i si j sau daca distantele sunt egale si d[k]+d[k][j]>d[j] ce nu e bine? am 15 pct si restu WA... Titlul: Raspuns: 291 Roy-Floyd Scris de: Toma Radu din Octombrie 16, 2006, 21:13:18 pai...d(i)(j) trebuie sa reprezinte numarul maxim de arce ce le poate avea un drum intre i si j...
Titlul: Raspuns: 291 Roy-Floyd Scris de: Rus Cristian din Octombrie 16, 2006, 21:43:08 scuze de exprimare, d[j] reprezinta numarul maxim de arce intre i si j
Titlul: Raspuns: 291 Roy-Floyd Scris de: Bondane Cosmin din Octombrie 16, 2006, 21:51:25 uite cum am facut eu :
1.daca gasesc un drum minim intre i si j, actualizez si nr maxim de arce intre i si j 2.daca gasesc un drum egal cu cel minim intre i si j , actualizez si nr maxim de arce intre i si j (daca este nevoie) sper ca se intelege ! spor :P Titlul: Raspuns: 291 Roy-Floyd Scris de: Rus Cristian din Octombrie 16, 2006, 22:30:51 asa am facut si eu ](*,)
Titlul: Raspuns: 291 Roy-Floyd Scris de: Bondane Cosmin din Octombrie 17, 2006, 16:27:54 ai initializat la inceput matr care tine minte nr maxim de arcuri intre i si j ??
Titlul: Raspuns: 291 Roy-Floyd Scris de: Rus Cristian din Octombrie 17, 2006, 17:49:03 da, am initializat matricea de drumuri cu d[j]=1 in afara de diagonala principala
Titlul: Răspuns: 291 Roy-Floyd Scris de: Pandia Gheorghe din Aprilie 01, 2007, 00:13:31 Ceva cu siguranta nu e in regula, am scris acelasi algoritm si in pascal si in C si tot iau maxim 15 puncte, mai e oare o conditie? A facut-o cineva de 100 sa ma lumineze si pe mine ?
am facut roy-floyd si pentru suma a[i,k] + a[k,j] = a[i,j] verific daca b[i,k] + b[k,j] > b[i,j] sa actualizez si matricea cu numarul maxim de drumuri... In rest primesc "Incorrect" Someone pls help... LE: Am sa va rog sa ma scuzati ca pun itrebari la probleme asa vechi despre care nu "a mai adus nimeni vorba" de luni bune. Sunt relativ nou pe site si incerc sa rezolv orice problema imi iese in cale. ( Am zis asta pentru ca citeam topicul de Xor Max unde suntem indemnati sa ne uitam la articole la solutie... numai ca era la articole cu muuult timp in urma - daca mai sunt pe undeva solutiile sau macar hint-uri si pentru problemele mai vechi va rog sa-mi dati si mie acces :sad: daca e ok. Multumesc ) Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 01, 2007, 07:15:35 Problema asta a fost propusa la concursul "Happy Coding 2006", din cate imi aduc aminte, deci nu foarte demult... Eu cand am implementat-o greseam ordinea for-urilor, in loc de (k,i,j) pusesem (i,j,k)... verifica sa nu fi facut si tu la fel...
Titlul: Răspuns: 291 Roy-Floyd Scris de: Sebastian Crisan din Aprilie 01, 2007, 10:51:45 Ce complexitate are algoritmul?
Cu O (n3) imi da TLE pe 50% din teste. Titlul: Răspuns: 291 Roy-Floyd Scris de: Cezar Mocan din Aprilie 01, 2007, 11:17:47 Ciudat... eu am luat 100 cu O(n^3) aplicand Dijkstra (fara heap) pe fiecare nod...
Titlul: Răspuns: 291 Roy-Floyd Scris de: Bondane Cosmin din Aprilie 01, 2007, 11:34:37 Citat Cu O (n3) imi da TLE pe 50% din teste. Intra fara probleme. Vezi sa nu intri pe undeva in ciclu' sau nu stiu dc nu iti intra in timp. Titlul: Răspuns: 291 Roy-Floyd Scris de: Sebastian Crisan din Aprilie 01, 2007, 11:52:50 Cod: void Roy_Floyd () Asa am facut (+citire +afisare). spuneti-mi pls care e problema... :-k Titlul: Răspuns: 291 Roy-Floyd Scris de: Barsan Paul din Aprilie 01, 2007, 12:07:42 nu inteleg de ce folosesti 2 matrice de costuri, ideea algoritmului roy floyd este ca daca poti mari( micsora) valoarea drumului de la i la j cu nodul intermediar k. Algoritmul il gasesti in foarte multe carti , se studiaza in clasa a XI-a si poti sa-l gasesti pe google , astai primul rezultat : http://andybyte.lx.ro/c++/roy_floyd.htm :thumbup:
Titlul: Răspuns: 291 Roy-Floyd Scris de: Cezar Mocan din Aprilie 01, 2007, 12:33:31 Nu stiu pe unde am auzit ca algoritmul Roy-Floyd nu intra in timp la problema asta... :-'. Daca vrei poti incerca Dijkstra.
Titlul: Răspuns: 291 Roy-Floyd Scris de: Kerekes Felix din Aprilie 01, 2007, 12:36:11 Intra si Roy-Floyd (a se citi numele problemei)
Titlul: Răspuns: 291 Roy-Floyd Scris de: Pandia Gheorghe din Aprilie 01, 2007, 13:56:32 Intr-adevar gresisem ordinea forurilor [i,j,k] in loc de [k,i,j] desi am scris algoritmul de 2 ori. Observasem acest lucru (m-am uitat intr-o carte) dar nu mi s-a parut relevant, mai ales ca pe exemple da bine si [i,j,k]. Am facut pe hartie un test mai mare si am inteles de ce e corect asa. Destul de dragutz! Bine ca m-am prins acuma ca nu mi-as fi dat seama si faceam [i,j,k] "pana la moarte!"
Multumesc! am luat 100p :ok: P.S. Pt. "sebi" - citirea si scrierea sper ca le-ai facut cu functiile din <stdio.h> - stream-urile sunt mai lente. Si inca ceva: Daca in matricile f si d ai 0 pe diagonala principala, nu ai nevoie sa verifici ( i != j ) care iarasi "mananca" din timp! Good luck! :banana: Titlul: Răspuns: 291 Roy-Floyd Scris de: Ionescu Victor din Aprilie 01, 2007, 23:52:28 aveam si eu exact aceeasi greseala...de un an incerc sami dau seama ce are...oricum multumesc de hint...acum am 100 :banana:
Titlul: Răspuns: 291 Roy-Floyd Scris de: Petcu Marius din Aprilie 06, 2007, 10:13:27 Am o problema:
am facut ordinea forurilor buna am calculat nr maxim de arce bine(cred) dar nu im dau seama ce are Cod: Cod sters Titlul: Răspuns: 291 Roy-Floyd Scris de: Pandia Gheorghe din Aprilie 06, 2007, 14:47:54 Buna marius. Eu am observat 2 probleme, dar nu garantez ca asta e cauza:
Citat if (a[i,j]=a[i,k]+a[k,j]) and (b[k,i]+b[k,j]>b[j,i] ) then b[i,j]:=b[i,k]+b[k,j]; 1. Nu inteleg de ce compari b[k,i]+b[k,j]>b[j,i] si apoi atribui b[i,j] := b[i,k]+b[k,j] ? adica le pui pe dos. Prima comparatie ar trebuie sa fie b[i,k]+b[k,j] > b[i,j] nu invers cum ai pus tu. Ai inversat atat i si j cat si i si k. 2. De obicei e bine sa pui caracterul "sfarsit de linie" dupa ultimele date scrise in fisier, daca nu se precizeaza altfel in enunt. Deci dupa ce afisezi matricea b poti sa mai pui un writeln. In rest pare corect. P.S. Nu e bine sa postezi surse. Adminii iti vor sterge mesajul! Titlul: Răspuns: 291 Roy-Floyd Scris de: Petcu Marius din Aprilie 06, 2007, 21:58:37 Multumesc foarte mult. :D
Inversam ordinea. Nu cred ca puteam imi dau seama singur de asta. Am luat 100. :winner1: Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 17, 2007, 18:05:59 Am implementat si eu aceasta problema .. si .. pe 50% din teste imi da TLE ... si nu vad cum as putea sa mai imbunatatesc ... vre-o idee se poate ?
Titlul: Răspuns: 291 Roy-Floyd Scris de: Ivan Nicolae din Aprilie 17, 2007, 20:25:17 Mie imi merge fara nici o optimizare speciala..... dar poate ai putea sa ne dai putine detalii....
Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 18, 2007, 00:14:32 pai .. solutia e simpla ...
aplic royfloyd ... si caut sa micsorez distantele ... in cazul in care am gasit acesi distanta... caut sa maximizez numarul de muchii in cazul in care am gasit un drum mai mic... micsorez drumul si reactolizez numarul de muchii .... Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 18, 2007, 07:53:59 pai .. solutia e simpla ... aplic royfloyd ... si caut sa micsorez distantele ... in cazul in care am gasit acesi distanta... caut sa maximizez numarul de muchii in cazul in care am gasit un drum mai mic... micsorez drumul si reactolizez numarul de muchii .... Daca vrei neaparat poti sa faci un fel de roy-floyd in O(N^2 log N) folosind dijkstra cu arbori de intervale / heapuri... dar merge O(N^3)... fii atent la dimensiunile matricii... daca e prea mica poti sa dai peste alte variabile si sa le strici... eventual rescrie toata sursa, poate e un bug greu de sesizat! Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 18, 2007, 08:42:32 O sa o rescriu .. chestia este ca imi iese din timp .... asta ma enerveaza ... daca ar zice ca gresesc .. ar fi altceva ... insa .. iese din tim cu foarte putin ... matricea e dimensionata bine ... daca nu era .. apareau probleme de citire in afara locului unde a fost alocata .. sau aparea raspuns gresit ...
Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 18, 2007, 19:59:16 O sa o rescriu .. chestia este ca imi iese din timp .... asta ma enerveaza ... daca ar zice ca gresesc .. ar fi altceva ... insa .. iese din tim cu foarte putin ... matricea e dimensionata bine ... daca nu era .. apareau probleme de citire in afara locului unde a fost alocata .. sau aparea raspuns gresit ... Iese din timp cu foarte putin la absolut orice problema la care trimiti - asta pt ca la putin timp dupa ce depasesti iti este oprit programul ;) Legat de dimensiuni, e posibil ca tu sa accesezi ceva in afara matricii si acel ceva sa fie din intamplare adresa vreunui indice, pe care il modifici si sa iti iasa din timp... e foarte putin probabil, dar daca altceva nu e... :-' Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 18, 2007, 20:37:59 Cod: for(k=1;k<=n;k++) Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 19, 2007, 07:05:31 Pare corect... am dubii daca acel max e corect, parca trebuia o banala adunare, dar... e foarte posibil sa gresesc.
Bun, am descoperit pana acu ca for-urile merg bine... sa fie de la citire? Eu unul am citit cu scanf si am luat 100 cu n^3... si din cate stiu sunt stream-urile mai incete... pe urma daca ai facut si tu cu scanf & printf ti-as fi zis ca poate ai niste matrici mult prea mari pe care el pierde timp sa le aloce, sau daca le initializezi tu pierzi timp pretios... :-k altceva nu stiu de la ce poate fi, dar cea mai buna rezolvare este sa il rescrii peste vreo 2 zile, dupa ce ti-a iesit din cap problema... o sa fii mai relaxat atunci :thumbup: PS: daca vrei o sa iti dau PM cu sursa mea... Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 19, 2007, 08:40:03 matricile le-am declarat global .. deci ele sunt initializate de la inceptu cu 0 ...
citirea am facut-o cu fscanf si scierea fprintf .... matricile .. sunt la limita roymax[257][257] ( cu 1 mai mult .. dar .. nu cred ca asta e problema .. ) initializarea pe care o fac eu .. este legata de roymax[][] , care reprezinta numarul de muchii dintre doua drumuri ... si care pentru i!=j este 0 in rest 1 .... si o fac la citirea matricei de costuri roymin .... in ceea ce priveste pe max() .. e corect .. daca nu ar fi .. nu mi-ar da raspuns corect ... pe 50% din teste ... pe restul mie imi iese din timp .. nu da raspuns gresit ..+ .. am folosit max() din STL .. si apoi am si implementat un max .. acelasi punctaj ... am incercat chiar si cu un if() ...ca mam gandit ca sunt prea multe apeluri .. tot degeaba.... iese din timp Titlul: Răspuns: 291 Roy-Floyd Scris de: Ivan Nicolae din Aprilie 19, 2007, 09:00:20 Si totusi are dreptate sima_cotizo ... dc e max-ul ala acolo? adica ar trebui direct roymax[j] = roymax[k] + roymax[k][j]; Stiu ca n-ar trebui sa infuenteze, dar.... n-ai de unde sa stii ce se intampla daca il scoti.... (pan la urma max insemna o operatie in plus).
Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 19, 2007, 09:08:50 Dubios, matricea in care ai valoarea drumului dintre doua puncte nu o initializezi cu o val foarte mare?... Eu asa stiu ca trebuie :-'
In rest e bine... foarte ciudat... inca o data te intreb, citesti cu streamuri? :) e foarte putin probabil sa fie de la asta... dar merita sa incerci si cu scanf... Woops, :) de fapt chiar trebuie nr max de laturi pe care le parcurgi... e bine asa... ar fi dubios sa fie nevoie de o rearanjare a instructiunilor de genul Cod: if ( lungimea e mai mica) actualizeaza lungimea si nr de muchii = 0; Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 19, 2007, 10:29:26 Este nevoie de max() pentru ca atunci cand ai gasit un drum de aceasi lungime maximizesi numarul de muchii necesare parcurgerii drumului .. adica ei maximul dintre nr muchii actuale .. si cea noua gasita ..
Initializarea de care vorbesti e facut la inceput ... cand se da graful .. daca intre ori si ce doau noduri se da o muchie nu mai este nevioe sa initializez cu ceva foarte mare ... Daca interschimbi .. nu ajungi nici unde .. am incercat :P Am mai spus .. citesc cu fscanf() si scriu cu fprintf() Titlul: Răspuns: 291 Roy-Floyd Scris de: Sima Cotizo din Aprilie 19, 2007, 10:52:59 Da, ai dreptate... n-am citit toata problema :D ... daca nici una din problemele astea nu e... atunci nu stiu. Daca vrei neaparat fa dijkstra cu heapuri / arbori de intervale ... sau rescrie toata sursa. Mie mi-a mers cu n^3... daca vrei iti dau diseara pm cu sursa mea / imi dai tu cu a ta, ca sa vedem... [acum plec la scoala :( ]
Titlul: Răspuns: 291 Roy-Floyd Scris de: Airinei Adrian din Aprilie 19, 2007, 11:14:31 Nu se merita sa faci dijkstra cu heap sau arbori de intervale fiindca ai O(N^2) muchii. Nu imi dau seama de iei TLE, poate ai pus matricile alea pe long long? (merge mai incet long long si int e de ajuns)
Titlul: Răspuns: 291 Roy-Floyd Scris de: nash mit din Aprilie 19, 2007, 11:55:39 Gata .. acum merge .. intradevar .. aveam declarata matricea de elemente long long .. eu citisem ca fiecaer muchie are lunfimea intre 1 si 100 000 si de fapt scria ca fiecare drum este mai mic decat 100 000 deci ... asta era ..
Multumesc Titlul: Răspuns: 291 Roy-Floyd Scris de: Militaru Adrian din Ianuarie 03, 2008, 12:19:35 Cod: roymax[i][j]=max(roymax[i][j],roymax[i][k]+roymax[k][j]); Cod: roymax[i][k]*roymax[k][j] Titlul: Răspuns: 291 Roy-Floyd Scris de: Toma Radu din Ianuarie 05, 2008, 18:42:47 Nu, deoarece se cere numarul maxim de muchii ce le poate avea un drum de la i si j. Produs se foloseste, de exemplu, la numarul total de drumuri disjuncte de lungime minima de la i la j.
Titlul: Răspuns: 291 Roy-Floyd Scris de: Alexandru Vlad din Februarie 27, 2008, 19:10:09 Aplic roy floyd, actualizez matricea costurilor, daca am gasit drum mai mic sau daca noul drum este egal cu cel din matricea costurilor, verific daca nr de arce este mai mare si actualizez daca trebuie.
nu inteleg unde gresesc... Cine m-ar putea ajuta? ](*,) Titlul: Răspuns: 291 Roy-Floyd Scris de: Asofronie Samuel din Noiembrie 08, 2009, 16:45:42 Din ce cauza apare "Killed by signal 11(SIGSEGV)"
Titlul: Răspuns: 291 Roy-Floyd Scris de: Andrei Misarca din Noiembrie 08, 2009, 19:19:52 Citeste documentația (http://infoarena.ro/documentatie/evaluator). Probabil ieși din limitele unui vector sau ai declarat prea mult.
Titlul: Răspuns: 291 Roy-Floyd Scris de: hulparu adrian din Februarie 23, 2010, 10:35:31 Mi-a tocat nervii vreo 3 ore problema asta. :aha:In mintea mea, in loc sa calculez numarul de maxim muchii calculam numarul de drumuri de lungime minima. Trebuia sa casc ochii mai bine inainte sa ma apuc de lucru :-'.
PS: intra cu Roy-Floyd foarte usor in timp Titlul: Răspuns: 291 Roy-Floyd Scris de: leonard savu din Decembrie 28, 2016, 22:59:11 presupun ca greseala e la cum calculez lungimea maxima dar nu vad unde
Cod: if(i!=k && j!=k && a[i][j] >= (a[i][k]+a[k][j])) Titlul: Răspuns: 291 Roy-Floyd Scris de: Ioan Eftenoiu din Mai 30, 2017, 19:28:37 Cine poate lasa o solutie la problema ?
Titlul: Răspuns: 291 Roy-Floyd Scris de: Ioan Eftenoiu din Mai 30, 2017, 19:28:56 Cine poate lasa o solutie la problema ?
|