Salut,
Ma intrebam daca cineva a mai avut probleme cu acordarea vizei H1B pentru job full-time in SUA anul acesta.
In ultimii ani au fost un numar de cereri record pentru vize H1B, si ma gandesc ca asta e o problema cu care se va confrunta oricine doreste sa se angajeze full-time in state la o companie mare de IT.

Pentru cine nu stie, anul acesta au fost in jur de 233k cereri pentru 65k vize H1B, si s-a tras la sorti cine primeste si cine nu. Aceste vize sunt necesare pentru angajarea full time (nu internship) inclusiv la companii precum Google si Twitter.

Eu personal impreuna cu alti colegi de facultate am avut oferte de la Microsoft US si nu am fost selectati pentru viza, Cei de la MS ne-au oferit in schimb joburi temporare in Canada

A mai patit cineva ceva similar/ sau a gasit vreun workaround?

Salut,

Cel mai bine ar fi sa iti cauti un prof care se ocupe de pregatire pt olimpiada, merge daca gasesti si pe cineva care nu e prof dar care a fost la olimpiade in anii trecuti. Un prof iti poate prezenta informatia crescator ca dificultate, ca sa ai intai baza iar apoi sa faci lucruri din ce in ce mai grele, iti poate face un syllabus personalizat, te poate mentine motivat.

Daca totusi nu ai acces la un prof, cel mai bine ar fi sa te folosesti de: (am incercat sa le enumar in ordine crescatoare a dificultatii)

Aplicatii:
1. TopCoder: Intai si intai ar fi bine sa incepi cu problemele div2 easy de pe TopCoder , faci vreo 20 -25 -> treci la div2 medium etc
FIecare problema de acolo e etichetata in functie de tipul ei: de ex backtracking, recursion, dinamica. Cam asta se cere la clasa a Xa din cate stiu, daca reusesti pana in februarie sa faci cam 50 din fiecare categorie, ar trebui sa n-ai probleme.
2. Arhiva educationala de pe Infoarena, ideea e intai sa faci algoritmii pe foaie sa-i intelegi apoi sa implementezi fiecare algoritm de acolo
Multe chestii de acolo nu se cer la clasa a Xa,
3. Problemele date in anii trecuti la oji/oni clasa IX X . le gasesti la downloads pe infoarena.
4. Ar mai fi si USACO Training Gate, problemele sunt foarte misto organizate acolo

Teorie (asta e tot ce ai nevoie in primul an parerea mea):
1. Tutorialele TopCoder , majoritatea sunt excelente in opinia mea
http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static
2. Cartea Competitive Programming, de Steven Halim (e cam 14$ dar parerea mea ca merita, e o varianta mai scurta a Cormen)
Prima editie o gasesti aici:
http://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp1.pdf
3. Cormen - Introduction to ALgorithms (o pun la sfarsit deoarece e cam intimidanta pt un beginner), Citeste de aici intai si intai capitolele : structuri de date elementare, sortare, algoritmi greedy si programare dinamica apoi treci la capitolele urmatoare doar cand ai nevoie de ceva anume din ele.

Ideea e cand nu intelegi ceva, sa nu pierzi timpul, sa treci la altceva nou si sa revii la ce n-ai inteles mai tarziu

Uitanduma pe leetcode, mi-am amintit iar de aceasta problema, cum ca de un an tot nu stiu sa scot mai bun de N^3 cu un hash, si eu sunt foarte curios cum se face aceasta problema de 100 de puncte
Am gasit un articol http://en.wikipedia.org/wiki/3SUM pe wikipedia care zice ca pentru cazul cu 3 numere nu se poate mai bine decat N^2, asa ca banuiesc ca pentru 5 numere marginea inferioara teoretica e N^3 . Se poate face de 100 cu N^3 si hash sau tre sa schimb total algoritmul ?

