Ok... mersi... daca mai stie cineva ceva... ca jur ca n-am gasit... nici macar pe http://justfuckinggoogleit.com ...

Salut! Poate cineva sa-mi spuna daca stie ceva de algoritmul lui Dantzig? Din ce am gasit pe net este un algoritm folosit la gasirea drumului minim intr-un graf. N-am gasit mai multe detalii... Daca ar putea cineva sa ma ajute as fi foarte recunoscator.

Pai.. eu am citit "babeste" caracter cu caracter. Citirea mea e ceva de genu:

Cod:

scanf("%d %d\n",&R,&C);
for(int i=1;i<=R;i++) {
 for(int j=1;j<=C;j++)
  scanf("%c ",&map[i][j]);
 scanf("\n");
}

Unde map[j] e de tipul char... si intra in timp... dar cred ca se poate si direct cu  %s. Oricum, bafta!  

Mersi... Util de stiut!   Dar totusi in legatura cu algoritmul meu... are cineva vreo/vreun sugestie/critica/sfat?

Sunt constient ca este o stare. Astfel ca in Dijkstra pe langa un vector D cu proprietatea ca D=distanta minima de la 1 la i, mai tin si un vector D2=cati wati am consumat pana in i. Cand i este prieten am grija ca toate drumurile la care ajung prin i sa aiba numarul de wati resetat. Si asta fac pentru un l de la 1 la K. Si practic singura conditie de continuare este ca numarul de wati folositi pentru a ajunge intr-un nod j este mai mic decat l. Adica nu aleg un nod decat daca am wati sa ajung pana la el. Apoi retin drumul minim aflat din punct de vedere al timpului. Apoi dintre acestea retin pe cel pentru care am folosit cei mai putini wati. Iar spre rusinea mea   care este diferenta intre o si O ? Mersi mult!

Algoritmul meu are o complexitate O(N^2*K). Adica... mai simplu... pt. fiecare K calculez drumul minim prin care se poate ajunge de la 1 la N, respectand conditia watilor. Algoritmul folosit e Dijkstra. Testul asta are ceva ce ar putea sa fie ratat?

   
Recunosc ca este cu adevarat provocator. Dar cu toate astea...ati putea sa-mi dati macar un mic hint? Adica m-am tot chinuit si n-am reusit sa-l iau...  
Raman etern recunoscator pentru orice hint.  

O(N*N)  

Eu am incercat sa implementez... si n-am reusit. Am tratat si cazul cand n=1. Probabil imi scapa ceva mic... Nu stiu... Daca a mai avut cineva vreo problema similara si ma poate ajuta as fi recunoscator....      

Eu am facut un algoritm O(N*T). Dar nu sunt sigur de corectitudine... Si dat fiind ca nu iau 100... presupun ca nu e corect... or uit ceva. Iata ce fac eu:

1. Leg de frunze un nod virtual care are distanta catre acele noduri 0
2. Pornesc un bfs din acel nod astfel incat sa generez intr-un vector distantele minime din orice nod catre cea mai apropiata frunza.
3. Selectez maximul dintre aceste valori.
4. Afisez toate nodurile care au distanta maxima.

Pe testul dat in exemplu merge. Logic cred ca ar trebui sa fie ok. Daca poate cineva sa-mi zica daca ii se pare incorect. Mersi mult.

Da. Fara indoiala un concurs reusit. Desi intr-adevar fiindca a fost un singur test nu am putut verifica exact unde greseam. Dar oricum la concursuri gen preONI nu am cum sa evaluez sursele pe parcurs... deci oricum e mai bine asa. In plus, fiind evaluatorul online tot timpul e mai linistitor(zic eu). Asa macar dupa ce te chinui la o pb. stii clar: ai rezolvat-o sau nu. Oricum e ceva nou. Multumesc tuturor celor care au facut aceasta experienta posibila!  

Am si eu o mica intrebare... In legatura cu valorile de test de pe site.

Sursa mea, care a luat 100 de puncte... la testul 5 5 5 6 6 6 afiseaza ca raspuns... 11.900... iar pe site scrie ca valoare... 7.714.

Pare un pic dubios...nu?  

Ahem... poate ca pare ciudat... dar... n-ar fi fost mai buna egalitatea?  
Adica ... daca nu putea bate un alt cal... e clar ca profitul adus era <=0 ... deci ... cea mai mare valoare... nu ar fi 0? Adica remiza?

Eu faceam in felul urmator:
1. Sortam caii si ai lui gigel si ai lui ionel crescator.
2. Pornind de la 1 parcurgeam caii astfel:
  2.a. Daca cal Gigel > cal Ionel => Gigel+200 lei. Se trece la urmatorii 2 cai.
  2.b. Daca cal Gigel = cal Ionel se trece la urmatorii 2 cai.
  2.c. Daca cal Gigel < cal Ionel => Gigel-200 lei. Se compara calul acesta al lui Gigel cu urmatorul cal al lui Ionel.

