La ubuntzei avea ceva daca treceam de mai multe ori prin destinatie? Din enunt asa am inteles.
Si orasele nu trebuiau vizitate in ordinea in care se dadeau nu?
Trebuia minimul posibil si trebuiau incercate toate posibilitatile?

Da scuze, eu nu inteleg foarte bine problemele de joc optim... , adica nu intelg bine notiunea de a juca optim.

Dar atunci Ionel poate pleca din 4 si Vasile poate alege 2 si apoi Ionel alege 5 si castiga!
4 de ce nu se afla intre solutii?

Sigur de victorie inseamna ca orice mutari ar alege Ionel, va castiga intotdeauna?

Ca de exemplu din 6 Vasile merge in 4 si apoi Ionel in 7 si  Vasile nu mai are unde sa mute deci Ionel castiga.
Dar daca din 4 merge in 2 si apoi Vasile merge in 5 atunci Ionel pierde.

Va rog lamuriti-ma si pe mine  .

Da dar la tine daca cercul i nu se intersecteaza cu cercul i+1 atunci mai are vreo sansa sa se intersecteze cu cercul i+2?
In cazul de mai jos are:

Acum poate omit eu ceva din mesajul tau.

LE : Am reusit sa fac exercitiul pana la urma. 

Cum ai facut?

http://www.isjcj.ro/

Cred ca la regulamentul de la al 3-lea link se refera Petru.
Scrie acolo:
   Limbajele de programare agreate sunt: MinGWStudio şi FreePascal disponibile pentru instalare la adresa http://infoarena.ro/schimbare-borland/pachet

Si eu iau 95 cu MLE pe ultimul test declarand vectorii asa:

Cod:

#define nmax 10001

vector<short> G[nmax];
short N,K,nh;
short c[nmax];
short H[nmax];

Imi poate spune si mie cineva cum sa mai reduc din memorie?

Multumesc anticipat!
Cu H[]-heapul si c[] vectorul folosit pentru dinamica.

[joi]

Salut!
Eu nu am intrat pe infoarena in weekend-ul acesta si din ce imi aduc aminte aveam 112 probleme rezolvate joi seara/(poate si vineri ).
Astazi de dimineata cand m-am uitat pe site am vazut ca am 111.
Stiu ca vineri(nu joi!) seara erau niste probleme la evaluator, pe care eu le-am reclamat.
Ati facut cumva vreo reevaluare la vreo problema in aceasta perioada?


PS: numarul de probleme incercate nu imi mai aduc aminte care era... acum sunt 28.

Evaluatorul nu functioneaza!

Eu nu inteleg urmatoarea situatie la problema asta.
Sa ziceam ca sunt la o bila de tip C si am a[poz]=2. Daca poz=N este evident ca am gasit o solutie buna.
Chestia ciudata este ca din 9 dintre teste reiese ca poz poate fi si mai mic.
Adica:
B->2B - nu este cazul
B->1A3AC- cere ca C sa fie ultima bila => C=>3BC-C-ul ramane ultima bila
                                                             =>12A-infundatura
                                                             =>2-infundatura   
Deci C-ul va fi mereu ultima bila si daca il inlocuiesc cu o bila 2 nu mai am alta bila sa pun dupa si ca sa fie o configuratie corecta trebuie ca pozitia pe care transform bila C in 2 sa fie N.

Imi poate spune cineva de ce nu am dreptate cu rationamentul acesta?

http://www.olimpiade.ro/informatii.php?etapa=3&materie=8&editie=9

[folosind produsul incrucisat]

Am doua intrebari la care nu am reusit sa gasesc un raspuns, asa ca apelez la voi   :

1) Cum compar unghiurile polare a doua puncte P₁ si P₂ in raport cu un al treilea P₀ folosind produsul incrucisat (ex. 35.1-2 (prima editie) si ex. 33.1-3 (a doua editie) ).

Off-topic : stiu ca se poate calcula unghiul polar a lui P₁ in raport cu P₀ si asa : m = arctg( (y₁ - y₀ ) / ( x₁ - x₀ ) ) . E corect ?

2) Cum imi dau seama in timp liniar daca un set de puncte {p₀, p₁, ..., p_n-1} formeaza un poligon convex. In carte scrie ca daca verificam sa avem numai intoarceri la stanga sau numai intoarceri la dreapta nu produce intotdeauna rezultatul corect. Sunt nedumerit ca eu nu am reusit sa gasesc un contraexemplu. (ex. 35.1-4 (prima editie) si ex. 33.1-5 (a doua editie) ).

Multumesc anticipat !