Ar fi frumos un banner mare in partea de sus a paginii cu el , sa aiba un aspect solemn si cu cateva citate, cuvinte ale prietenilor lui

Nu l-am cunoscut personal, insa pot sa zic ca realizarile lui m-au inspirat si m-au facut sa imi doresc mai multe realizari de la mine ...

RIP

Pagina cu solutii e blank la anumite concursuri, desi solutiile existau la un moment dat (au fost publicate la vremea concursurilor). De exemplu la problema Jap de la algoritmiada 2009 tin minte sigur ca solutia se gasea pe pagina:
http://infoarena.ro/algoritmiada-2009/runda-2/solutii

Am mai vazut inca ceva straniu, la alte concursuri daca solutiile apar blank si dau edit imi apare textul solutiilor dar neformatat. Solutiile probabil mai sunt in baza de date dar e o problema cu rendarea textului cand se incarca pagina ?

@MciprianM
La o multinationala. Sediu printre altele la NY, Londra, Frankfurt. Clienti mari corporatii din toata lumea. Salarii mari pt RO(am cerut foarte mult pt un fresh graduate cu experienta 0. Si ei mi-au dat cat am cerut).
Dar plafonarea asta nu e doar la ei, io cred ca asa e cam in toate companiile, cel putin in RO. Poate in state la Google & FB o fi altfel, nu cunosc . Dar nici in state nu e totul roz. In postul meu precedent cand ziceam "bisnitar", ma gandeam printre altele la fostul patron Apple.
Cauta pe bestjobs joburile de programator. Sa vezi descrierea joburilor. Dezamagitor

Ma intreb cati de aici au avut pana acum un job serios (i.e. full-time) in programare.

Pe mine titlul postului ma duce cu gandul exact la cum as imparti si eu programarea: in doua categorii antagonice
Prima este a utiliza limbajele si tehnologiile existente deja pentru a realiza produse si unelte care pot fi folosite de oameni obisnuiti in viata de zi cu zi (i.e. site-uri), sau de companii in afacerile lor (i.e. SVN-uri, project management tools etc). Aici conteaza viteza si abilitatea de a scrie cod rapid si functional, nu neaparat optimal dpdv algoritmic,  caci un simplu site poate avea zeci si sute de mii de linii de cod in spate. A doua categorie este cea "teoretica", cea orientata spre algoritmica, unde iti concentrezi efortul spre a intelege concepte matematice din ce in ce mai dificile, a crea legaturi intre diferite obiecte matematice , a descoperi noi proprietati. De exemplu, Graph Theory e o subramura a matematicii, strans legata de combinatorica, problema fluxului maxim este defapt un caz particular al problemei de programare liniara, bazata pe algebra liniara.
Dezvoltarea de algoritmi necesita mai intai modelarea unei probleme teoretice sau din viata reala, apoi intuitie si logica matematica, pentru a gasi euristic o solutie , iar apoi trebuie si demonstrat riguros corectitudinea sa. Iar o simpla modificare a cerintei poate face rezolvarea mult mai grea. (Exemplu: intr-un graf , nu se cere drumul minim, ci al K - lea drum minim, sau graful e dinamic, sau infinit)
Pentru mine informatica este o pasiune pur intelectuala, strans apropiata de a doua categorie. Am caiete pline de numere, grafuri, demonstratii. In schimb cand vine vorba de scris cod "banal", sunt lenes
Problema e ca atunci cand te angajezi full-time la o firma sau multinationala, se cam rupe firul. In primul rand, nu prea mai ai timp sa lucrezi la acel site sau proiect la care lucrai din pasiune. Nu mai exista codat cand ai chef cu laptopu in brate, cu muzica tare in casti. In schimb: overtime si stat la servici chiar daca n-ai chef, stress, proiecte neinteresante, target-uri, corporatisme, sedinte peste sedinte, completare de time-sheets, hartogaraie, rapoarte, daca esti incepator, bug-fixing pe codu seniorilor, "nu conteaza sa fie optim, ci sa mearga si sa fie gata in 2 zile", etc . Iar profitul pe urma muncii tale nu il incasezi tu, ci deseori il incaseaza un "bisnitar"

