Toata lumea pe care o cunosc eu a scris "Ultima noapte...". Imi cer scuze daca uit de cineva.

http://youtube.com/watch?v=owMjAbkU1eE

Problema se poate rezolva asa:

1. Faci un graf cu nucile + pozitia initiala.
2. Faci o dinamica, a[ i ][ j ] -> costul minim sa mergi prin nodurile din configuratia binara a lui i si sa te afli in nodul j.

Daca nu intelegi, mai detaliez. Complexitatea finala e O(2 ^ n * n ^ 2) si ar trebui sa intre in timp.

Daca la g++ nu mentionezi niciun output cu flagul "-o", atunci iti compileaza in a.out direct... deci ce a facut el cred ca e corect

imi cer scuze, nu am stiut.

Poti, te rog, explica de ce nu alegi pivotu direct random?

In functia lui am incercat sa fac asta prima data. Alegand pivotul random direct, pentru N = 5 si sirul: 1 2 3 4 5 da uneori rezultatul: 2 3 4 4 5. Am mai vazut implementari care tin cont de faptul ca pivotul se afla pe prima pozitie, dar nu am avut rabdare sa ma uit pe functia lui. Cel mai sigur e sa interschimbi prima pozitie cu un pivot random, si merge pe toate cazurile pe care merge qs implementat normal.

In primul rand nu trebuie sa rulezi .out-ul. Corect este:

ulimit -v 1024
./a

Ti-am modificat functia ta sa aleaga pivotul random. Da niste teste mari, de genul 20000, 19999, 19998 .. 1 si vezi diferentele de timp.

Cod:

void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   if(left != right)
   {
   	int aux = numbers[left], randompoz = left + rand() % (left - right);
   	numbers[left] = numbers[randompoz];
   	numbers[randompoz] = aux;
   }
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
	 numbers[left] = numbers[right];
	 left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	 left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}

1. La ONI poti scrie ce vrei in sursa.. nu prea se uita nimeni in sursa ta atat timp cat nu depui contestatie. Daca depui contestatie exista posibilitatea ca cineva din comisie sa se uite peste sursa ta.

2. Segmentation Fault apare in unul dintre urmatoarele cazuri:
a. Incerci sa accesezi o zona de memorie nealocata. De exemplu:

Cod:

int a[100]; 
printf("%d\n", a[101]);

b. Folosesti prea multa memorie. In Linux poti verifica daca iti depaseste memoria folosind comanda ulimit.
De exemplu, pentru a verifica daca programul test ruleaza ok cu mai putin de 1 mega memorie folosesti:

ulimit -v 1024
./test

In cazul in care programului nu ii ajunge 1 mega memorie, iti va afisa un mesaj de eroare.

3. Bubble sort este o metoda de sortare, pe care nu ti-o recomand datorita complexitatii mari (N^2). Metode de sortare mai rapide sunt:

-> QuickSort - complexitatea in cel mai rau caz este N^2, dar daca alegi pivotul random va merge mult mai bine. La fiecare pas alegi un pivot, si interschimbi elementele astfel incat toate elementele < pivot sa se afle in stanga pivotului, iar cele >= ca pivotul sa se afle in dreapta. Apelezi recursiv functia de sortare pentru cele 2 regiuni.

-> MergeSort - N log N - un vector cu N valori este impartit in doi vectori de dimensiune N / 2. Se apeleaza recursiv functia de sortare si apoi interclasezi cei 2 vectori sortati.

-> HeapSort - N log N - bagi toate elementele intr-un heap si extragi la fiecare pas minimul (sau maximul)

O implementare foarte buna a functiei de sortare este functia sort() din STL.

Nokia Morph
http://www.youtube.com/watch?v=IX-gTobCJHs

Chiar acum am testat chestia aia: int a[100] = {-100}; atat in Linux cat si pe BC 3.1

