ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1794. Masterpieces of World Architecture

Very easy solution!
Posted by smolcoder 2 Nov 2010 14:31
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.
Re: Very easy solution!
Posted by Anton Papin 11 Nov 2010 01:58
This algo gets TL too... plz send me code to rockprogressive.s[at]gmail.com
Re: Very easy solution!
Posted by Varun Sharma 10 Jan 2011 04:52
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
Re: Very easy solution!
Posted by ValenKof 10 Aug 2011 02:31
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
Re: Very easy solution!
Posted by jiyujie 15 Apr 2012 09:21
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.
Re: Very easy solution!
Posted by jiyujie 15 Apr 2012 09:22
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.
Varun Sharma wrote 10 January 2011 04:52
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
Re: Very easy solution!
Posted by Marin Shalamanov 13 Mar 2013 18:59
I got AC for voting solution...
Re: Very easy solution!
Posted by staticor 8 Jul 2013 21:52
i'd rather like this.  cuz it's clear :)
Re: Very easy solution!
Posted by staticor 8 Jul 2013 22:01
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