Muti soferii din autobuzul cu numar mai mic de soferi in autobuzul cu numar mai mare de soferi. Fiecare sofer va fi mutat de cel mult logN ori.

Solutiile oficiale presupun ca poti ajunge din nodul 1 in orice alt nod. Poate la asta se refera "graf orientat conex", nu imi dau seama.

E picat evaluatorul. O sa isi revina odata ce cineva din echipa infoarena il reporneste.

Aceste informatii ar tb sa fie facute public. Stiu ca e redundant, eu vazand timpii tai la problema pot lejer sa fac o suma a lor, similar si cu memoria. Dar acest lucru ajuta in momentul in care pe un utilizator anume il intereseaza "cine a scos timpul total minim si a folosit memorie cel mai putin". Sau fiind 2 criterii lucrurile se pot incrucisa neasteptat. Am vazut acest procedeu pe un site care merge pe aceeasi idee cu infoarena. Numele nu mi-l amintesc. Pe baza acestui lucru ar trebui facut un clasament (ptr cei cu surse de 100p) - aceasta reprezinta o sugestie.

Aceasta facilitate va fi disponibila in curand™.

Offtopic: Nu va mai pierdeti timpul cu certuri aiurea pe net
@Enal G: Fa-ne o favoare si, inainte sa postezi, sa faci un rezumat al postarii.

2. Au fost schimbate limitele de timp pentru probleme la un moment dat (http://www.infoarena.ro/calibrare-limite-de-timp). La profil nu ii apare ca fiind rezolvata fiindca acolo se iau doar submisiile din arhiva de probleme iar aceasta pe care ai pomenit-o a fost la concurs.

1. Am reusit maxim 90. Nu cred ca intra in Java solutia asta. Ar merge marita putin limita.
2. E arbore fara radacina. Nu conteaza din ce nod pornesti cu primul bfs.

Cum de nu s-a facut niciun test cu distanta maxima a oilor 2^31 - 1? Majoritatea surselor de 100 iau TLE pe un astfel de test. Mai sunt si multe surse de 100 care ar trebui sa ia WA.

Daca lipseste doar un numar programul il afiseaza de 2 ori.

Testeaza pe programul tau

Nu actualizezi bine minn si maxx. Gandeste-te ce se intampla daca lipseste un singur numar. Ca sa scapi de MLE incearca sa folosesti bitset in loc de vector de bool. Gasesti pe net cum se foloseste.

A fost data o problema asemanatoare la IOI http://www.ioi2011.or.th/hsc/tasks/EN/race.pdf (mergea O(NlogN) fara frunze). Ciudat, cei de la IOI n-au facut secret de stat din faptul ca sunt N-1 muchii.

Dinamica gen problema rucsacului unde toate obiectele au marimea N-i.

Poti gasi aici http://www.infoarena.ro/cauta-probleme. Pentru Backtracking poti incepe cu http://www.infoarena.ro/problema/flip.

Prin dinamica eu inteleg ca rezultatul se afla in dinamica. Ce ai facut tu e tot un fel de BFS.

Trebuie sa construiesti acel numar 99..99, deci e cam acelasi lucru.

Da 0 pe parcurs doar daca N >= MOD. In acest caz poti aplica http://en.wikipedia.org/wiki/Lucas%27_theorem.

La solutia cu programare dinamica ar trebui sa retii sirul minim lexicografic pe care il poti obtine ajungand la o celula (i, j) iar asta e O(N^3).

La penultima iteratie ai e=r. Apoi la ultima iteratie, r devine 0 si faci m=e (e-ul de la iteratia anterioara, adica r-ul anterior). Deci penultimul r e m-ul de la final.

Ti-am zis mai sus. In interiorul for-ului trebuie sa memorezi valoarea lui i intr-o alta variabila (tu ai pus e inainte). Dar sa faci asta si pentru n (de exemplu, m=n si apoi lucrezi cu m).

for(i=1;i<=n;i++) {
  e=i;
  m=n;
  while(....
  ...
}

Tratezi separat coordonatele x si y fiindca sunt independente. Apoi trebuie doar sa cuplezi fiecare nava cu un x (sau y). Deci ai in jur de 2000+N noduri. Te opresti in momentul in care cuplajul e K.

Sa nu mai scrii asa ceva "i<=n && i++" in viata ta. Vad ca memorezi valoarea variabilei i in variabila e ca sa nu modifici i-ul. De ce nu faci asta si pentru n?

Din cate imi amintesc, in Pascal tipul de date "integer" e pe 16 biti si numarul tau depaseste plaja de valori pe care o poate memora. Trebuie sa declari variabila "longint".

Aceasta e politica infoarena din toate timpurile.

Cum a fost concursul pentru mine:

0:30 Habar n-am cum se face Naveplanare. Hai sa o citesc si pe cealalta.
0:50 Geometrie, nu pare promitator. Hmm, pare mai usoara. Cred ca m-am prins.
1:07 Done. Next.
1:30 Aaa, deci navele se muta secvential si nu paralel?! Ok, poate asa e mai simplu.
1:50 Hmm, flux. Dar nu pare sa intre in timp. Aaaa, ok, m-am prins.
2:00 Nu am chef sa implementez flux, sigur nu e ceva mai simplu? c***t, hai ca implementez flux... sau copiez din alta sursa.
2:10 Ok, hai sa adaptam sursa si sa construim graful.
2:30 c***t, am mai multe muchii intre o pereche de noduri. As putea sa schimb, dar mi-e lene. Sigur nu e ceva mai simplu? Bine, hai ca fac asa. Pointeri, minunat.
2:45 Done. Sper ca e ok. Wtf, s-a calificat Halep in finala? 

Problemele dragute, dar nu pe placul meu . Insa nu au fost ambiguitati in enunturi, deci  .

Drum6 - Motivul pentru care nu merge un simplu greedy e ca la un moment dat s-ar putea sa ai 2 celule egale si nu stii pe unde sa o iei. Deci, poti sa tii intr-o lista celulele pana la care ai un drum minim lexicografic si tot inaintezi. E un fel de bfs.

K-BubbleSort - Simulezi algoritmul din problema, cu optimizarea ca retii pozitiile la care ai v[i] > v[i+1]. Complexitatea e O(N+K).

Submatricele cu o singura coloana sunt valide?