1) (x1-x0)*(y2-y0)-(x2-x0)(y1-y0)>0  rezulta ca unghiul polar al lui P2 e mai mare ca unghiul polar al  lui P1.
2) Cred ca ceea ce vrei este in desenul de mai jos:

Ok.
Multimesc mult pentru explicatia muncita .

Dupa ce ai facut flux, in graful rezidual vor exista niste muchii pentru care fluxul este egal cu capacitatea. Daca elimini acest muchii, graful tau devine neconex, deci inseamna ca taietura este inclusa in aceasta multime de muchii.

Pai eu le-am considerat pe toate muchiile care au fluxul egal cu capacitatea.
Adica, sa inteleg ca raspunsul nu este multimea muchiilor cu flux[ i ][ j ]=cap[ i ][ j ] , ci o submultime a acestei multimi?
Daca da, cum o determin(daca se poate fara parcurgere)?

Stiu sa aflu valoarea taieturii minime.
Imi poate spune cineva cum aflu muchiile?

Cred ca la problema asta se petrece ceva ciudat .
Mi-am retrimis sursa de 100 de puncte si iau 0 puncte   .
Rog frumos un Admin sa se uite putin la teste.

LE: Never mind. Se pare ca daca afisezi cu "\n " in loc de "\n" sau '\n' e raspuns gresit acum.

Ajunge sa retii doar ultimele 2 linii. Dupa cum se observa si din recurenta din articolul de solutii, la fiecare pas nu ai nevoie decat de linia i si i + 1. Iar in legatura cu memoria, vroiam sa pun limita 648kb, dar nu prea am eu permisiunea asta, pentru ca problema nu a fost adaugata de pe contul meu. Poate se ofera vreun admin sa modifice limita .

Oups  !  Asa este, nu stiu de ce am avut impresia ca nu se poate cu 2 linii, cred ca m-au derutat j-urile.
Acum iau 70 pe sursa facuta cu 2 linii cu relatia din articolul de solutii.
Si vad ca mai sunt si altii care au picat testele 4,9,10.
Ce contin special aceste teste?

Later edit: Am luat 100, problema era de la faptul ca declaram numerele de pe tabele int, in loc de long long, sau nu faceam conversia cand calculam matricea dp[][].

[dp[player][ i][j]]

Nu reusesc sa gasesc recurenta buna la problema Treasure.
In concurs amluat 4 teste(din 10) si cand m-am uitat ieri pe sursa mi-am data seama ca recurenta era complet gresita.

Eu in concurs am luat starea
dp[player][ i][j]-valoarea maxima pe care o poate obtine jucatorul player(Bessie este 1, Bonnie este 0) din primele i si ultimele j monede.

Rezultatul a fost maximul elementelor dp[1][ i][N-i] cu i=0 la N


Starile initiale au fost dp[1][0][0]=dp[0][0][0]=0.

Iar relatia mea de recurenta este

  dp[player][ i][j]= suma_stanga[ i]+ suma_dreapta[N-j+1] - min(dp[1-player][ i-1][j] , dp[1-player][ i][j-1] );

cu suma_stanga[ x]=suma primelor x monede;
si suma_dreapta[N-x+1]=suma ultimelor x monede;


Imi poate spune si mie cineva ce este gresit in rationamentul meu?

D[ i ][ i ] = V[i ] pentru 1 ≤ i ≤ N
D[ i ][j] = max(V[ i ] - D[i + 1][j], V[j] - D[ i ][j - 1]), i ≠ j
D[ i ][j] = max(D[ i][j], V[ i ] + V[j] - D[i + 1][j - 1]), j - i ≥ 2
Solutia se va afla in D[1][N].
Pentru a obtine insa 100 de puncte nu trebuie retinuta intreaga matrice, ci doar ultimele doua linii.

Care sunt ultimele 2 linii?
Nu cumva trebuia diagonale? Si chiar si asa cum as putea tine ultimele 2 diagonale?

Atkin?

Nu vei gasi un astfel de test.
Wefgef a spus in timpul concursului ca toate frazele contin litere.

http://infoarena.ro/forum/index.php?topic=5114.0

primul element al subsirului trebuie sa fie mai mic lexicografic decat al 2-lea (scrie in enunt: s1<s2, s2>s3, s3<s4, s4>s5, ...)

Da. Asta era.

Am o intrebare.
Nu cumva primul element trebuia sa fie mereu mai mic decat al doilea?
Eu am facut in ambele variante si cred ca din acest motiv iau 50.

Problemele propuse la concurs vor fi pastrate in Arhiva de probleme?