Wednesday, November 20, 2013

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.

No comments:

Post a Comment