In mod normal ar trebui sa asigure ca caii care vor castiga sunt maximi.  

Operatie de modulo pe numere mari?!?!?! Woah... te-ai chinuit ceva... E o idee... Dar nu e nevoie... Mai schimba un pic formula... O sa vezi ca iese si fara numere mari.  

Am si eu o intrebare. Nu-mi iese testul 9.    Am vazut pe forum ca nu sunt singurul care a avut aceasta problema. Nu iau TLE, ci W.A. Vreau sa intreb daca greseala mea este la algoritmul meu de flux. Este primul pe care l-am implementat pana acum si am vazut ca testul asta este facut tocmai sa fice fluxurile neoptimizate. Eu fac in felul urmator:

1. Tin 2 matrici, 1 de capacitati, 1 de ce capacitate reziduala mai am pe ramura i j
2. Aceasta a 2-a matrice este initial initializata cu -1.
3. Fac Edmonds-Karp. Adica fac un BF.
4. Iau drumul de la BF fac o functie update care imi schimba in matricea reziduala. Astfel daca in matrice drumul de la i la j != -1, pur si simplu scad sau cresc dupa cum trebuie. Daca drumul este chiar -1. Atunci fac asa:

Cod:

 A[tata][fiu]=cap[tata][fiu]-min;
 A[fiu][tata]=min;

Cam atat. Ma gandesc ca poate problema e undeva aici. Daca cineva poate sa ma ajute i-as fi recunoascator ca nu stiu ce sa mai fac.    

Interesant... Si testul dat pe site e cam acelasi.... Hmm... Cred ca intr-un fel ai putea sa fii mandru. Oricum... Interesanta faza...

Ok, eu am o idee... Nu stiu exact cat de buna este. Ma gandeam ca daca tot ati inceput sa puneti in arhiva probleme de la ONI din anii trecuti, ati putea chiar continua sa faceti chiar o arhiva de acest tip. Eu unul, am incercat sa caut pe net enunturi si rezolvari de la olimpiade mai vechi de 2 ani... si nu am gasit mai nimic    Cred ca ar fii foarte apreciata de toti care se pregatesc si pentru cei care nu au mai avut contact cu olimpiada. Chiar ar fi o chestie daca ati putea, sa zicem, sa faceti ceva gen acm... sa se poata simula o olimpiada... fiecare sa simuleze o olimpiada.... Ar fi interesant zic eu. Oricum site-ul se prezinta foarte bine, iar pentru mine a fost si inca este un mare ajutor in pregatirea mea, ca sa nu mai zic un prilej de destindere! Va multumesc si bafta in continuare!  

Am si eu o nelamurire la problema asta. Mi-se pare un pic ambiguu textul ei. Acolo spune ceva de genul: "daca alege o lanterna cu un nr. de wati mai mic decat necesar durata va fi strict mai mare... daca nu va fi mai mare sau egal". Adica el poate merge pe o zona chiar si fara lanterna dar ar dura mai mult? Sau cum? Cum influenteaza timpul de deplasare lanterna? Puteti sa incercati sa imi explicati si mie?    Mersi!

Pai... este o diferenta... daca vrei sa vezi singur care, ca poate nu ma crezi.... fa un:

Cod:

printf("%d %d\n",sizeof(long),sizeof(long long)); 

Asa iti va afisa marimea in bytes. Daca totul e ok, ar trebui sa dea 4 8. Adica 4*8=32 si 8*8=64. Cel putin asa da pe linux   Oricum... asta e diferenta... adica destul de mare.

Bafta!

Pai... ca hint.... puteai sa afli daca un camion de capacitate X poate transporta toate saltelele(sau nu) in O(N). Si apoi trebuia sa gasesti valoarea minima. Si preferabil .... in timp cat mai scurt...   Puteai face acest lucru ... ori luand fiecare valoare si verificand.... ori .... altfel....   Bafta!

Scuze ca intreb....dar... unul din marile avantaje ale Happy Coding era tocmai k puteai sa iti evaluezi sursele pe viu.... Ori, fara suparare... nu prea am benificiat de aceasta facilitate pana acum. Sper sa puteti sa dati drumul cat mai curand. Bafta si felicitari pentru un concurs reusit!

Gata. Am luat 100!  
Multumesc mult tuturor pentru ajutor si pentru idei!

Mersi mult! Am luat 100 acum. Dar totusi de ce nu mergea cu printf? Rontujea rezultatul sau de ce? Oricum mersi de idee.

Salut!
Si eu iau tot 75/100. Rationamentul sper ca e corect, asa ca ma gandesc ca ar putea fi tot de la precizie. Eu fac tot cu printf. De curiozitate, tu cum ai facut sa nu mai fie problema de precizie?

Salut. Am implementat si eu problema, dar din pacate, nu merge testul 7 -> WA. Am observat ca au mai fost persoane care au avut probleme la acest test. Daca puteti  sa-mi dati vreun sfat... Mentionez ca am tratat(corect sper eu) si cazurile cu -1 sau 0.  Mersi.