Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativă a concursului prin explicarea detaliată a soluţiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platformă potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul 8, însă am considerat că o atitudine de tip "Las' ca începem de luni, asa se face treaba" n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul "Luni" al Monthly-ului este practic in 2013. Acestea fiind zise, let s get to work.

Runda 8 a avut 91 de concurenţi înscrişi şi 79 de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar 2 concurenţi au terminat concursul având 3 probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We're not quite there yet, dar ne străduim :).

Switch

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu 16 noduri (fiecare matrice posibila) şi 4 arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

Însă această problemă are o soluţie mult mai scurtă, pe care mulţi concurenţi au intuit-o şi au implementat-o. Graful are de fapt doar două componente conexe. În prima se află matricele cu număr par de 1, iar în cealaltă cele cu număr impar. Pentru a demonstra acest lucru, observaţi că o operaţie de negare nu schimbă niciodată paritatea numărului de 1 (De ce?). Faptul că din orice matrice pară se poate ajunge in orice altă matrice pară este destul de evident, în special fiindcă multe dintre configuraţii sunt doar oglindiri/rotiri ale celorlalte.

Prima soluţie este mai flexibilă, iar corectitudinea ei nu depinde niciodată de particularităţile transformărilor sau ale matricelor, putând fi folosita şi pentru matrice de N x N. Ea are complexitate O(2 ^ N * M), unde M este numărul de transformări posibile. Cea de a doua soluţie are însă complexitate O(1) şi se scrie in 2 rânduri.

Cifre3

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motive.

1. Toate numerele trebuie să aibă ca factori primi doar numere din mulţimea 2 , 3 , 5 , 7, deoarece acestea sunt singurele cifre care sunt numere prime.
2. Având în vedere că numărul de cifre este limitat de 20, puterea maxima a lui 2 este limitată de 60 (numărul format din 20 de cifre de 8), cea a lui 3 de 40 , iar cele ale lui 5 si 7 chiar de catre 20.

Deci există maxim 60 * 40 * 20 * 20 = 960 000 de produse posibile. Observaţi că această margine superioară este o supraestimare destul de puternică, având în vedere că exponentul maxim nu poate fi atins de fiecare cifră în acelaşi timp.

Astfel, am putea să variem exponentii pentru fiecare dintre cele 4 cifre prime şi apoi să hotărâm pentru fiecare configuraţie daca se poate obţine dintr-un număr cu lungime între A şi B. Pentru a simplifica problema, observăm că dacă Lmin ar fi numărul minim de cifre necesar pentru a obţine numărul X, atunci pentru orice lungime L mai mare sau egală decât Lmin există un număr de lungime L care îl poate produce pe X. Adăugăm L - Lmin 1-uri in coadă. Pretty simple huh?. Numărul A devine astfel irelevant. Tot ce trebuie sa verificăm pentru un anumit număr X este dacă Lmin(X) este mai mic sau egal cu B.

Acest lucru se poate face printr-o abordare de tip greedy, ilustrată în fragmentul de cod de mai jos, extras din sursa lui Rareş Buhai, primul concurent care a rezolvat problema în timp de concurs.

int getNum(int x)
{	
	int result = 0;
	if (x != 1) ++result;
	for (int c2 = 0; c2 <= 3 * x; ++c2)
		for (int c3 = 0; c3 <= 2 * x; ++c3)
			for (int c5 = 0; c5 <= x; ++c5)
				for (int c7 = 0; c7 <= x; ++c7)
				{
					int minneed = c5 + c7, addmin = 100000;
					for (int k = 0; k <= min(1, min(c2, c3)); ++k)
						addmin = min(addmin, k + (c2 - k) / 3 + (c3 - k) / 2 + ((c2 - k) % 3 != 0) + ((c3 - k) % 2 != 0));
					minneed += addmin;
					
					if (minneed <= x)
						++result;
				}
	return result;
}

Acestea fiind zise, vă prezentăm soluţia lui Mihai Popa, a doua submisie corectă în timp de concurs.

int p = 3,add = 3;
	for ( int i = 2 ; i <= b ; ++i ){
		p += add;
		++add;
	}
	
	fprintf(g,"%d\n",p*p+1);

Demonstraţia o lăsăm ca tema acasă. Extindeţi raţionamentul de mai sus, potrivit căruia numerele de lungime L produc aceleasi produse ca numerele de lungime L - 1 şi, pe lângă acestea, unele noi pe baza celor vechi.
De notat că deşi soluţia lui Rareş (ca şi cea a comisiei..) este mai complexă şi mai greu de codat, are avantajul că necesită un timp scurt de gândire, fiindca este practic un brut. Alegerea unei soluţii nu neaparat eficiente sau scurte, dar care rezolvă problema în restricţiile date este uneori de preferat în dauna unei implementări simple cu idei uşor mai complicate, mai ales într-un concurs de tip Monthly, Codeforces, sau TC SRM.

Culori4

Deci contribuţia problemei ăsteia la concurs a fost o coloană de 0 adaugată în clasament?

Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se presupune ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP-Complete^*, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat :D).

