În secțiunile Date de intrare și Date de ieșire, fișierele sunt denumite incorect traseu.in și traseu.out. Ar trebui corectat în traseu3.in și traseu3.out. Sper să vă ajute.

[pages that have been mapped but not used]

Noroc,

Am primit PM despre discuția asta, așa că răspund. Precizez de la început că nu am nicio afiliere cu OJI sau alt nivel de olimpiadă. Ca să nu încep fiecare frază cu „din câte știu eu...”, considerați că tot ce scriu aici este din câte știu eu.

OJI se corectează pe Windows. În schimb, evaluatorul IA rulează sub Linux. De aici decurge o diferență importantă. Iată întâi ce zice „man top” (boldul îmi aparține).

RES  --  Resident Memory Size (KiB)
           The non-swapped physical memory a task has used.
VIRT  --  Virtual Memory Size (KiB)
           The  total  amount  of  virtual  memory  used by the task.  It
           includes all code, data and shared libraries plus  pages  that
           have  been swapped out and pages that have been mapped but not
           used.

Deci în Linux există conceptul de memorie pe care ai declarat-o, dar încă n-ai accesat-o și deci „nu se pune” la o eventuală limitare. Să considerăm următorul program:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)

int main(void) {
  unsigned char v[N];
  while (1) {
  }
  return 0;
}

Dacă îl rulez, merge bine-mersi, iar top zice:

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND     
23954 cata      20   0    4192    356    280 R 100.0  0.0   0:49.77 test        

Pare deci că kernelul a mapat cumva doar 4 MB, iar programul folosește efectiv 356 KB. Să încercăm acum:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)

int main(void) {
  unsigned char v[N];
  int i;
  for (i = 0; i < N; i++) {
    v[i] = 111;
  }
  while (1) {
  }
  return 0;
}

Acesta dă segfault. Pare deci că programul chiar cere acei 100 MB pe stivă, ceea ce nu se poate. În varianta a 3-a facem vectorul global:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)
unsigned char v[N];

int main(void) {
  int i;
  for (i = 0; i < N; i++) {
    v[i] = 111;
  }
  while (1) {
  }
  return 0;
}

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND     
24061 cata      20   0  106592 102788    312 R 100.0  1.3   1:22.81 test        

Aici într-adevăr programul folosește 100 MB (nu știu de ce sunt 106 -- poate din cauza diferenței între 1.000 și 1.024).

În Windows, în schimb, dacă declari un vector static, chiar ți-l alocă. Bineînțeles, nu e normal să folosim Windows la olimpiadă și este regretabil că o generație întreagă de informaticieni de elită, smântâna cremei ca să zic așa, cresc dependenți de software neliber. Dar asta este situația curentă și, în timp ce milităm pentru renunțarea la Windows, lucrăm în contextul dat. Deci ești dator să știi că infoarena pregătește utilizatori adevărați, linuxiști, dar că ce merge pe IA nu va merge la OJI. Te cred că ești nemulțumit și te invit să militezi alături de noi pentru eliminarea Windows-ului din toate fazele olimpiadei (și, dacă se poate, din viețile noastre).

Acum, referitor la măsurarea memoriei. Codul infoarena este liber (mulțumim!) și poți vedea ce face programul jrun în particular. Caută funcția update_from_proc() și vei vedea că, într-o buclă, jrun cere de la sistem date despre câtă memorie folosește programul executat.

De ce așa? Pentru că nu este trivial altfel. Nu există o metodă bună de sandboxing. Ce decurge de aici? Că, dacă faci verificarea în buclă prea des, vei gâtui programul și va ajunge jrun să ruleze mai mult decât programul. Dar, dacă o faci prea rar, riști să măsori incorect memoria maximă folosită, căci poți avea ghinionul să măsori de o parte și de alta a unui vârf.

Cam astea-s contribuțiile mele; evident, corectați-mă dacă aberez.

Noroc,

Testele 2-3 și 5-10 conțin muchii multiple între aceeași pereche de noduri. Sub GNU/Linux, le puteți lista cu:

  cut -f 1-2 -d ' ' grader_test2.in|sort|uniq -d

M-am gândit că poate unele surse se poticnesc de asta.

Numai bine,
Cătălin

+1 pentru jocuri / joculețe. Programarea trebuie să fie o plăcere și dezvoltarea de joculețe este nemaipomenit de distractivă. În diverse etape ale formării mele am implementat un minesweeper, un tetris (inclusiv colaborativ, doi jucători în același pahar), o fugăreală prin labirint 2D, un program de reversi, un program de antișah. Din fiecare am învățat foarte mult, de la rudimente de temporizare, grafică și sunet până la algoritmi avansați (pentru șah -- proof number search, endgame tables, zobrist keys, bitboards etc.).

De când cu Internetul, este ușor să publici multe din rezultate și asta îți dă o satisfacție și mai mare. De exemplu, din joacă în joacă am compilat cea mai detaliată carte de deschideri pentru antișah (nu public link-ul, dar căutați [suicide chess opening book]).

