Testele din atasamente sunt aceleasi cu cele din raportul evaluatorului (http://infoarena.ro/job_detail/407086)?
Daca verific manual, primesc aceleasi rezultate ca in atasamente, dar evaluatorul imi da incorect la majoritatea testelor.

Multumesc! 

[bradut]

Daca se poate posta aici, rog pe cineva care a facut problema bradut sa-mi spuna pe scurt ideea de rezolvare.

Ciclurile sunt cele care trebuie sa fie tot timpul pozitive.

dar algoritmul determina cicluri de cost negativ? nu prea vad cum ... pentru ca is alea 3 for-uri,  si atat, eventual numa daca mai aplici inca o data Roy-Floyd, si tot mai poti imbunatati costuri....atunci exista ciclu negativ?

Poti afla daca ai cicluri negative dupa prima aplicare Roy-Floyd asa... verifici diagonala principala din matricea costurilor (drum minim de la i la i) si daca ai cost negativ inseamna ca ai un ciclu de cost negativ.
Dar nu cred ca ar trebui sa apara la vreo problema cicluri de cost negativ. Nu prea are sens.

pot exista costuri negative?

La problema asta nu o sa fie, insa algoritmul Floyd-Warshall/Roy-Floyd merge si pe grafuri cu costuri negative.
Ciclurile sunt cele care trebuie sa fie tot timpul pozitive.

M-am uitat peste sursa ta si am o întrebare :

De ce declari matricea s de 10000 pe 10000 ? Nu trebuia de 501 pe 501 ?

Ba da, ai dreptate. Nu stiu de ce am declarat-o asa.

Ramane insa problema incadrarii in timp la ultimul test.

http://zhuzeyuan.hp.infoseek.co.jp/ita/chap16.htm
Citeste mai jos, pe la Optimal polygon triangulation

Intr-adevar, nu am vazut asta, dar totusi...

the optimal triangulation procedure runs in time O(n³)

Exista o solutie NlogN din cate stiu, citeste prin Cormen

Nu este, poate confunzi problema cu alta. In Cormen e aceeasi solutie ca cea oficiala de aici.

Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942. S-ar putea sa mearga .

Nu cred ca ar ajuta mult, avand in vedere ca am de citit maxim 500 de numere. O sa incerc totusi.

LE: Nu merge. Exista o solutie mai buna decat O(n³)? Sau se poate optimiza altcumva?

Presupun ca pentru pascal nu s-a verificat daca intra in timp.
http://infoarena.ro/monitor?task=podm&compiler=fpc

Sau as mai putea optimiza sursa mea cu ceva?

Asa da... e mai pe intelesul meu.
Abia acum am inteles si ce e de fapt inversul modular.

Nu inteleg cum se calculeaza numarul de combinari. Daca stiti alt loc in care e explicata chestia asta, va rog sa postati linkul aici.

Am observat ca s-a terminat timpul alocat pentru interbari.

Totusi, raspunsul din enunt (434185) este corect pentru exemplu?

Probabil ca tu, la fel ca si mine, ai uitat ca se cere suma X1 * 1 + X2 * 2 + X3 * 3 + ... + XN * N, nu XN.
Mi-am batut capu ceva vreme cu asta. 

Da, e de la mine. Nu pot intra decat cu proxy.

Voua vi se incarca site-ul? Mie nu mi-a mers toata ziua.
Daca e de la ei, sper sa rezolve problema pana maine dimineata.

O chestie tare pe care tocmai am descoperit-o:

LSB(x) = x & -x

E veche.

In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta.
Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1.
De ce opusul unui numar este egal cu "negatia" + 1?

Acea "formulă" este defapt dublul ariei triunghiului format de cele 3 puncte, însă în cazul de față te interesează doar semnul. Acea arie se calculează cu ajutorul determinanților.

Mersi, am inteles. E ca si la calcularea convexitatii unui poligon cu ajutorul determinantilor, luand cate 3 varfuri consecutive.

In sursa data ca exemplu pentru al doilea algoritm (scanarea Graham) e folosita o functie "semn" care calculeaza daca unghiul format de 3 puncte este mai mare sau mai mic de 180 de grade:

Cod:

long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}

Cum s-a ajuns la aceasta formula?

Multumesc pentru raspunsuri.  

LE: Mi-am facut cont pe forumul .campion abia acum, si nu am inca dreptul sa postez mesaje, asa ca o sa pun aici inca o intrebare:

Eroarea "Nonzero exit status: 200", primita pe evaluatorul .campion, corespunde cu "200-Division by zero"?

Nu am gasit nicaieri pe site-ul concursului precizari cu privire la erori.



LE2: Raspund tot eu... impartire la 0 era.

Am o intrebare pentru cei care au mai participat, sau pur si simplu stiu mai multe.
Daca eu (clasa a 12-a fiind), ma inscriu la "Toate grupele", afecteaza cu ceva faptul ca nu rezolv toate problemele de la grupele S si M?

LE: Mai am una: si problemele din etapele de pregatire conteaza la clasamentul final?

Au fost schimbate testele la problema asta?
Rezolvarea mea (in pascal) nu reuseste nicicum sa intre in timp.
Am reintrodus si niste surse mai vechi, tot in pascal, care au luat 100 p cu cateva luni in urma, si nici ele nu scot mai mult de 50 p.


LE: Trebuia folosit "shl" si "shr" in loc de "*2", "/2", si in pascal trebuie parsata si citirea, altfel nu intra in timp.

LE2: Inca ceva... La testele 1 si 7 este cate un spatiu (" ") in plus la sfarsitul liniei cu elementele vectorului.

De ce unii useri nu apar in clasamentul dupa rating?
Sunt exclusi membrii echipei infoarena, este ratingul maxim 800, sau de ce?

Mersi 

L.E. Am facut o mica modificare (round in loc de trunc), dar la testul 7 primesc tot WA, desi pe testul oficial imi da raspunsul corect.
Pe infoarena sunt aceleasi teste?

Inca ceva... daca poate sa verifice cineva care a luat 100 de puncte, ce rezultat ii da pt a=8000, b=8192.

Dati-mi va rog niste teste, si raspunsul la ele, sa imi dau seama unde am gresit  .
Pe testele exemplu, pe testele create de mine, si pe 6 din 10 de la evaluare merge bine.
http://infoarena.ro/job_detail/280166

Se poate sa existe drumuri minime pentru care nici un tip de lanterna nu este posibil, atunci programul meu fiind nevoit sa gaseasca un drum mai lung?
Era mai sus un astfel de exemplu...

Cod:

8 6
0 0 0 0 0 0 0 0
8
1 2 1 2
2 3 1 2
3 4 1 2
4 8 1 1
1 6 1 1
6 7 1 1
7 5 1 1
5 4 1 1

Daca sunt astfel de cazuri, nu pot sa caut tipul de lanterna potrivit doar dupa ce am gasit drumul minim. Trebuie sa tin cont de asta cand caut drumul.

Imi da numai 40 de pct pe problema... 4 rezultate incorecte (inca incerc sa vad ce am gresit) si 2 afara din timp (cred ca din cauza ca folosesc bellman-ford fara coada).