Să rezolvăm o variantă mai simplă a problemei. Să presupunem că nu există două caractere ? alăturate. Astfel, culoarea unui anumit semn de întrebare nu afecteaza colorarea altui semn de întrebare. Putem deci răspunde cu o formula.
ANS = p1 * p2 * p3 * ... pk unde pi este numărul de posibilităţi de a colora al i-lea semn de întrebare.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate celulele albe au doar vecini negri iar celulele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare ? de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare ? numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că K, numărul de ?, este mai mic sau egal cu 18, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât 9, fie cel de semne de întrebare negre este mai mic sau egal decat 9. Obţinem astfel o complexitate de timp O(5 ^ (K / 2) * K).

Triangles

Prima soluţie care ne vine în minte are complexitate O(N log N) şi nu se încadrează în timp. Pentru a ajunge la ea, realizăm ca întotdeauna are sens ca numerele alese să formeze o secvenţă continuă în şirul valorilor sortate. Pentru o anume secvenţă din şirul sortat, putem afla dacă toate cele K elemente din ea sunt bune verificând ca v[i] + v[i + 1] >= v[i + K - 1]. Cu alte cuvinte, verificăm ca cele mai mici două numere sa poată forma triunghi cu cel mai mare dintre ele (acesta este practic cazul limită. Daca vreun alt triplet nu îndeplineşte condiţia asta, atunci nici tripletul acesta nu o va îndeplini). Această idee se implementează foarte uşor, însă sortarea necesită timp O(N log N). Poate dacă parsăm? Nope. Radix sort? Nope.

Soluţia bună are o linie in plus faţă de cea descrisă anterior. Ideea este ca de fapt nu o să avem nevoie niciodată de toate cele N numere pentru a găsi o soluţie printre ele. Este suficient să păstrăm doar primele K * log(2, Vmax) numere. Valoare care in cazul de faţă este egală cu 150 000. De ce? Gândiţi-vă ce înseamnă dacă o anumită secventă (i , i + K + 1) nu reprezintă soluţie. Rezultă că v[i + K - 1] > v[i] + v[i + 1]. Deci V[i + K - 1] > 2 * v[i]. Cu alte cuvinte, cât timp nu găsim soluţie, odată la cel mult K numere, valorile se dubleaza. Dar numerele nu pot fi mai mari decat 10 ⁹, deci numărul de dublări este limitat de log(2, 10 ^ 9), care este aproximativ 30. Astfel complexitatea devine O((K log Vmax) log (K log Vmax)), iar linia despre care vorbeam este

n = min(n , 150 * 1000);

A fox hides in one of eleven holes. These holes are placed in a line. Each night the fox moves from its current hole to a neighboring one, left or right. Each morning you can check one hole. Is there a strategy that makes sure you catch the fox?

Fell free to discuss it in the comment section. If you saw it before, please don't spoil it.

What's the minimum value this Python code can print:

import threading

num_threads = 5
count = 10

counter = 0

def increment(count):
  for i in xrange(0, count):
    global counter
    counter += 1

threads = []

for i in xrange(0, num_threads):
  threads.append(threading.Thread(
                   target=increment,
                   args=(count,)))

for t in threads:
   t.start()

for t in threads:
   t.join()

print counter

The fact that the code is in Python doesn't really matter. Basically you're given 5 threads that each increment an integer variable counter exactly 10 times. The variable isn't guarded by any lock. You can assume that reads and writes to the variable are atomic operations. What's the minimum value the counter can have after all threads finished.

Meet in the middle (sometimes called split and merge) is a clever idea that uses caching to get efficient solutions. Much like divide et impera it splits the problem in two and then tries to merge the results. The benefit is that by using quite a bit of extra memory you can tackle problems of twice the size you could before.

Before we go on I want to mention that the additional problems are the best part of the article. Now let's go through a few applications of the trick.

4sum (popular interview question)

Given A, an array of integers, find out if there are any four numbers in the array that sum up to zero (the same element can be used multiple times). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.

The naive algorithm checks all four number combinations. This solution takes O(N⁴) time.

A slightly improved algorithm brute forces through all n³ three number combinations and efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has O(n³) complexity.

By now, you’re probably wondering how the meet in the middle technique can be applied here. The critical insight comes from rewriting a + b + c + d = 0 as a + b = -(c + d).
Now we store all n² sums a + b in a hash set S. Then iterate through all n² combinations for c and d and check if S contains -(c + d).

Here's how the code looks

def 4sum(A):
  sums = {}
  for a in A:
    for b in A:
      sums[a + b] = (a, b)

  for c in A:
    for d in A:
      if -(c + d) in sums:
        print (sums[-(c + d)][0], sums[-(c + d)][1], c, d)
        return

  print "No solution."

This algorithm has O(n²) time and space complexity. There's no known faster algorithm for this problem.

Bidirectional search

Find the shortest path between two nodes nodes in a large graph, for example the Facebook friendship graph.

img source

The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is k and the average degree in the network is p BFS explores O(p^k) nodes.

A better solution starts from both nodes and sees when the two search frontiers meet. This reduces the number of states explored to O(p^k/2).

The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.

Breaking 2DES

DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie-Hellman. 3DES works around this problem by encrypting the message 3 times using 2 keys.

Let’s see why 2DES is vulnerable. Let Ek be the encryption function using the secret key k and Dk the decryption function using the secret key k. 2DES uses two keys, k and K. Ek(EK(p)) = s does the encryption and DK(Dk(s)) = p does the decryption.

