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

Do you think there is a mistake with the verdict for problem 794-C?
Автор jrm3891, история, 5 лет назад, По-английски

The problem is listed below: https://mirror.codeforces.com/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'

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

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

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).

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить