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)