Am dat si eu bacul la info ( acu 5 ani ce e drept ) si iti pot raspunde la intrebari, desi cei mai in masura cred ar fi sa iti raspunda profii de info de la tine din liceu
1. Aici conteaza peste cine dai la corectura. La foarte multe licee din tara din pacate inca se face Borland Pascal/C++, si poate cine iti va corecta lucrarea a avut contact la clasa numai cu acestea, si implicit cu o versiune mai veche de C++. Din cate imi amintesc, Borlandu pe care il stiu si eu din liceu nu are inclus si STL (s-ar putea sa ma insel). Cel mai bine zic eu ar fi ca sursele sa fie compilabile si in Borland

2. Aici e destul de clar. E bine sa arati ca stii sa implementezi o cautare binara, sau un quicksort (desi bacul nu e olimpiada, si pe vremea mea erau foarte putine probleme de bac care necesitau ceva mai sofisticat decat un bubblesort, sau un backtracking). Eu daca as fi prof as da punctajul maxim celui care si scrie de ex cautarea binara si nu doar o apeleaza din stdlib

3. Daca esti sigur pe tine ca sunt corecte, foloseste algoritmi "mai avansati" (i.e. optimali). Important e sa fie corecte, probabil la bac inca se scrie pe foaie codul, bear in mind ca singurul debugger e foaia si creionul . Nu te aventura la ceva mai greu decat daca esti sigur ca e corect.

4. Vezi 1. si 2.  Poti folosi tablourile din C, int* ,char* , si operatorii new si delete.  O coada o poti implementa ori ca un simplu tablou cu 2 indici, ori ca lista simplu inlantuita. Ia 2 minute maxim in plus de scris. Ideea e ca la structuri de date simple, sa stii sa le implementezi rapid de unu singur. Daca vei vrea sa lucrezi in programare, una din primele intrebari la un interviu va fi implementarea de ex a unei liste, stive sau cozi.

5. Comentariile la cod sunt bune tot timpul. Este un guideline pentru un cod bine scris, mai ales in industria de soft.

Am fost in cls. a 12a la ICHB si pot sa spun ca e o diferenta ca de la cer la pamant intre ce info se face acolo si ce info se face la 95% din celelalte licee din bucuresti. Pe la majoritatea liceelor profii, in mare parte, cunosc doar ce se gaseste in manualul de liceu, de exemplu stiu sa iti explice Dijkstra in N^2, insa nici macar nu au auzit ca se poate face cu heapuri in NlogN, Mai sunt si profi mai buni dar ei pleaca in afara sau se duc sa lucreze la firme ... Ideea e ca pentru un elev, nu e suficient sa ajunga sa ii placa o materie, trebuie sa aiba noroc sa dea peste profi capabili sa vada un potential si sa il pregateasca corespunzator.

Citind despre stopping times si martingale, am gasit o alta rezolvare, sa zicem "proprie" a problemei asteia, insa as vrea sa o pot demonstra si matematic
De exemplu X = 10, M = 12
Observ ca exista siruri de forma CCCPPPCCCPPCCSP ... , unde cu C castig 1, cu P pierd 1. Deoarece nu ma opresc decat cand ajung la 0 sau la M sirurile pot avea lungime finita sau infinita (De exemplu CC e sir valid , la fel si CPCPCPCPCPCPCPCPCPCPCPCP .......... C (infinitate de CP urmat de C)  ) .  Daca sirurile pot avea lungime infinita, atunci multimea jocurilor posibile e infinita.
Observ insa ca pot imparti multimea sirurilor in clase (categorii) disjuncte, de forma

