Si eu am M * log(N) cu o constanta destul de mica si iau 40p. A fost strânsă limita de timp. Oricum dacă sortai muchiile aveai deja M * log(M).

Pot exista self-loops?

Costul muchiilor este mai mic in modul decat 2³¹-1?

Nu chiar. Gândește-te ce se întâmpla când unesti 2 arbori. Dupa unire atunci când faci un Find se poate sa vizitezi anumite muchii pe care le-ai vizitat mai înainte.

The first problem can be solved using Simulated Annealing method. Time complexity is O(N log P), where P depends on the precision the result is calculated. This method also works for the third problem.

Nu trebuie sa trimiți pe infoarena fișierul xml asociat proiectului CodeBlocks. Trimite fișierul .c/.cpp. Fi atent si cum numești fișierele de intrare/ieșire: nu pune path-uri absolute, ci fa asa ifstream f("cmmdc.in").

Sa zicem ca intr-un nod ajung 3 autobuze: unul cu 2 soferi, altul cu 3 și altul cu 5. Atunci nu trebuie sa ii mut pe cei 2 din primul si pe cei 3 din al doilea, in al treilea autobuz? Ultimul va fi cel care va "avansa" catre radacina impreuna cu 10 soferi.

Cum se poate demonstra ca este cel mult log(N)? Eu am mutat șoferii din toate autobuzele în autobuzul care avea un șofer cu număr maxim de mutări (asta pentru fiecare nod din arbore) si pica. Adica facem o parcurgere in adancime si pentru fiecare nod, dupa ce rezolvam subarborele sau vedeam cate autobuze ajung in el. Unul dintre acestea trebuie sa treacă mai departe către rădăcina. Si acesta era cel care avea un sofer cu numar maxim de mutari.

Cum sa scapă la problema Autobuze3 de condiția de 25 de mutări pentru un șofer? Ideea inițiala a fost ca răspunsul este costul unui MST. Dar cum se construiește răspunsul astfel încât sa nu existe mai mult de 25 de mutări?

Exista o eroare in configurarea problemei.

Este ok ca nu se modifica.   Mulțumesc!

Data rundei finale este sigur 23-24 mai, sau exista șansa sa se modifice? Întreb pentru ca mai sunt niște concursuri în perioada aceea.

Runda va fi sambata, pe 28 martie?

Sunt 2 lucruri diferite în principiu şi fiecare are avantajele lui, depinde unde vrei sa le foloseşti. Marea diferenţă este ca clasa vector pune la dispoziţie un "vector" dinamic (ca o listă simplu înlănţuită). Este foarte des folosit atunci când se lucrează cu grafuri pentru a reţine lista de adiacenţă. Poţi folosi un tablou unidimensional simplu oricând nu ai nevoie de o structură în care să adaugi elemente "dinamic" şi în multe alte locuri. Oricum, poţi înlocui un vector normal cu un vector din STL, depinde cum îţi e mai confortabil.

Pot exista mai multe puncte Q cu aceeași abscisa x?

Spor tuturor! 

Testarea de la OJI se realiza/realizeaza in alte conditii decat pe infoarena. Tu trebuie sa respectii restrictiile de aici, adica 10 ≤ M ≤ 1.000.000 si limita de timp 0.05 secunde. 

Fisierul de intrare este trapez.in nu trapeze.in. La fel si pentru iesire.

Atunci cand un program trece de la codul sursa la executabil se parcurg mai multe faze. Prima dintre ele este etapa de preprocesare realizata de un preprocesor. In mare in aceasta etapa se inlocuiesc directivele de preprocesare (e.g. #define) cu valorile lor. De exemplu, daca in cod ai scris ceva de genul

Cod:

#define NMAX 100
int v[NMAX];

el va deveni, dupa preprocesare:

Cod:

int v[100];

, iar directiva va disparea.
Etapa de compilare consta in traducerea codului in limbaj de asamblare care este dependent de arhitectura si de setul de instrucțiuni al procesorului. Erorile de compilare sunt clasice: sintaxa, nu declari variabile, etc. Nu inteleg la ce vrei sa te referi prin eroare de preprocesare.

Programul tau nu este suficient de rapid si de aceia primesti Time Limit Exceeded. Rezolvarea ta nu este cea optima, adica ordinul de complexitate este prea mare. Pentru 100p trebuie sa folosesti indicatorul lui Euler. 

Un subsir crescator este maximal daca nu mai poti adauga elemente la el care sa pastreze invariantul de monotonie. In seventa 2 1 2 3 4, subsirul 1 3 4 nu este maximal deoarece se poate extinde la 1 2 3 4. Acum din multimea subsirurilor crescatoare maximale tu trebuie sa il gasesti pe cel de lungime minima si minim lexicografic.

C++ este de ajuns pentru un incepator.   Depinde ce vrei sa faci. Daca te intereseaza algoritmica invata bine C\C++. Tutoriale despre C++ gasesti peste tot pe web, e.g. http://www.cplusplus.com/. Dupa ce inveti sa il foloesti, eventual si OOP, apuca-te de rezolvarea de probleme. Daca te intereseaza olimpidele, pe la clasa a 10-a se da Lee (asa ii se spune parcurgerii in latime, sau Bellman-Ford-ului cand este aplicat pe matrici  ), putina programare dinamica si probleme cu siruri de caractere. Incepe sa rezolvi probleme propuse la locala, judet si cele de din arhive. Vezi ca nu intotdeauna o stea dificultate inseamna cel mai usor  . Parerea mea este sa te gandesti cat mai mult la o problema, si asta nu inseamna 10 minute, pentru ca asa te dezvolti. Daca nu iti dai seama de idee, abia atunci utita-te pe solutia oficiala sau intreaba pe forum.

Parcurgi fiecare element de pe prima linie, si din fiecare te deplasezi linie++ si colona-- cat timp line si coloana raman in intervale valide. Astfel, vei parcurge matrice pe diagonale paralele cu diagonala secundara.

Faptul ca primesti SIGSEGV depinde de sistemul de operare pe care se testeaza solutia. De exemplu Unix-urile sunt mai "sensibile" decat Windows-ul. Exista situatii cand un program functioneza pe Windows dar pe Unix (ex. Ubuntu, Mint) primeste SIGSEGV.

Daca a si b sunt prime intre ele trebuie afisat 0.