For problem 4:
When I read the statement, first thing that came in my mind was the Petr's problem from Google Code Jam Round 1A.
 
Let's consider X be the identity permutation of length N, initially.
For every positive integer i, i<= N, we generate a random number j from [i+1, N] and swap X[ i ] with X[j]. Pr(X[ i ] == k) = 1/n, for every i,k positive integers, i,k<= N.

I have an idea for first problem, it's an adaptation of Mihai's solution for second problem.
Let's 0 be Tail-Head and 1 be Head-Tail. The probabilities for 0 and 1 are equal, p * (1 - p). We roll the dice twice until we see Tail-Head or Head-Tail. So we ignore Head-Head and Tail-Tail.

8 ) s(n, m) = number of permutations of length n that execute the 4th line exactly m times.
To compute s(n, m) we can consider the s(n-1, m-1) case and put the new element on the first position or the s(n-1,m) case and add the new element on other position.
So s(n, m) = s(n-1, m-1) + (n-1)*s(n-1, m) ( Unsigned Stirling numbers of the first kind)
The expected value is sum ( m * s(n,m) ) / n!, for 1<= m<= n.

I get stuck here, so I tried another approach:

Let's consider Y(i) = max(X(j)), 1<= j<= i, X is the permutation and Z is a random variable where Z(i) = 1 / (number of occurences of Y(i) in Y). sum( Z ) = number of times line 4 is executed for X.
The expected value, E(Z) = sum ( E(Z(i)) ). E(Z(i)) = sum(1/k * P(Z(i) == 1/k) ), for 1<= k<= n. So E( Z(i) ) = 1/n * (1/1 + 1/2 + 1/3 + .. + 1/n) ) = 1/n * Hn.
E( Z ) = n * (1/n * Hn) = Hn.

6) Let's consider p(i) be the probability to draw a new card if I have already i cards.
p(i) = 1 - i / n = ( n - i ) / n, for 0 <= i < n
Let's Ti be a random variable, where Ti(j) represents the probability to pick a new card from j draws if I already have i cards.
Ti(j) = p(i) * ( (1 - p(i)) ^ (j - 1) ) ( geometric distribution )
From the fact that Ti is geometric distributed , the mean ( E(Ti) ) is 1/p.
The expected times you need to draw before having each card at least once is sum( E(Ti) ), for 0<=i<n
sum( E(Ti) ) = n + n/2 + n/3 + .. + 1 = n * (1 + 1/2 + .. + 1/n ) = n * Hn, where Hn is the n-th harmonic number.

Fie D1 dreapta ce contine punctul A1(0,0,0) si are directia v1(0,1,1)
Fie D2 dreapta ce contine punctul A2(0,1,0) si are directia v2(1,-1,0) .
Fie matricea M1 =( ( xA2-xA1 , yA2-yA1 , zA2-zA1 ) , (xv1 , yv1 , zv1 ) , (xv2 , yv2 , zv2 ) )
M2 = ( ( yv1 , zv1) , (yv2 , zv2) )
M3 = ( ( zv1 , xv1) , (zv2 , xv2) )
M4 = ( ( xv1 , yv1) , (xv2 , yv2) )
dist(D1,D2) = abs ( det(M1) / sqrt(det(M2)^2+det(M3)^2det(M4)^2) ) ) = sqrt(3)/3 .
In postul de mai sus (GoldelianH) , am gresit directiile . 

Poti rezolva problema prin programare dinamica

Cod:

	sol[0]=sol[1]=1;
	for(i=2;i<=n;i++)
		for(j=i-1;j>=0;--j)sol[i]=max(sol[i],sol[j]*(i-j));

Testele de la evaluarea partiala coincid cu cele din enunt ?

sol[ i ] = sol[ i-1  ]+ sol[ i-2 ] - 2

La problema de la grupa small am luat 90 de puncte pentru ca am declarat un vector de 300.000 ...dar nu au fost respectate restrictiile si trebuia sa il declar 300001 ... iar la problema de la medium ... m-am gandit ca e de la '-'-ul ala ... adica daca bag un n mai mare decat 9973 imi da o valoare negativa... ma ajuta cineva?  Mihai... cum ma incurca minusul ala? 

Minusul ala te incurca daca a[i-1] e divizibil cu 9973 . Poti face in felul urmator a=(a[i-1]+a[i-2]+9971)%9973 .

Cu un DFS intr-un graf neorientat obtii 100 de puncte.