Un sir falimentar are formele:
1) ....... P ......... (nr egal de C si P)  P ...... (nr egal de C si P)  ....  P.     (ajung sa pierd de inca 10 ori fata de cate ori am castigat)
2) ....... C  ....... (nr egal de C si P)  .... P ......... (nr egal de C si P)  P ...... (nr egal de C si P)  ....  P  (castig O singura data, apoi ajung sa pierd de 11 ori fata de cat am castigat)

Un sir castigator are formele:

1)  .......... P .......... C .......... C .......... C ............ C .......... ..... C  (ajung sa pierd de 9 ori fata de cate ori am castigat, apoi castig de unspe ori fata de cate ori am pierdut)
2)  .......... P .......... C .......... C .......... C ............ C .......... ..... C  (ajung sa pierd de 8 ori fata de cate ori am castigat, apoi castig de   zece ori fata de cate ori am pierdut)
....
...
10) ........ C ............. C (ajung sa pierd de 0 ori fata de cate ori am castigat, apoi castig de 2 ori fata de cate ori am pierdut)

Asa observ ca desi am o infinitate de siruri pierzatoare, ele se pot imparti in 2 clase.  Si desi am o infinitate de castigatoare, le pot imparti in 10 clase. Deci probabilitatea de a falimenta pare sa fie 2/(10 + 2) = 1.6666667. Sau pe cazul general max(1 - X/M,0)

Dilema mea e cum pot sa explic ca  multime "infinita" e de 5 ori mai mare decat alta multime "infinita". Desi intuitiv e logic, nu prea stiu cum sa transpun intro demonstratie de teoria probabilitatilor. Mi se pare ca o problema simpla de info de clasa a X a ascunde o matematica mai putin simpla

PS Draguta problema, si poate rezolvarea mea va ajuta pe unii sa o inteleaga mai bine

Sa se sorteze fiecare sir sau toate sirurile?
Daca ti se dau N stringuri de lungime maxim M atunci poti sorta cu quicksort si mai rapid cu sort() din STL. Daca trebuie sa sortezi fiecare 1....N string de lungime M, nu am idee mai rapida decat ai spus tu.

Da, toate sirurile. Pai se poate sorta mai repede decat N*M*logN? sort'u din STL scoate mai putin pt stringuri?
Adica .. nu face tot NlogN comparatii ? Si ca sa compari 2 siruri ar lua O(M).

Si m-ar interesa si ceva materiale utile si succinte despre arbori de sufixe, am gasit si eu articole (art lui Ukkonen) dar sunt mult prea mari si greoaie.

Ok problema ar suna cam asa
Se dau N siruri de caractere Unicode de lungime maxim M ,  N si M <= 1000000. Sa se sorteze crescator in functie de indicele caracterului
Mie imi vine in cap quicksort in  O (N * M * logN), sau eventual un trie , in O(N*M)
Exista ceva mai rapid ?

Salutare,
Am luat si eu 100 la aceasta problema dar tot am o nelamurire.
Daca folosesc euclid extins si inmultesc apoi cu c / cmmdc
De ce tot timpul solutiile se incadreaza in +/-2 miliarde ? pt a si b foarte mari adica, e vreun rationament matematic implicat?  Adica asa se intampla, dar nu imi dau seama de ce

si exista vreo metoda prin care sa  aflu de ex  solutiile ecuatiei ax + by = c de modul minim?

Am si eu cateva intrebari(si observatii) legate de aceasta problema
1) inainte sa pun conditia daca Nr e 1 atunci fals luam 20p, dupa am ajuns la 90
2) trebuie parsata citirea ? inainte sa parsez luam TLE pe 7 teste. Cu parsare scot max 1.8sec. Totusi ar mai trebui optimizat algoritmu sa intre si fara parsare?
3) E ceva special la testul 1 ? Nu-l iau de nici o culoare  
edit: am gasit, pe 2 il vedea ca nr compus lol...

foarte misto problemele, organizarea super bravo

