lexiyvv's blog

By lexiyvv, history, 2 years ago, In English

Using CF's Feature to pass CF1705F in practise

Sill useful till 2022/7/21 9:27, the post time.

It's found that A well known blog has talked about that trick two years ago, you can read (and upvote) that because that's really interesting (and maybe useful).

Let's think of randomize.

For two adjacent problems $$${a_i,a_{i+1}}$$$, randomly question once.

It can be easily calculated that the posibility of instantly getting the correct answer is $$$\frac{1}{2}$$$.

If we get the correct answer, go on querying $$${a_{i+2},a_{i+3}}$$$.

For other possiblilties, we can know the relationship between $$${a_i,a_{i+1}}$$$, so we can go on querying $$${a_{i+1},a_{i+2}}$$$.

Finally, we query once to get the answer of the last problem. By using the relationships, we can get the overall answer.

The expected query number is $$${\frac{2}{3}n+2}$$$.

The expected failure chance per testcase is $$${\frac{1}{3}}$$$.

But there is a feature that CF rejudges the TLE submissions per testcase $$$3$$$ times.

So, every time we exceed query limit, while(1) instantly to get TLE instead of WA for rejudging.

This makes the failure chance per testcase $$$\frac{1}{27}$$$, making the overall pass chance $$$\frac{1}{10}$$$.

In practise, we just need to resubmit several times to get AC.

In contests, this method can be used in randomized solutions to make the AC possibility larger.

Accepted link: 164438874 and 164437895

(Mike, plz don't fix this.It's so useful that... qwq)

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

»
2 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

Yes, it is well known that you can do that. That is why the tests have 20 random tests to try and kill such solutions which abuses this trick. Perhaps we should have added more.

we need to resubmit several times to get AC

Do remember that only the last submission that passes pretest will be run on systests, so using this method is quite risky

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

Auto comment: topic has been updated by lexiyvv (previous revision, new revision, compare).