simp1eton's blog

By simp1eton, 11 years ago, In English
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?
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why haven't you given a direct link to the solution?

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.
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
As I have mentioned, the solution is in this site (http://www.hsin.hr/coci/) and it is Question 5 of Contest 3. There isn't really any direct link because you have to download the zip file and open it. If you want something more specific, this is the best I can give. is http://www.hsin.hr/coci/contest3_solutions.zip.
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There are many solutions to solve this task.
    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.
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Wow, that's a really amazing solution Harta! I will try submitting that XD and then examine your segment tree solution. Thanks a lot!