Cam putin totusi primii 10 de la fiecare grupa sa se califice, si de ex am vazut ca multi care s-au clasat bine la o grupa s-au clasat bine si la celelalte.  
Eventual s-ar putea selecta si "de rezerva" in caz ca nu va putea ajunge cineva ...

Tot 90pct iau si ma gandesc la prob asta de ceva timp

Ideea mea e ca la inceput sa inserez toate perechile de sume (i,j) cu i = 3 .. n - 1 si j = i + 1 .. n

Apoi

Cod:

int cnt = 0;
        for(int j=2;j<=N-2;++j)
        {
         for(int i=1; i<j; ++i)
          cnt += count(S - c[i] - c[j]);

         for(int i=j+2;i<=N;++i)
          erase(c[j+1] + c[i]);
        }

Astfel scot per total scot un numar minim de comparatii intre elemente ... corectatima daca gresesc
Ca hash am incercat tot ce se putea ... Open Addressing cu 2 hash, hash dublu, acum folosesc un hash simplu cu metoda inmultirii

Trebuie alta abordare totusi?  Eu pt hash folosesc un vector<int> de 3033 elemente  (la prob hashuri a intrat lejer in timp)
.  Trebuie facut hashul altfel ?  . Am incercat si dimensiuni mai mari ( < 660013) dar merge mult mai greoi 
Deci mai mult de atat nu vad ce as mai putea optimiza la rezolvarea cu hash-uri vorbind , cea cu cautarea binara n-am incercato


edit : am bagat un sort() si am luat 100   Ms Andrei

Vedeti ca pe testul 7  M= 10000 si in enunt limita e 9999,  eu tot luam 90 si nu stiam de ce ...  sa nu mai declare si altii dimensiunile la limita cum am facut yo

Aici la hashuri mai intra super frumos si rapid in timp si problema banana http://infoarena.ro/problema/banana

pt cei ce folositi streamuri si eventual nu luati 100 aveti grija la citire ... ceva genul

Cod:

while(!fin.eof()) 
 fin>>op>>cuv 

poate cauza buguri de ex daca nu gaseste cifre/caractere compatibile sau ajunge la sf fisierului si atunci citirea nu mai are loc si raman vechile valori si algoritmul le foloseste pe acelea / calc de 2 ori pt aceleasi valori ... pt aceasta prob puteti folosi ceva gen

Cod:

if( fin.good() ) { op1() op2() etc}

acest mic detaliu a facut la mn dif dintre 30p si 100p

[edit] e o idee buna sa faci bucatile de cod vizibile folosind tagul "[ code ]"

Cele K prime ale unei subsecvente trebuie sa fie distincte?

Numarul de N - 1 strazi trebuie sa ramana constant dupa fiecare adaugare a unei strazi noi?

Mai dati probleme cu arbori daca mai stiti

Ma gandeam sa fac un articol despre arbori AVL, rotatiile explicate pe indelete, inserari,stergeri, divizari, concatenari (cu algoritmul lui Clark Crane). Daca are cerere, ma apuc sa lucrez la el in limita timpului disponibil

Hai ca am gasit problema Zeap http://infoarena.ro/problema/zeap , am facut cu AVL , mere f bine, scoate max o sec pe ult test

http://infoarena.ro/problema/order

Ar merge cu Treapuri.

Ms , o sa ma apuc si de aia cand o sa am timp

M-ar mai interesa si ceva probleme despre divizari si concatenari de arbori in timp optimal ... 

Salut baieti ,
M -am apucat sa invat mai calumea arbori (imi tre la fac) si m-ar interesa cateva probleme care exista aici pe infoarena , care se rezolva cu arbori binari echilibrati , AVL-uri , treapuri , in special probleme "curate" care sa nu necesite si alti algoritmi foarte avansati .   Asa ca sa nu mai stric tot farmecul probl si sa caut direct in solutii    Miar fi de mare ajutor ms