Diffie-Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding Ek(p). Also for the pattern s it uses all the possible keys to decrypt s, Dk(s).
If we find any match in the two sets it means that Eki(p) = Dkj(s) so the secret keys are ki and kj.
The naive brute force algorithm does 2⁵⁶ * 2⁵⁶ iterations going through all possible values of k1 and k2 while this algorithm uses 2⁵⁶ * 56 memory to store all Eki(p) and does 2⁵⁶ work to find a match.
This is quite a bit of space and quite a bit of computation time. But a for a large enough company or country it starts being within the realm of posibility.

The problem DOUBLE the International Olympiad in Informatics 2001 was basically asking to break 2DES for keys of size 24 which is quite feasible.

Discrete logarithm

Given n a prime number and p, q two integers between 0 and n-1, find k such that p^k = q (mod n).

The naive solution goes through all possible values of k and takes O(n) time.

The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.
Let's write k = i[sqrt(n)] + j
Notice that i <= sqrt(n) and j <= sqrt(n).
Replacing k in the equality we get p^{(i[sqrt(n)] + j)} = q (mod n).
Dividing by p^j we get p^i[sqrt(n)] = qp^-j (mod n).
At this point we can brute force through the numbers on each side of the equality and find a colision.

The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

Caveats

Unlike divide and conquer meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.
Bidirectional search can be often replaced by some search algorithm that uses some heuristics like A*.

Additional problems

1. Friend of a friend(interview question) Given two user names in a social network design an efficient way to test if one is a friend of a friend of the other.
2. 6 degrees of separation Given two user names in a social network design an efficient way to test if they are at most 6 friends apart.
3. Equal partition Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity O(2^n/2))
4. Minimal vertex cover Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the graph has at least one node inside the set. (Hint: complexity O(3^n/2))
5. Square fence You're given an array L which represents the lengths of n planks. You have to answer if there's any way to form the edges of a square fence using all the planks without breaking or overlapping them. (Hint: complexity O(4^n/2))
6. 8 puzzle The 8 puzzle is a sliding tile game of 3×3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonally neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the final sorted configuration in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
   
7. 4 reversals We are given two equal length strings S and T. Figure out if we can get string T starting from string S and applying 4 substring reversal operations. (Hint: complexity O(n⁵))

Try to solve them in the comment section.

Andrei Dragus told me an interesting puzzle:

N people play the following game. They stand in a circle. Someone puts a numbered hat on each person's head. The numbers are from 1 to N and they can repeat. Each person can't see the number on his own hat but can see the numbers on all the other N - 1 hats. Each person tries to guess the number on his own hat. If one of them guesses correctly they've won the game. They all say their guess at the same time. Communication occurs before the hats are placed.

1. Prove that the N people can agree on a strategy beforehand such that they can win the game for any hat configuration.

2. Prove that if one of the N people sees just N-2 of the other hats then there isn't any perfect strategy.

Let's discuss the solution in the comment section.

We're starting a series of articles describing tricks useful in programming contests. Please keep the comments in English.

Being flexible and easy to code, the square root trick is pretty popular in the Romanian programming contests community. It even has a name: "jmenul lu Batog" which means Batog's trick :). Bogdan Batog introduced it to a few high school students more than ten years ago and the trick entered romanian coding contest folklore.

The idea is that we can use bucketing or a two level tree as some people call it to improve naive data structures or algorithms. The square root part appears when we minimize the function n/x + x, we'll see more about that later on.

Let’s check out a few problems that explain how the trick works.

Range Sum

Given A, an n elements array, implement a data structure for point updates and range sum queries:
- update(i, x): A[i] := x,
- query(lo, hi) returns A[lo] + A[lo+1] + .. + A[hi].

The naive solution uses an array. It takes O(1) time for an update and O(hi - lo) = O(n) for the range sum.

A more efficient solution splits the array into length k slices and stores the slice sums in an array S.

The update takes constant time, because we have to update the value for A and the value for the corresponding S.
The query is interesting. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one, but for slices completely contained in our range we can use the values in S directly and get a performance boost.

Here is an update example:

In update(6, 5) we have to change A[6] to 5 which results in changing the value of S[1] to keep S up to date.

query(2, 14) = A[2] + A[3]+
               (A[4] + A[5] + A[6] + A[7]) +
               (A[8] + A[9] + A[10] + A[11]) +
               A[12] + A[13] + A[14] 
             = A[2] + A[3] +
               S[1] + S[2] +
               A[12] + A[13] + A[14] 
             = 0 + 7 + 11 + 9 + 5 + 2 + 0
             = 34

def update(S, A, i, k, x):
  S[i/k] = S[i/k] - A[i] + x
  A[i] = x

def query(S, A, lo, hi, k):
  s = 0
  i = lo
  while (i + 1) % k != 0 and i <= hi:
    s += A[i]
    i += 1
  while i + k <= hi:
    s += S[i/k]
    i += k
  while i <= hi:
    s += A[i]
    i += 1
  return s

Each query takes on average k/2 + n/k + k/2 = k + n/k time. This is minimized for k = sqrt(n). So we get a O(sqrt(n)) time complexity query.

This trick also works for other associative operations, like: min, gcd, product etc.

Nearest neighbour

