552A - Vanya and Table For each rectangle she adds ,the value of all the cells in that rectangle is increased by one. Hence it is obvious that if a rectangle of side n*m is added ,the ans increases by n*m

for each rectangle

scan(x1)

scan(y1)

scan(x2)

scan(y1)

ans=ans+(x2-x1)*(y2-y1)

Time ComplexityO(n)

552B - Vanya and Books By number of digits the question means the total number of digits.

Hence number of digits for 1=1

number of digits for 10=2

number of digits for 100=3

We need to write all numbers from 1-n We find the number of digits in n (lets call it k).

Ans=(the number of digits in all 1 digit numbers)+(number of digits in all 2 digit numbers)+...(number of digits in all k-1 digit numbers)+number of digits from 10^k to n.

As the number of p digit numbers = 9*pow(10,p-1)

for(i from 1 to k) ans=ans+i*(9*pow(10,k-1))

And finally ans=ans+(n-pow(10,k-1)+1)*k

Time ComplexityO(log(n))

552C - Vanya and Scales The problem is a simple case of recursion.We have weights of the form w^k(0<k<100). if there exists a combination of weights that forms the mass M , then

M=summation(w^k1)-summation(w*k2)

Hence M has to be of the form w*t+k (-1<=k<=1)

t also has to be of the form w*t1+k1 (-1<=k1<=1)

Hence the recursion continues . The base case is when t<w.The answer will be yes if t=w-1||t=1||t=0

Time ComplexityO(log(M))

552D - Vanya and Triangles

The problem can be solved by a simple brute force for all the points in pairs of 3.If the area of a given pair of 3 triangles is not zero , then it is a possible triangle.

for(i from 0,n-1) - for(j from i,n-1) - — for(k from j,n-1) - — — if (area (i,j,k)!=0) - — — ans++;

Time ComplexityO(n^3)

The problem can however be solved in n^2 complexity.By iterating over all points in pairs of 2 , we can store their slopes in a map.

Then on iterating over the map we can find the number of triangles which wont contribute to the answer.

for(it in map)

• not += (it*(it-1)*(it-2)/6)

answer=n*(n-1)*(n-2)/6-not

Time ComplexityO(n^2)