In problems A and G in Codeforces Round #713 (Div. 3) invalid hacks were allowed for some time. Such hacks will be removed, and hacked solutions will be rejudged. ×

Edge cases for Round 675 E

Revision en1, by galen_colin, 2020-10-04 23:33:37

I know a lot of people (including myself) have failed system tests on this notorious problem, and if you've been scratching your head for a while trying to figure out why, this (might be) the blog for you! (although it seems like there's more than 1 type of bug)

One common fail was a wrong answer on test 46. This bug might be because you haven't checked that the two characters you're removing were actually consecutive in the initial string (for a test case like deedc) — this can be remedied by storing indices along with the characters of the string and making the appropriate checks. However, this may now lead you to a different wrong answer. What I found that broke my program was the following simple case: ddeedc. The assumption I made was that if two equal characters at the front of the string haven't been removed yet, then it's not optimal to remove any more of those characters in that "chain" of equal characters (i.e. we checked it before). So to check if you wanted to remove two characters, it would be enough to check two positions ahead (or one, depending on implementation), and remove those two characters only if they were greater than the character two ahead.

However, that assumption is wrong. When ee is removed from that string, we end up with dddc. The reason that the last two d's weren't removed is because they weren't together initially in the string, meaning that it breaks my assumption (since it's optimal to remove the first two d's). So instead of checking the character two characters ahead, I instead had to check for the next different character (which is kind of obvious in retrospect). This can be fixed by storing another stack that contains exactly one copy of each character, rather than the consecutive groups of them. It's probably not easy to read, but if you want it, here's my correct submission.

Were there other bugs you found? Maybe you should comment them here, and we can have this blog as a universal compilation of our stupidity.

Tags 1422e, stupidity, subscribe

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English galen_colin 2020-10-04 23:33:37 2162 Initial revision (published)