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)