MagicSpark's blog

Looking For 1354G non-random solutions.
By MagicSpark, history, 5 years ago, In English

When I'm taking part in Educational Codeforces Round 87,I come up with a random solution.

But I didn't think it can pass.(In fact I'm wrong and the solution has more than 99.99% possibility to pass)

And I think for a long time to find a non-random solution without getting good ideas

Can somebody solve this problem?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my random solution 80523216 You can easily prove that it has a high possibility to pass.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I wrote my random solution here. I think the solution is similar to you :)

If we can find any stone box (not necessarily minimum index) in at most $$$29$$$ queries, we can solve this problem. This seems much easier than the original problem.

If we solve this sub-problem deterministically, we can solve the original problem deterministically. Though, I haven't come up with the solution yet.

(I expect that the intended solution is also randomized. That's because hacks are prohibited for this problem.)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes you are right... I am also trying to solve this,but got no ideas. So I think other ways may work instead of this.

    → Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

My solution is not randomized (link: https://mirror.codeforces.com/contest/1354/submission/80509851)

Basically, I try to find a stone by splitting the objects into two groups (if it's odd, leave one out to check for later). Then, the stone is likely to be in the heavier group.

However, someone pointed out that there are testcases that could break my solution, like 100 97 99 99 100 100 100 1, where 100 is a stone. If I split by ranges, it will take the first 4 (100 97 99 99), but will then go to (99 99) as it is heavier than (100 97).

Quite sure the solution is very likely to pass (because k <= n/2). But in hindsight, I probably should have randomized the indexes of the objects.

→ Reply