Aveți mulți ani înainte și nu e cazul să vă repeziți la proiecte utile prea curând.

[probabil]

Ca să fac o analogie din The Big Bang Theory, e ok să fii și Howard, nu trebuie neapărat să fii Sheldon. Realitatea e că doctoratul nu e pentru toată lumea. Unii oameni sunt făcuți să fie ingineri software. Invers, unii oameni sunt meniți pentru o viață academică și nu ar putea ajunge niciodată la disciplina și principiile de inginerie software necesare pentru a scrie programe-mamut într-o echipă mare. Eu probabil aș fi putut face un doctorat, dar n-aș fi fost nici pe departe atât de fericit pe cât am fost în industrie. Nu e vorba numai de bani, e vorba și de practicile riguroase pe care le-am deprins la Google și care mă ajută să-mi pun ideile pe Internet.

Mircea a punctat foarte bine ideea cu internship-urile. Merită făcute din timp, ca atunci când ajungeți la răscruce să știți încotro o apucați.

Oooh, oooh, e loc de dat cu părerea? Hop și eu! Am să compar Facultatea de Automatică din UPB cu sistemul universitar din SUA (eu unul am fost la MIT), pentru că sunt cazurile particulare cunoscute mie.

Ca să încep cu concluzia și să nu plictisesc pe nimeni, mai întâi aplicați la universități și pe urmă vedeți voi. Dacă MIT sau Stanford sau altele de talia lor vă acceptă, vă duceți; ar fi nebunie să aveți oferta de la MIT sau Stanford în mână și să nu vă duceți. Știu că la 18 ani lucrurile se văd altfel, dar Cătălin de 31 de ani îi este recunoscător lui Cătălin de 20 de ani că a făcut alegerea asta. Dacă primiți oferte de la școli mai apropiate de nivelul alor noastre, atunci intervin și toți ceilalți factori mai mult sau mai puțin subiectivi.

Și eu sunt de acord că nu e bine să pleci numai ca să poți spune „am făcut facultatea în străinătate”. Automatica este în primul rând bine văzută în afară și în al doilea rând chiar se compară cu multe universități americane, cu excepția celor de top. Acum, ar fi grozav să putem cuantifica aceste afirmații, dar una din problemele Politehnicii este că sunt puține statistici disponibile. Nici datele despre universități din SUA nu sunt chiar publice, dar, dacă dai câteva zeci de dolari, poți vedea statistici ca rata de angajare în primul an după absolvire sau salariul mediu după absolvire sau procentul care continuă cu un doctorat. Nu știu cum se colectează datele astea, dar se colectează. Despre Poli (și din păcate despre multe alte aspecte) românii își cam fac impresii bazate pe două-trei data points, vreun prieten sau rudă sau cunoștință.

Ca metodă de studiu, diferența care mie mi se pare uriașă între MIT și Automatică este conectarea permanentă la lumea academică, exact cum a spus și Mihai. Mai toți automatiștii pe care îi știu, chiar și cei mai eminenți, au terminat Automatica pe principiul minimei rezistențe. Poți să termini facultatea cu 10 pe linie și să nu fi înțeles ce înseamnă să înveți și cât de important este să-ți antrenezi capul dacă ți l-a dat Dumnezeu. La MIT însă, unde numărul teoretic necesar de cursuri era 4 pe semestru, nu știu pe nimeni dintre români care să nu fi luat 5 și uneori 6 cursuri, plus vreun sport pe lângă, pentru că îți dădeai seama că vrei să absolvi în N ani, dar în același timp ți se ofereau atâtea lucruri de învățat și nu voiai să renunți la niciunul. Acolo descoperi că biblioteca este un loc unde mergi de plăcere, nu doar o dată pe semestru cu turma ca să-ți iei manualele. Acolo profesorii sunt prea integri ca să-ți ofere un punct în plus la examen dacă tu le tehnoredactezi 10 pagini din noul lor manual. Acolo seminaristul nu te lasă să copiezi pentru că tocmai s-a certat cu proful (da, mi s-a întâmplat mie). Acolo există propriu-zis o ofertă de cursuri și un sistem pe credite: au ei grijă să iei și N cursuri care nu au legătură directă cu specializarea ta, dar poți alege aceste cursuri dintr-o ofertă de zeci sau sute. Nu-ți place electrotehnica? Nici o problemă, ia algoritmi de aproximație în loc. Nu-ți place fizica? Ia niște probabilități. Cel mai mic curs la care am fost a avut șapte studenți și toți șapte voiam să fim acolo.

Încercați să nu lăsați teama de necunoscut să fie un factor în decizia voastră. Facultatea vine la o vârstă palpitantă, să spunem cam între 19 și 25 de ani. Dacă nici atunci nu sunteți pregătiți să plecați în lume cu două valize, atunci pregătiți-vă pentru un rest al vieții foarte plicticos. Nu uitați că nimic nu este ireversibil. Puteți oricând să vă întoarceți în România, să luați credit pentru ce cursuri ați luat, și să continuați la o facultate românească.