In niciunul dintre ele nu initializeaza vectorul! Ceea ce face e doar sa puna valoarea -100 pe prima pozitie din vector (a[0]).
Era foarte simplu ca in timpul concursului sa verifici daca comanda aia chiar merge, si chiar era recomandat sa o faci. Pot spune ca ai avut noroc ca ai luat 56 de puncte.

Sper ca te-am lamurit si ca pe viitor nu mai expui de 10 ori aceeasi problema!

Cred ca ar trebui sa mai rezolvi niste probleme inainte sa te apuci de bagat probleme in arhiva, deoarece procesul de includere a unei probleme in arhiva nu consta doar in copierea enuntului. Trebuie scrisa o sursa, uneori generate teste, uneori scris un evaluator, etc.

Daca te ti de treaba o sa ajungi sa bagi si probleme pe infoarena.

Te-ai calificat.. ce mai conteaza ce a fost la OJI sau ca nu-ti merge ceva pe Borland, toti trecem prin asa ceva incepand cu perioada de pregatire dinaintea judetenei. Gandeste-te la cei care nu s-au calificat din cauza Borlandului (daca au fost). Acum ai Linux sau ce mai vrei tu, asa ca nu are rost sa iti mai descarci nervii si frustrarile aici...

Nu are nimeni nimic cu tine daca scri intrebarile astfel incat sa nu trebuiasca sa le citim de 3 ori pana intelegem ce ai vrut sa zici

Spor la treaba

getch - citeste un caracter de la intrare
getche - citeste un caracter si il afiseaza pe ecran

getche nu e standard

Ce are functia getche (in afara ca e deprecated)?

Unde se tine proba de concurs?

pentru a folosi functia power folosesti:

#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

sper ca asa se scrie ultima dintre ele.

Functia power din STL este implementata in timp logaritmic.

Testele la problema SN nu sunt suficient de bune.

In rest, a fost ok runda, dar incearca sa nu mai pui link la Wikipedia la fiecare cuvant.

http://youtube.com/watch?v=7nBgqFKhrmE
intre 01:48 - 01:56 il puteti vedea pe Wefgef 

Dupa mutarile facute asupra cladirilor, coordonatele acestora trebuie sa ramana in intervalul [0, 10^8]?

Ma gandesc ca un sistem in care un anumit utilizator cere voie altui utilizator sa vada sursa ar reduce o parte din probleme. Deci, userul x care a rezolvat o anumita problema de 100 de puncte poate avea 3 optiuni:

-> dau voie tuturor sa vada sursa (sursele) mele
-> userii pot sa-mi ceara sa le arat sursa (default)
-> nu accept cereri

Un alt user, cand intra pe o problema si doreste sa vada sursele va vedea sursele celor care au aprobat acest lucru (prin optiunea 1). De asemenea, va avea o lista a userilor carora le poate "cere" sursa. Ar fi bine ca fiecare user sa aiba afisate statistici (cate surse a cerut, ce probleme, etc.). Acest sistem este destul de asemanator cu "cerutul" surselor pe mess sau pe e-mail, dar ar fi mai confortabil.

Cred ca ar fi multi utilizatori care ar fi foarte de acord sa isi faca toate sursele publice si astfel nu am obliga pe nimeni in nici un fel.

Wefgef.. o comunitate ramane comunitate cand toti, sau majoritatea membrilor sunt multumiti. Nu cred ca e ok sa "vinzi" dreptul de folosire a evaluatorului cu pretul proprietatii surselor. Asta e parerea mea cel putin.

Daca Gigel trece (impreuna cu alti detinuti) printr-o celula in care se afla un detinut, are posibilitatea de a alege daca detinutul il urmeaza?

Bravo Paul!

Multumesc! Felicitari si celorlalti clasati pe primele locuri!

Duminica .. pana atunci mai ascult niste manele si mai bag niste surse!

Eu iti dau un plus ma, ca sa vezi cum reactioneaza oamenii adevarati!