jrm3891's blog

Do you think there is a mistake with the verdict for problem 794-C?
By jrm3891, history, 5 years ago, In English

The problem is listed below: https://codeforces.net/problemset/problem/794/C

The verdict says: wrong answer 1st words differ — expected: 'abac', found: 'baca' But I think my output: 'baca' is correct. I have gone through the problem several times but I fail to see why the output should be 'abac'

  • Vote: I like it
  • -29
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

This is a bad blog. Why would you not show the test case? How does the verdict help when one doesn't know the input? It's not even a sample test, so one has to go looking for your submission to find it. Zero explanation on why you think 'baca' is the correct answer either. Ridiculous.

Inputs in the test case are "cbxz" and "aaaa". First player's best strategy is to force the second player into putting 'a' in the beginning rather than putting anything there himself. The game proceeds as follows:

  • First player makes ???c and is left with {b, x, z}
  • Second player has only 'a'-s so puts one as far back as possible making ??ac
  • First player makes ?bac
  • Second player makes abac

I won't try to prove this is the optimal answer for both, you can do that, but it's clearly not 'baca' (which comes from a very simple but wrong greedy). It is clear from the game described above that the first player can force 'abac' or better, so he wouldn't settle for 'baca'.

Also the problem is solved by 2000+ people and has an editorial. It's naive to think such a simple test is wrong and no one noticed (not impossible, but negligibly likely).

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

    Sorry I am new to programming and to codeforces.

    Let me post my code which is written in python and also the input:

    s=sorted(input())
t=sorted(input(),reverse=True)
z=""
for i in range(round(len(s)/2)):
    z=z+s[i]+t[i]
print (z[:len(s)])

    Test: #6, time: 93 ms., memory: 0 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Input
cbxz
aaaa
Output
baca
Answer
abac
Checker Log
wrong answer 1st words differ - expected: 'abac', found: 'baca'

    I was not able to find the solution. I tried cliecking on "standings" but I did not find a solution. I would appreciate it if you could tell me what's wrong with my code.

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

      The idea of your algorithm is wrong. You assume the strategy for each player is to fill his best choice as early as possible in the string, but in reality one might prefer to fill letters towards the end to force the opponent into doing things they don't want to do.

      The test you're wrong on is a perfect example of why your algorithm is wrong.

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

        Hi, if you don't mind can you please provide me with the link to the editorial? I tried finding it online but couldn't. Appreciate your help

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

          Open the problem and look at bottom right. In the section "Contest Materials" click on "Tutorial".

          → Reply