TIMUS - 1120 Sum of sequential numbers

Link to the problem on Timus Online Judge

The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know that you know problem statement is straight forward :), so let's talk about solution.
What do I do in a problem like this? I pay attention to range of input. Let's rewrite what problem wants for output :

• N = A + (A + 1) + … + (A + P − 1) 
• N = P*A + 0 + 1 + 2 + ... + (P-1)
• N = P*A + (P-1)*P/2

What does a good teacher do when you are solving a problem? He asks you meaningful questions to lead you to the solution. When a good teacher is not available (most of the times) try to do this favor for yourself, ask yourself meaningful questions about input, so you can understand new aspects of the problem you are solving.

Can we iterate over all possible values for P? or What could be maximum value for P according to range of input? Yes, what is the maximum value of P if N=10^9. If you look at the equations, P would be less than square root of 10^9, about 33,000, that's good, cause if you can iterate over all possible values for P, then A would be known in the equation.
What is value of A if we know N and P? A = ( 2*N - (P-1)*P ) / (2*P) such that : numerator must be positive and numerator must be divisible by denominator, then you can pick maximum value over 33,000 possible values for P.

TIMUS - 1207 Median on the plane

Link to the problem on Timus Online Judge

 This is a Computational Geometry problem. No 3 points lie on the same line and this is a great help about our approach to the problem. Since no three points lie on the same line, if you choose point A there is another point B which line AB divides all points equally. I choose the first point according to dictionary order, then if you can sort other points in increasing order of angle relating to the first point, then the other point would be obvious.

 

As you see in the figure I've chosen point 0 and want to sort other points in the given order(so the answer would be point 4 in this case), Surprisingly the problem reduces to a sorting problem and we know we can sort in O(n log n). We need to write a comparator for two points, I mean we need to identify between two points x and y which one comes earlier in the sorted list?

And how do we write the comparator? If the cross product of vector x-v[0] and x-y is negative then x-v[0]-y are clockwise, otherwise they are counter-clockwise.

At last we use function comp to sort other points.
sort(v.begin()+1, v.end(), comp);

TIMUS - 1036 Lucky Tickets

Link to the problem on Timus Online Judge

First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or second if sum/2 > n*9, in first case we can not divide sum in two parts equally, in second case if we put 9 in all positions we can not make sum/2.

This is a Dynamic Programming problem, state of our dp is : dp[i][sum] which means we are on digit i and we want to make sum, how do we do that? We have to find sub-problems related to this state.
dp[i][sum] = SUM{ dp[i-1][sum-k] for k = 0...9, st sum-k >= 0 }
The base case is that we know dp[0][0] = 1, which means there is one way to make sum of zero with zero digits, and that is nothing! :) ( like combination(0, n) = 1 )

And what is the answer after calculating dp[i][sum]?
The answer is dp[n][sum/2]*dp[n][sum/2] (multiplication principle).

TIMUS - 1017 Staircases

Link to the problem on Timus Online Judge

If you look closely to the structure of different staircases for a specific n, you might understand the recursive structure of them, I mean some staircases have common prefix and from a column their difference starts.
If you are familiar with Dynamic Programming and think about state of the dynamic programming, sooner or later you will find a solution with time complexity O(n^3).
Let's define our state as this : dp[min][rem] which means in this column we are standing at we need to put at least min bricks and we have rem bricks remained to use, so what do we do about this column we are standing at?
We test all possible values for this column -> dp[min][rem] = SUM{ dp[k+1][rem-k], such that k = min...rem } which means for the next column use at least k+1 bricks and you have rem-k bricks remained.
What about the basic state? What is basic state, The state which we know the answer and now more recursion is needed. when rem is equal to 0 or rem is equal to min, there is no need to recur again, the answer to this state is equal to 1.

TIMUS - 1114 Boxes

Link to the problem on Timus Online Judge

After I read the problem statement, I tried to think of a popular technique. First I noticed the number of red balls and blue balls. I tried to fix the number of red balls and blue balls chosen to put in the boxes with two for loops. Now I have n boxes and A1 red balls and B1 blue balls which are the same and must be put in the boxes. Another observation is that the arrangement of red balls and blue balls are not related to each other, so the overall answer is the multiplication of the answer for red balls and blue balls, which is calculated separately.
Let's denote the number of balls in the i-th box with Xi, then the answer for red balls is the number of answers to this equation X1 + X2 + ... + Xn = A1 : st. Xi >= 0. This is a classic problem in combinatorics and the number of solutions to this equation is equal to Combination(n-1, A1 + n-1), the same holds for B1, and the number of solutions for Blue balls is Combination(n-1, B1 + n-1), so for this fixed A1 and fixed B1 the answer is Combination(n-1, A1 + n-1) * Combination(n-1, B1 + n-1).

But there is another Cute combinatorial solution which needs no for loops over the number of red balls and blue balls. Let's add another box, if some balls are not put in the first n boxes, then we put it in the last box. So the answer for Red balls is the number of solutions to this equation : X1 + X2 + ... + Xn + X(n+1) = A : st Xi >= 0. Answer to this problem is Combination(n, A+n), and finally the over all answer is Combination(n, n+A) * Combination(n, n+B).

There is another solution to this problem using Dynamic Programming.
The state to our solution in DP is dp[boxi][a][b], we are on boxi, we have a red balls and b blue balls, we choose how many balls we want for boxi.
dp[boxi][a][b] = SUM{ dp[boxi+1][a-i][b-j]  : such that i=0...a  j=0...b }
and we know dp[n+1][xx][yy] = 1, it means we have filled the first n boxes and there are xx red balls and yy blue balls chosen to be out of boxes :)