Using CF's Feature to pass CF1705F in practise

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

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)