galen_colin's blog

Edge cases for Round 675 E
By galen_colin, history, 4 years ago, In English

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.

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

calen_golin orz

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

storing another stack that contains exactly one copy of each character

My original submission used this strategy, but I did it incorrectly somehow and was hacked by Mediocrity (thank you, I was able to submit again because of you!). My issue was that sometimes my second stack wouldn't actually have only one copy of each character (e.g. sometimes it became jaa). So I just patched it by adding

while (distinct.size() >= 2 &&
       distinct[distinct.size() - 1] == distinct[distinct.size() - 2])
  distinct.pop_back();
→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

i like your tags

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have tried a lot but still stuck in Test 46. The above 2 examples are working fine. Any help/guidance will be appreciated

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try ddxxdc. Answer should be

    2 dc 3 ddc 2 dc 3 xdc 2 dc 1 c

    This was my bug. This accounts for the case where the next char not equal to the character changes.

    → Reply