I refer you to this problem: http://www.z-trening.com/tasks.php?show_task=5000000771
This problem is COCI 2009/2010 Contest 3 Problem 5. I went to look at the solution but do not really understand the solution, so I wonder if anyone here can help me.
I went to the COCI website (http://www.hsin.hr/coci/) and downloaded the solution and went to look at it, but I don't really get the solution. I ran it on the sample and this is what I got.
In the sample, there are 10 dwarfs:
1 2 1 2 1 2 3 2 3 3
Let's assume that we have splitted the segments into (1,8) and (9,10). Let's call them segment A and B respectively. We see that A's candidate is 2 and the count is 0. We see that B's candidate is 3 and the count is 2. Therefore, when we merge these two segments, the candidate is 3 and the count is 2. But if we count the number of 3s, there are only three of them out of 10.
So am I missing something here? Is there some additional steps required that is not mentioned?
This problem is COCI 2009/2010 Contest 3 Problem 5. I went to look at the solution but do not really understand the solution, so I wonder if anyone here can help me.
I went to the COCI website (http://www.hsin.hr/coci/) and downloaded the solution and went to look at it, but I don't really get the solution. I ran it on the sample and this is what I got.
In the sample, there are 10 dwarfs:
1 2 1 2 1 2 3 2 3 3
Let's assume that we have splitted the segments into (1,8) and (9,10). Let's call them segment A and B respectively. We see that A's candidate is 2 and the count is 0. We see that B's candidate is 3 and the count is 2. Therefore, when we merge these two segments, the candidate is 3 and the count is 2. But if we count the number of 3s, there are only three of them out of 10.
So am I missing something here? Is there some additional steps required that is not mentioned?
As it follows from the name, candidate is not the answer to the problem, it's merely a candidate to the answer. You still need to count the number of times the candidate appears. In this sample, it's less than a half, so the picture is not pretty.
I want to discuss a more interesting one that is randomly choose a number from interval a to b for each queries. Then you can do it several times and check if there is a solution (i.e. a number which has duplicates more than 1/2 of the numbers in that interval. This has a very big chance to get a correct result since suppose there is a solution then the probability to get a false result each time is less than 0.5(probability to get false numbers is {false numbers/numbers in that interval} and false numbers is not more than 1/2 of total numbers in that interval). You do iteration for N times (N = 50 is enough), thus the total probability to get a false result is approximately 0.5^50=(2^-ITER as stated in kalinov's solution)
Another solution is using segment tree.
You can check it here.
After you have solved it, you can consult my solution in z-trening using segment tree.