goodProg's blog

Solution to 2047C may be wrong?
By goodProg, history, 3 days ago, In English

Here is the problem : https://codeforces.net/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!

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

»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Transform it:

4 3 2 3

3 5 8 3

→ Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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?

    → Reply