Given a set S of n points and a query point p, find the point in S closest to p.

For uniformly distributed points, a good strategy is to represent the space as a grid and maintain a list of inner points for each cell. For a given query point, we can check the cell the point falls into and its neighbouring cells. For a sqrt(n) * sqrt(n) grid we’ll have one point per cell, on average. On average, finding the point in S closest to p, requires traversing a constant number of cells.

Longest common subsequence

Given two strings A (n characters) and B (m characters), find their longest common subsequence. (eg. The longest common sub sequence for abcabc and abcbcca is abcbc.)

There is a standard dynamic programming solution which uses an array best[i][j] to mean the longest common sub sequence for A[0:i] and B[0:j], computed as below:

if A[i] == B[j]:
   best[i][j] = 1 + best[i - 1][j - 1]
else:
  best[i][j] = max(best[i-1][j], best[i][j-1])

This algorithm takes O(nm) time and only O(n) space, since to compute a row you just need the previous row.
If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state (i, j) you know the previous state in the solution. The longest sub sequence corresponds to a path from (n-1, m-1) to (0, 0) on the parent matrix. This solution takes O(nm) space.

Let's try to use less memory. We solve the problem once and save every kth row from the best matrix and from the parent matrix.
We can start from the last saved row to compute the solution path from row [n/k] * k to row n - 1. Then we go downwards to compute the part of the solution between the row ik and the row (i+1)k . Computing part of the path between row ik and row (i+1)k takes O(km) space and O(km) time. Computing the whole path takes O(n/k (km)) = O(nm) time and O(km) space. Saving the first pass rows takes O([n/k]m) memory. Again, we minimize total memory usage by using k = sqrt(n). This solution takes O(sqrt(n)m) memory.

Caveats

There are more efficient solutions for the previous problems, but those are a bit more involved. The square root trick has a good balance between added complexity and algorithm speedup.

Additional problems

1. (Josephus Problem) n people numbered from 1 to n sit in a circle and play a game. Starting from the first person and every kth person is eliminated. Write an algorithm that prints out the order in which people are eliminated.
2. (Level Ancestor) You are given an tree of size n. ancestor(node, levelsUp) finds the node’s ancestor that is levelsUp steps up. For example, ancestor(node, 1) returns the father and ancestor(node, 2) returns the grandfather. Implement ancestor(node, levelsUp) efficiently. ( O(sqrt(n)) per query)
3. (Range Median) You are given an array of size n. Implement a data structure to perform update operations a[i] = k and range median operations efficiently. The range median query, median(l, r) returns the median element of the sorted subsequence a[l..r]. O(log(n)) per update and O(sqrt(n)log(n)) O(sqrt(n)log(n)log(U)) per query

Hope you've enjoyed it!
Try using the trick to solve Range Median and the other problems in the comments section.

Cosmin Gheorghe este unul dintre starurile olimpiadei de informatica avand rezultate impresionante (2 medalii de aur si una de argint la olimpiada internationala). Este student al prestigioasei universitati Massachusetts Institute of Technology. Cosmin face pe durata verii un internship la Twitter dupa ce anul trecut a facut unul la Google. El contribuie activ la educarea urmatoarei generatii de olimpici propunand probleme frumoase si fiind implicat in echipa infoarena.

Cum ai inceput cu informatica? Dar cu concursurile?

Cu informatica am inceput din clasa a 5-a. Atunci tocmai incepusem gimnaziul la Tudor Vianu si aveam si ore de informatica la clasa. La inceput eram total pierdut in clasa si nu intelegeam nimic din ce se intampla. Era o materie foarte diferita de celelalte si nu eram deloc obisnuit cu modul de gandire. Din acest motiv am decis ca trebuie sa lucrez singur o perioada macar sa pot intelege cat de cat ceva. Aveam o culegere cu probleme de gimnaziu care ne-a fost recomandata de profesor. Mai intai am inceput sa ma uit peste problemele rezolvate si am incercat sa inteleg rezolvarile. In timp am ajuns sa rezolv singur probleme noi si a inceput sa imi placa modul de gandire.

La concursuri am ajuns pentru ca profesorul a observat ca devenisem oarecum bun la rezolvat probleme si mi-a spus ca poate ar fi bine sa particip la olimpiada. In clasa a 5-a am participat doar la olimpiada dar din clasa a 6-a am ajuns sa particip la tot felul de concursuri prin Bucuresti.

Cum te antrenai pentru olimpiade? Aveai un program fix/sanatos? Ce te motiva sa lucrezi?

Trebuie sa recunosc ca in gimnaziu nu m-am antrenat niciodata serios pentru olimpiade. Era mai mult ca un hobby. Pur si simplu imi placea sa rezolv probleme si sa invat lucruri noi si faceam asta in timpul liber. Cu toate acestea am fost la niste cluburi de informatica care m-au ajutat foarte mult pentru ca aveam pe cine sa intreb. In orice caz in gimnaziu nu consider ca am avut rezultate extraordinare, mai ales ca singurul premiu la nationala am reusit sa il obtin abia in clasa a 8-a si atunci am iesit al treilea.

