Блог пользователя lexiyvv

Автор lexiyvv, история, 2 года назад, По-английски

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)

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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