OptimalNight's blog

By OptimalNight, history, 22 months ago, In English

In the last Educational round #129, problem D saw many hacks. Even though I have used a similar dfs/dp technique as the others who got AC, I was also under the impression that my solution might also get hacked as there is one slight difference. Instead of calling the recursion for all the digits present in the number (I was thinking it might give TLE), I only called the recursion for the largest 5 digits present in it. Link to the submission: https://codeforces.com/contest/1681/submission/158201638

It passed the system tests and withstood the hack cases as well. I still don't know if taking the top 5 digits is sufficient or if it is that there wasn't any test that oversaw this case. Is the logic sufficient or did I just get lucky?

If the logic is insufficient, then it shows yet another case of weak system tests. Over the last few contests, either I or one of my friends get an FST on the kind of mistakes which should have given WA on pretest 2. Even with these blunder mistakes, the program passes around 30-70 tests and then fails. Why don't these codes fail at the beginning? Are the system tests and pretests getting weaker day by day, or is it just that me and my friends are running a little thin on our luck.

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
22 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Whilst I am also slightly surprised, have you actually found a counter-example or are you just surprised too? I have no proof that your algorithm should work, but not counter-example either. Perhaps you just got lucky with a heuristic that works. Not sure we can say this is a case of weak system tests without knowing of a counter-example.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am myself surprised. When my solution which considers all the digits got accepted after the contest, I really thought that the above solution might fail. But it didn't. I don't have any proof or counter-example either.