How To Solve Informatics Olympiad?

How can I solve the questions of Indian national Informatics Olympiad 2012 ? (link provided)

• http://www.iarcs.org.in/inoi/2012/inoi2012/inoi2012-qpaper.pdf. Approach/code/algorithm/thought process/hint. Anything is welcome. There are only 2 problems. If you are a regular competitive proagrammer, you will enjoy them.

• Answer:

  I am giving the approach to both problems since I don't want to rob you of the pleasure of actually solving them! Problem 1 This problem admits a greedy solution. First of all, we can sum up the times for pole-vaulting and donut eating for each participant. So, for each participant we basically have a pair of values [math](x, y)[/math]. Sort the participants according to [math]y[/math]. The participant with the highest [math]y[/math] should be scheduled first and then the next and so on. The proof is quite simple. If you exchange the ordering of any two participants, then the time can never be reduced, it may increase though. Problem 2 Consider the problem when the second row didn't wrap around. The second row would vary from [math]1, 2, 3, ..., n[/math], [math]0, 1, 2, 3, ..., n - 1[/math], [math]-1, 0, 1, 2, 3, ..., n - 2[/math] and so on. Then, I guess it is easy to see the index which results in the maximum doesn't change. Now, lets come back to the original problem. At any given point the 2nd array would be of the form [math]i, i + 1, i + 2, ..., n, 1, 2, ..., i - 1[/math]. Break it into two subproblems, finding the maximum in the first part (the i to n part) and in the second part. Through some careful observations you will be able to update the two maximums efficiently! If you require further hints please comment or message me.