1) Don't forget, that pupils sit in a circle!
2) You have to count how many pupils you can satisfact with choice 'i' boy at first (even he doesn't to be so :-) ). There are algo claimed O(n)
3) If you have such info, it's so easy to calculate the answer ;-)
I can send the solution to your mail.

This algo gets TL too... plz send me code to rockprogressive.s[at]gmail.com

Hi,

Yes the problem can be solved by thinking about it as a voting problem. Consider the following input:

5
3 3 1 5 5

1st student wants 4th student to go first.
2nd student wants 5th student to go first.
3rd student wants 3rd student to go first.
4th student wants 5th student to go first.
5th student wants 1st student to go first.

5th student receives the maximum votes so answer is 5.

Consider another example from the problem test case.

4
4 1 2 3

1st student wants 2nd student to go first.
2nd student wants 2nd student to go first.
3rd student wants 2nd student to go first.
4th student wants 2nd student to go first.

So, the answer is 4.

Another example from a test case taken from elsewhere in the forum:

8
1 2 3 5 5 6 7 8

1st student wants 1st student to go first.
2nd student wants 1st student to go first.
3rd student wants 1st student to go first.
4th student wants 8th student to go first.
5th student wants 1st student to go first.
6th student wants 1st student to go first.
7th student wants 1st student to go first.
8th student wants 1st student to go first.

So the answer is 1.

Edited by author 10.01.2011 04:57

My solution:
Calc b[i] - count of numbers such (n+A[i]-i)%n == i
Then find max_idx - index of maximum element in array b
answer is  (n - max_idx) % n + 1

did you get AC?
I don't think to satisfy most students is right. for example(the one you mentioned):
5
3 3 1 5 5
your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference:
|3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8
but for another sequence:1 2 3 4 5,the difference is:
|3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8.
so as my conclusion, we should make the "displeasure" minimal. if using your method,
maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger.
sorry for my bad English.

did you get AC?
I don't think to satisfy most students is right. for example(the one you mentioned):
5
3 3 1 5 5
your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference:
|3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8
but for another sequence:1 2 3 4 5,the difference is:
|3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8.
so as my conclusion, we should make the "displeasure" minimal. if using your method,
maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger.
sorry for my bad English.

I got AC for voting solution...

i'd rather like this.  cuz it's clear :)

4
4 1 2 3

1st student wants 2nd student to go first.
2nd student wants 2nd student to go first.
3rd student wants 2nd student to go first.
4th student wants 2nd student to go first.

So, the answer is 4.


typo