Am inceput serios sa ma antrenez pentru olimpiade dupa ONI-ul din clasa a 8-a cand am fost destul de dezamagit ca nici atunci nu am reusit sa iau premiul I. Imi doream foarte tare sa reusesc si eu sa ies primul la nationala, dar ce-i drept, nu am lucrat niciodata serios pentru asta. Lucrul asta m-a motivat foarte tare si dupa testarea nationala mi-am dedicat aproape intreg timpul pentru antrenament. Pana la ONI-ul din clasa a 9-a am avut un program foarte serios: ma culcam aproape in fiecare seara la 10-11 seara si ma trezeam la 6-7. Pe langa iesit in oras cam la doua zile cu prieteni si niste activitati fizice (mers la sala, alergat, etc.) imi petreceam tot timpul rezolvand probleme pe infoarena si participand la concursuri. Nu prea imi dau seama cum am reusit sa fiu atat de motivat in perioada aceea, dar dupa clasa a 9-a nu am mai reusit vreodata sa revin la un asemenea program. In clasele care au urmat am lucrat mai putin si mult mai neregulat, dar cred ca in medie 4-5 ore pe zi tot lucram.

Conteaza mai mult antrenamentul pe cont propriu sau ajutorul unui profesor? Care e ponderea ? Ce persoane au avut o influenta in formarea ta?

Ambele conteaza destul de mult. Nu pot sa spun un raport exact. Personal consider ca e mai important antrenamentul pe cont propriu dar ajuta extraordinar de mult sa ai ajutorul unei persoane care sa te indrume. Cu materialele care sunt astazi pe net de unul singur poti invata destul de multe daca te antrenezi serios, dar daca nu lucrezi singur suficient nu conteaza cati profesori ai si cat de buni sunt. Personal eu am avut cam doua faze. Pana sa ajung la ICHB in al doilea semestru al clasei a 9-a, am lucrat foarte mult singur (cel mai mult de pe infoarena). La ICHB am dat de oameni cu multa experienta in domeniul concursurilor si problemele pe care le lucram la pregatiri erau de multe ori suficiente sa ma tina ocupat tot timpul. Eu consider ca rolul cel mai important al unui profesor este sa iti arate ce trebuie invatat, care sunt problemele bune care merita lucrate si sa iti explice lucrurile pe care nu le intelegi de unul singur. In mare parte profesorul iti optimizeaza antrenamentul sa fii cat mai eficient posibil. In rest totul depinde de tine sa depui efortul necesar sa lucrezi si sa intelegi cat mai multe.

Persoanele care au avut cea mai mare influenta in formarea mea sunt: Dan Grigoriu - profesul din clasa a 5-a pentru ca a reusit sa insufle entuziasmul lui pentru informatica mie (calitate mai rar intalnita intre profesori), Mariana Kisch - profesoara de la clubul la care am fost in clasele 7,8,9, si apoi profesorii pe care i-am avut la ICHB: Mircea Pasoi, Silviu Ganceanu, Mugurel Ionut Andreica, Mosoi Alexandru, Sorin Stancu Mara... (sper ca nu am uitat pe nimeni; imi cer scuze daca am omis pe cineva).

Pe langa totate astea e foarte important si grupul de prieteni cu care poti vorbi. Prietenii cu care am putut discuta despre probleme si concursuri m-au ajutat foarte mult pe parcursul timpului. Un grup de prieteni motivati poate usor tine locul unui profesor, odata pentru experientele impartasite in cadrul grupului din care toata lumea poate invata si pentru competia amicala interna ce se formeaza.

Cum iti stapaneai emotiile in timpul concursurilor? Cat conteaza psihicul la olimpiade?

Interesanta intrebare. Au fost multe cazuri cand am pierdut mult timp in concursuri sau am fost neatent la unele lucruri pentru ca eram prea agitat, enervat, grabit, ingrijorat sau stresat ca nu ma prindeam la vreo problema sau nu gaseam bugul intr-o sursa, etc. E destul de greu sa te stapanesti cateodata si nu stiu exact cum este cel mai bine de procedat in cazurile astea. Cred ca cel mai important e sa ramai calm tot timpul si sa te concentrezi cati poti de bine la ce ai de facut, indiferent de cate probleme ai rezolvat si cat timp mai e. Pana la urma daca te agiti sau te ingrijorezi cel mai probabil o sa iti fie si mai greu sa rezolvi ce ai de rezolvat si mai mult timpi o sa pierzi. Eu inainte sa inceapa concursile, ma calmam si ma linisteam incercand sa dorm pe masa pana veneau subiectele (mereu speram ca poate chiar reusesc sa prind cateva minute de somn inainte de proba :). Dupa aceea, incercam sa raman concentrat pe ce am de facut si sa nu ma ingrijorez prea tare de timpul ramas sau de faptul ca nu iese cine stie ce problema (bineinteles, era mult mai simplu de facut asta cand ieseau probleme decat atunci cand nu ieseau :)).

Ce faci/ce faceai in timpul liber ?

Ieseam in oras cu prietenii, incercam sa ma mentin activ (mergeam la sala, mai alergam, jucam ping-pong din cand in cand, etc.), mergeam la filme, jocuri pe calculator din cand in cand, etc. Nimic interesant sau special aici :)

Cum ai ajuns la MIT? De ce n-ai ales o alta facultate? Cum e viata acolo?

