Here is the problem which was baffling me for quite some time :
http://acm.timus.ru/problem.aspx?space=1&num=1794
The problem description is quite clear. In summary, there are students sitting in a circle and a teacher would be asking each of them some questions which are part of a test. Each student has their own choice as to when they would like to go give the test. The teacher will ask questions in clockwise order only and can start from anyone of them. The choices of the students are represented as this:
4 (number of students)
4 1 2 3 (their choices)
This means:
1st student would like to give the test at 4th position.
2nd student would like to give the test at 1st position. (He wants to go first, may be he is well prepared !!)
3rd student would like to give the test at 2nd position.
4th student would like to give the test at 3rd position.
In this case the teacher should start asking questions from the 2nd student because then each one of them will get the choice of their own, like this (remember that the students are sitting in the circle)
4 1 2 3
4th 1st 2nd 3rd
First Approach
Since I already knew from others the problem has an O (n) solution, I straightaway went looking for that. At first I thought we might need to look for longest increasing continuous sequence of numbers and that might be the answer. So in the above the longest increasing sequence is 1 2 3 and then 4 as all students are sitting in a circle. I drew out some cases and it failed there.
Second Approach : O(n^2)
Then I went for brute force approach. Start at every position and then see for which one you get the most correct positions. So for the above input:
4 1 2 3
1 2 3 4
4 1 2 3
4 3 1 2
4 3 2 1
For the second case we met the most matches (4) and so the answer is 2. The teacher should start asking from the second student onwards. The problem is this algorithm is n^2 and for n = 10^5, the loop will run 10 billion times which times out on their server.
Third Approach : O(n)
The key is to realize what's going on here. Let's look at the input again.
4 1 2 3
First student is saying that he wants to go fourth. Basically this means he wants the second student to go first.
Second student is saying that he wants to go first. This means he wants himself (second student) to go first.
Third student is saying that he wants to go second. This means he wants second student to go first.
Similarly fourth student is saying that he wants to go third. This means he wants second student to go first.
So basically we can replace "4 1 2 3" with "0 4 0 0". Now you can look at this as the votes received by each student from some other student or himself. Now we just need to see who received most votes. As an exercise you can try doing the following case:
5
3 3 1 5 5
This will get replaced by "1 0 1 1 2". The most votes were received by 5th student and so answer is 5. The reason 5th student got 2 votes is because 2nd and 4th student wants 5th student to go first.
Varun
http://acm.timus.ru/problem.aspx?space=1&num=1794
The problem description is quite clear. In summary, there are students sitting in a circle and a teacher would be asking each of them some questions which are part of a test. Each student has their own choice as to when they would like to go give the test. The teacher will ask questions in clockwise order only and can start from anyone of them. The choices of the students are represented as this:
4 (number of students)
4 1 2 3 (their choices)
This means:
1st student would like to give the test at 4th position.
2nd student would like to give the test at 1st position. (He wants to go first, may be he is well prepared !!)
3rd student would like to give the test at 2nd position.
4th student would like to give the test at 3rd position.
In this case the teacher should start asking questions from the 2nd student because then each one of them will get the choice of their own, like this (remember that the students are sitting in the circle)
4 1 2 3
4th 1st 2nd 3rd
First Approach
Since I already knew from others the problem has an O (n) solution, I straightaway went looking for that. At first I thought we might need to look for longest increasing continuous sequence of numbers and that might be the answer. So in the above the longest increasing sequence is 1 2 3 and then 4 as all students are sitting in a circle. I drew out some cases and it failed there.
Second Approach : O(n^2)
Then I went for brute force approach. Start at every position and then see for which one you get the most correct positions. So for the above input:
4 1 2 3
1 2 3 4
4 1 2 3
4 3 1 2
4 3 2 1
For the second case we met the most matches (4) and so the answer is 2. The teacher should start asking from the second student onwards. The problem is this algorithm is n^2 and for n = 10^5, the loop will run 10 billion times which times out on their server.
Third Approach : O(n)
The key is to realize what's going on here. Let's look at the input again.
4 1 2 3
First student is saying that he wants to go fourth. Basically this means he wants the second student to go first.
Second student is saying that he wants to go first. This means he wants himself (second student) to go first.
Third student is saying that he wants to go second. This means he wants second student to go first.
Similarly fourth student is saying that he wants to go third. This means he wants second student to go first.
So basically we can replace "4 1 2 3" with "0 4 0 0". Now you can look at this as the votes received by each student from some other student or himself. Now we just need to see who received most votes. As an exercise you can try doing the following case:
5
3 3 1 5 5
This will get replaced by "1 0 1 1 2". The most votes were received by 5th student and so answer is 5. The reason 5th student got 2 votes is because 2nd and 4th student wants 5th student to go first.
Varun
No comments:
Post a Comment