Teoretic, nu există nici o poartă în industrie pe care să o deschidă MIT-ul și care să fie ermetic închisă pentru un automatist (însă în cercetare, lucrurile stau altfel -- Mihai ne poate spune mai bine dacă poți ajunge să lucrezi la PARC sau la AT&T Labs cu o diplomă sau cu un doctorat din România). Practic, apar diverse complicații mondene, în special necesitatea unei vize de lucru, care pentru SUA poate întârzia procesul cu până la un an. O viză de student, continuată apoi cu o viză de lucru, este un drum mai umblat („streamlined” este cuvântul pe care îl caut).

Aspectul financiar este cam așa: munca la o companie străină este pe bani mai mulți, dar se corelează și cu nivelul de prețuri al locului. În San Francisco dădeam cam o treime din salariul net pe chirie, de exemplu. Oricum, viața este decentă, pentru că nici plin de bani nu ești, dar nici timp să cheltui nu prea ai Am trăit doi oameni cu un salariu vreme de câțiva ani și nu ne-am refuzat vreodată o vacanță sau o masă la restaurant, dar nici n-am condus un Porsche.

Gata, mă opresc din scris, că cineva trebuie să mai și muncească în țara asta.

@Cosmin: Baza de date a DEX online ar fi un început bun. Plus cărţi online, http://ro.wikisource.org/wiki/Pagina_principal%C4%83 de exemplu.

srv.diacritice.com este un început foarte bun, dar eu cred că este loc de mai bine. Nu mi-e foarte clar cum funcţionează, dar senzaţia mea este că se bazează pe frecvenţe fixe ale cuvintelor, fără să se uite la context. De exemplu, pare să prefere mereu „sau” faţă de „său” şi nu l-am putut convinge să aleagă „său” în nici un context.

MulÅ£umesc pentru cuvintele frumoase! Nu pot să mint, îmi place când mă vorbeÅŸte lumea de bine. 

Referitor la „ce urmează”, încă nu am un proiect de anvergură la care să lucrez, deşi am nişte proiecte pe ţeavă. Pentru DEX online, mai am câteva idei de importanţă mai mică; de exemplu, vreau să creez o pagină cu un <textarea> unde utilizatorii să poată copia texte fără diacritice, iar sistemul să adauge diacriticele.

ObligaÅ£ii nescrise există, desigur. ÃŽn primul rând siteul trebuie să rămână în picioare.  Pe urmă, trebuie să răspundem, cât de cât prompt, la emailurile primite (mai scapă unele cu săptămânile, dar încercăm să evităm asta). Voluntarii care lucrează la definiÅ£ii ÅŸi lexeme mai descoperă câte un bug sau mai au nevoie de o mică funcÅ£ie în plus, ÅŸi trebuie să mai scriu ÅŸi câtva cod. Practic, deÅŸi am încetat să mai scriu masiv cod pentru DEX online, nu am reuÅŸit să reduc volumul de muncă sub 5 ore pe săptămână. Asta nu este o problemă, ÅŸtiam deja din experienţă că este imposibil să te rupi complet de un proiect după ce lucrezi câţiva ani la el. Ce voiam să spun prin lipsa unor planuri pe termen lung este că, deÅŸi am schiÅ£at mereu planuri de viitor pentru DEX online, nu ne-am impus o dată la care să le materializăm.

Eşecuri au tot fost şi mă întreb unde ar fi ajuns DEX online dacă am fi găsit o soluţie pentru ele. De exemplu, n-am găsit niciodată un al doilea programator pentru site. Am mai primit câte un patch ocazional, dar ar fi putut ajunge mai departe cu un programator „cu normă întreagă” (chiar şi în accepţia DEX online, unde „norma întreagă” alternează săptămâni de 40 de ore cu săptămâni de 0 ore). De asemenea, am avut un succes limitat în încercările de a obţine şi alte dicţionare spre distribuire. Toate dicţionarele existente în DEX online sunt generale, dar ne-ar fi foarte utile nişte dicţionare de jargon (medical, informatic etc.). Din păcate, toate negocierile pe care le-am purtat au avut un succes limitat.

@a: Aşa este... Pe vremuri, când nu aveam decât definiţii din DEX, şi acelea puţine, nu aveam definiţii pentru cuvinte vulgare, pentru că DEX-ul le omite. Şi acele cuvinte reprezentau o fracţiune importantă din căutări. Am învăţat să acceptăm că lumea judecă valoarea unui dicţionar şi după numărul de obscenităţi pe care le cuprinde, plus că e falsă pudoare să te prefaci că un cuvânt nu există în limbă, oricare ar fi el. În timp, am reuşit să găsim destul de multe din ele prin dicţionare mai puţin candide decât DEX-ul. Nu le avem nici azi pe toate, fiindcă multe din ele se află la limita unui dicţionar argotic (în sensul că nu toată lumea le înţelege).

1/5 + 1/25 + 1/125 + 1/625 + ... converge la 1/4