De prin gimnaziu visam eu la MIT, apoi pe la sfarsitul liceului am zis ca nu mai aplic in afara ca e prea mare bataia de cap (cu saturile si aplicatiile si toate cele), dar m-am razgandit din nou si am zis ca nu prea e nimic de facut in tara la facultate si cu siguranta ar fi mai bine sa plec afara. Nu stiu exact de ce am ales MIT-ul si nu alta facultate. Doar ca stiam eu din auzite ca e cea mai tare pe engineering asa ca de ce nu? Parea locul ideal pentru o persoana careia ii plac stiintele in general. In plus, MIT a fost singura facultate care m-a aceptat :)) (am aplicat si la Brown si Stanford). Oricum, un sfat pentru toti cei care sunt in dubii sa aplice in afara sau nu si motivul pentru care nu vor sa aplice sunt SAT-urile si aplicatiile: SAT-urile sunt foarte simple. Eu am dat matematica si fizica si a fost foarte simplu. Daca inveti la fizica o saptamana e de ajuns (si eu nu am invatat cine stie ce fizica in scoala), si la matematica doar trebuie sa te antrenezi pe niste examene ca sa intelegi cum merge. Mai greu putin o sa fie la engleza dar nici aia nu e prea grea (cu cateva saptamani de antrenament ar trebui sa fie destul de usor de luat 700+). Cu aplicatiile e putin mai complicat dar si ele pot fi facute destul de usor. Conteaza totusi sa va ganditi serios la ce scrieti acolo pentru ca e important. Pentru aplicatia de MIT cred ca m-am tot gandit 2 luni care ar fi cele mai bune povesti de scris (o sa fie cateva intrebari despre voi si trebuie raspuns in 300-500 cuvinte) si in care ar fi cel mai bun mod in care sa le prezint. La celalalte doua am stat cateva zile si am scris ceva acolo; probabil de aia m-au acceptat doar la MIT.

Despre viata la MIT nu stiu exact ce sa spun. In mare parte e mult de lucru pentru teme si examene. Daca e sa mai faci si altceva pe langa scoala e si mai mult de lucru :). Dar in rest sunt o multime de oameni de treaba si prietenosi cu care sa iti petreci timpul si sa discuti tot felul de lucruri. Ai foarte multe posibilitati sa faci orice (de la tras cu arcul la roboti) si ai sansa sa comunici cu profesori foarte renumiti. Depinde doar de tine sa iti dai interesul sa faci ceva.

Am vazut multe probleme misto propuse de tine. Urmezi niste pasi sau pur si simplu iti vine ideea ?

Nu e foarte simplu sa scoti probleme. De obicei incep sa ma gandesc la ce as vrea o problema sa ceara oarecum luand in calcul cum as vrea sa fie rezolvata (daca sa fie dinamica, ceva cu grafuri, geometrie, etc.). Apoi pur si simplu dau random cat de bine pot pe cerinte pana iese ceva care merita rezolvat. Cateodata iese repede, cateodata deloc :). Astea sunt problemele facute de la 0 de mine. Cateodata mai modific probleme vazute deja intr-un mod in care mi se pare interesant.

Ce planuri de viitor ai?

Ar fi super daca as putea sa iti raspund cu certitudine la intrebarea asta :)). Deocamdata trebuie sa termin facultatea. Inca ma mai gandesc la ce urmeaza dupa.

Ce crezi ca ar trebui facut pentru a crea si alte centre in tara in afara de Bucuresti?

E o discutie serioasa aici. Probabil s-ar putea face un intreg thread pe forum despre asta. Personal, consider ca sunt doua lucruri importante aici: facultatile si fondurile. Bucurestiul este un loc unde gasesti oameni care pot pregati elevi pentru olimpiada pentru ca majoritatea studentilor buni vin la Bucuresti la facultate. Daca in schimb studentii ar prefera sa mearga la facultati din Iasi sau din Cluj ar fi si acolo centre de pregatire (si se intampla asta dar nu la fel ca in Bucuresti).

Apoi sunt importante fondurile. Este necesar sa ai licee care sunt dispuse sa plateasca oameni care sa antreneze elevii. Trebuie sa fim realisti totusi si sa intelegem ca trebuie sa oferi ceva unui student sa prefere sa vina sa iti pregateasca elevii in loc sa iasa in oras cu prietenii; ar fi frumos din partea lui daca ar face totul voluntar dar pana la urma fiecare trebuie sa isi vada si de lucrurile lui. Ar mai intra in discutie si profesorii de la scoala aici, dar din pacate sunt foarte putini capabili sa antreneze elevi la nivel de olimpiada. Aici e o problema intreaga cu sistemul de invatamant si nu vreau sa incep o disputa, dar cred ca si aici sunt importante fondurile (multi prefera sa lucreze la companii in tara sau afara decat sa fie profesori). Nu e usor de rezolvat problema fondurilor, dar e consider ca atat timp cat liceele nu prioritizeaza cat de cat pentru a obtine fonduri pentru a antrena elevi, nu se vor forma organic centre puternice in alte parti ale Romaniei, mai ales in situatia financiara curenta.

Ce sansa le dai celor care nu sunt din Bucuresti sa ajunga ca si tine?

