ajs97's blog

Solution to Gym Problem?
By ajs97, history, 9 years ago, In English

Recently I was solving a gym contest and came across this problem:http://mirror.codeforces.com/gym/100739/problem/D. I have absolutely no idea as to how to solve it? Could someone give some ideas regarding the solution?

Tags gym, ktu
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't we view submission in gym? Does someone know the reason? If we can, then this problem will be solved, too.

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

You can write MxN equations R[i] + C[j] = K — A[i][j] (mod K), where R[i] — number of operation "increment i-th row", C[j] — number of operations "increment i-th column".

Now let's R[i] = 0. With that you can calculate all C[j] and R[i]. And total number of operations is sum of all R[i] and C[j].

It is one of the possible answers, but can be not minimal. It's because R[0] from optimal answer can be not 0.

We can't brute all values of R[0]. But we can do next observation: if we increment any of R[i] — we need to increment all R[i] and decrement all C[j]. When we do this, total number of operation will be changed for M — N.

It can be easy proven, that optimal answer would contain some R[i] or C[j] equals to 0 (if not — we can decrement our answer for M — N or N — M at most once).

So we can simply iterate over all R[i] and C[j], set it to 0 and find answer for that setting. From all answers we need to choose answer with minimal sum of operations.

P.S. Can you modify this from O((N+M)^2) to O((N+M)log(N+M))? ;)

→ Reply