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

Solution to 2047C may be wrong?
Автор goodProg, история, 6 дней назад, По-английски

Here is the problem : https://mirror.codeforces.com/contest/2047/problem/C

------------------

Here is my code:299031549

------------------

Concern

I might be completely wrong but it just takes the maximum of the second row after swapping, that may not always result in the correct solution.

Check this test case:

4

3 2 3 4

5 8 3 3

I think the answer is 22, but this outputs 23 Which is not possible unless we can swap diagonally. Please let me know what do you guys think about this!

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

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

Transform it:

4 3 2 3

3 5 8 3

→ Ответить
»
6 дней назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

3 4 3 2

3 3 5 8

you can swap cols like this and the path would be

3+4+3+5+8 = 23

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

    That makes much more sense, could you maybe explain a little about why the solution works?

    I am particularly confused about the part where we just take the max of array b. Why would that guarantee the solution?

    → Ответить