Sunt o multime de resurse online in ziua de astazi de unde se poate invata foarte usor. Singura problema e ca poate sunt prea multe si nu sti exact de unde si ce sa lucrezi sau sa inveti. Pentru asta e foarte util sa gasesti pe cineva care sa iti spuna cam ce e important de facut. E mai greu sa gasesti o astfel de persoana depinzand de unde te afli, dar prin email si pe infoarena sigur se pot rezolva lucruri. Apoi daca ai parte de un grup de prieteni pasionati, puteti incerca sa va ajutati reciproc: de exemplu fiecare poate rezolva anumite probleme si apoi fiecare explica solutiile celorlati; in felul acesta se poate acoperi un numar de probleme mult mai mare decat se poate individual. Daca esti serios si lucrezi poti sa ajungi sa faci bine la olimpiade oriunde te-ai afla.

Povesteste despre internshipurile pe care le-ai facut. Cum au fost experientele si ce cunostinte invatate la concursuri sau in facultate s-au dovedit utile?

Vara trecuta am fost la internship la Google si vara asta fac un internship la Twitter. La intershipuri propriu-zis lucrezi la un proiect. Trebuie sa citesti cod deja existent si sa il intelegi si ori sa modifici codul deja existent ori sa creezi ceva nou care sa se lege cu codul deja scris. Nu prea o sa folosesti vreun algoritm de olimpiada la internship din pacate. Poate o sa mai faci un bf sau ceva dar nu cred ca o sa codezi vreodata un arbore de intervale. Cu toate astea, toate concursurile de algoritmi la care ai participat te ajuta foarte mult la interviuri. Eu unul nu sunt genul de software engineer care sa stie tot ce se intampla cu tehnologiile web si alte lucruri de genu. In afara de c++, nu stiu bine vreun alt limbaj si nici la OOP nu pot sa zic ca stralucesc. Cu toate astea am reusit sa trec de toate interviurile pe care le-am dat pana acum pentru ca am rezolvat aproape toate problemele de algoritmi pe care le-am primit la interviuri. Au fost chiar cazuri cand, dupa ce am rezolvat o problema, am fost intrebat cum as face un server care sa serveasca raspunsurile si am spus ca nu stiu pentru ca nu am facut niciodata un server (cu toate astea am trecut interviul :). Majoritatea problemelor primite la interviuri sunt cam de nivel de clasa a 10 de ONI (foarte rar ceva mai complicat). Structuri de date complicate nu o sa folosesti mai niciodata (hashurile sunt de baza). Pe langa asta niste probleme mai deschise unde trebuie sa iti dai cu parerea la ce ar putea merge si ce nu prea ar merge. In general experienta din timpul concursurilor ajuta foarte mult pentru ca trebuie sa gasesti o solutie cat mai aproape de cea optima in timp limitat. Pe langa asta daca mai sti si altceva pe langa algoritmi, e foarte bine.

Multumim pentru interviu! Daca aveti intrebari, Cosmin va va raspunde in sectiunea de comentarii.

I'm trying out an experiment. I'll write a few blog posts in English and I ask you to use English in the comments. Hope it goes well.

Here's a synchronization puzzle that's somewhat classic but very neat:

You are one of P recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
I have set up a “switch room” which contains a light switch, which is either on or off. The switch is not connected to anything.
Every now and then, I will select one prisoner at random to enter the “switch room.” This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.
Each prisoner will visit the switch room arbitrarily often. More precisely, for any N, eventually each of you will visit the switch room at least N times.
At any time, any of you may declare: “we have all visited the switch room at least once.” If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!
* Devise a winning strategy when you know that the initial state of the switch is off.
* Devise a winning strategy when you do not know whether the initial state of the switch is on or off.

As always, if you've seen the puzzle before please don't spoil it.

O colectie de abtibilduri contine n tipuri diferite. Fiecare plic are probabilitatea 1/n de a contine oricare dintre cele n abtibilduri. Care este numarul mediu de plicuri cu abtibilduri ce trebuie cumparate pentru a obtine intreaga colectie.

Discutati problema in sectiunea de comentarii. Cei care ati vazut-o inainte, nu stricati placerea celorlalti.

Tocmai te-ai angajat, ai trecut prin etapa obligatorie de "orientare", ai intalnit in 10 minute 50 de oameni si ai retinut 2 nume, ai primit un birou si un calculator si acum e momentul sa faci unul din lucrurile care iti vor simplifica viata si te vor ajuta sa fii mai productiv: "get the right tool for the right job".

Poate unii dintre voi care lucrati de ceva vreme ati observat ca cei mai vechi in bransa au tool-urile lor care sunt intotdeauna la o apasare sau o serie de comenzi in terminal distanta. Venind de pe bancile facultatii nu am realizat multa vreme importanta acestor scule dar intr-o zi m-am trezit avand urmatoarea discutie cu un coleg mai vechi in bransa:
El: din momentul asta eu nu mai vin la tine la calculator sa te ajut sa debughezi.
Eu: de ce ?
El: Pentru ca tu nu ai sculele necesare.

Mi-a luat ceva timp pana le-am strans si am invatat sa le folosesc intr-un mod relativ decent dar de atunci nu am mai avut aceasta discutie si sincer sunt mult mai productiv.
In felul asta am ajuns la ideea acestui articol care sper sa fie util pentru voi. Daca aveti alte tool-uri pe care le folositi poate puteti sa sharuiti si cu noi restul.

Asa ca fara alta multa vorbarie sa trecem la chestii mai serioase :

1. OS : aici e o zona tricky si nu vreau sa pornesc un flame war asa ca bare with me: am trecut de la Windows pe care l-am schimbat in momentul in care trebuia sa-mi instalez 2 servere de jboss pe aceeasi masina si setup wizard-ul ma enerva la culme, apoi Linux ( Ubuntu) care e a naibii de bun pentru development dar care m-a dezamagit la fiabilitate si uzabilitate ( crapa X-ul o data la 2 zile, daca foloseam 2 monitoare nu era chiar foarte friendly samd ) si intr-un final am ramas pe Mac OS X. Multa vreme am cam strambat din nas la ideea de Mac dar dupa ceva vreme a ajuns la concluzia ca e mix-ul perfect intre usabilitatea Windows-ului si mediul developer friendly din Linux. Asa ca daca puteti acordati-i o sansa. Nu veti fi dezamagiti.
2. IDE : alegeti unul si nu-l schimbati. Nimic nu e mai anti-productiv decat sa-ti schimbi IDE-ul dupa ce te-ai obisnuit cu el. Invatati scurtaturile pe care vi le pune la dispozitie, invatati tool-urile pe care le are si folositi cat mai mult din ce va ofera. Pentru ca scriu in cea mai mare parte a timpului Java si pentru ca restul echipei foloseste acelasi IDE am ajuns la IntelliJ Idea dupa o lunga perioada de Eclipse. Bun Eclipse-ul dar parca mai bun IntelliJ-ul. Oricum e o chestie de gust pentru ca tool-ul pe care il stii e cel mai bun.
3. Editor de text: poate veti spune "Daca am IDE ce nevoie mai am de editor de text?". De multe ori vei edita fisiere de configurare, vei citi loguri si vei face alte 100 de operatii care sunt prea heavy weight pt un IDE. Pick VIM or Emacs. Din nou, stati pe el pana cand ajungeti la un nivel de power user. Recompensa o sa merite investitia. O chestie simpatica pe Mac este MacVIM
4. Daca lucrati pe Linux/Mac OS X poate merita sa va uitati la ZSH ca inlocuitor pentru bash. Un link util . Are o gramada de mici detalii care-ti fac viata mai usoara: completion pt directoare si fisiere, istoria sharuita intre terminale, shortcut-uri pt diverse actiuni/comenzi. Plus o chestie de gust: are teme care-ti modifica command prompt-ul pentru a oferi mai multe informatii ca branch-ul de Git pe care lucrati, full path-ul curent. Nu exagerati totusi cu "infrumusetarea", nimeni nu are nevoie sa-si vada in terminal nivelul de baterie ramas. :). Si tot pe Mac s-ar putea sa va interseze ITerm2 ca inlocuitor pentru Terminal. Parca e putin mai polished, putin mai utilizabil, putin mai productiv.
5. Daca tot suntem aici poate o tema ca Solarize pentru vim/zsh/IDE. V-ar face terminalul mai placut.
6. Folositi GIT. Permiteti-mi sa repet: folositi GIT. Si daca tot folositi GIT merita sa va uitati pe repository-urile de dot files care sunt peste tot pe net. Dot file-urile, pentru cei care nu stiu, sunt fisiere de configuare pentru shell/vim/emacs etc. Internetul e plin de oameni care si-au customizat shell-ul sau editorul de text si pe care le puteti folosi ca inspiratie. Un tutorial decent. Chestia buna la a face asta este ca daca va crapa computerul sau lucrati pe mai mult de o masina puteti sharui toate setarile intre masini/ sa faceti un restore.
7. Uneori va trebui sa controlati mai multe masini simultan. Nu prea are rost sa repetati comenzile de 5 ori asa ca o recomandare ar fi cSSHX sau versiunea de linux cssh. Cluster SSH e un tool simpatic care iti va deschide mai multe terminale peste ssh pe toate masinile si va replica toate comenzile.Te salveaza de o groaza de timp pierdut si bataie de cap si il puteti gasi aici
8. Daca lucrati pe Linux toate tool-urile care vin by default cu sistemul ar trebui sa va fie prieteni buni: grep, find, sed, cut, awk . Use them wisely. Fie ca parsati niste loguri cautand evenimente, fie ca cititi codul sursa ( apropo read this ) these tools are the way to go.
9. Si cand tool-urile de la punctul 8 nu vor fi deajuns ... python to the rescue. Dar asta e subiect de conversatie pentru alta data.
10. Daca scrieti aplicatii web mai sunt 2 chestii pe care trebuie sa le folositi : Charles pentru a sti exact ce goes over the wire ( evident daca sunteti un pic mai hardcore Wireshark e o alta varianta). Iar a doua chestie este fie Firebug pentru Firefox fie developer tools din Chrome/Safari daca aveti treaba cu HTML/CSS/JS.
11. [ LE ] O scula buna pentru diff intre fisere/directoare e iarasi de mare ajutor. Variantele care vin cu sistemele de operare( opendiff pt Mac, diff pt Linux ) sunt ok dar cumva eu tot ajung sa am instalat pe sistem fie Meld fie Araxis Merge. Nash Mit amintea in comentarii si de Beyond Compare pentru Windows.

Daca aveti comentarii sau alte idei please share them.

Razvan