### ajs97's blog

By ajs97, history, 8 years ago,

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?

• +9

| Write comment?
 » 8 years ago, # |   0 Why can't we view submission in gym? Does someone know the reason? If we can, then this problem will be solved, too.
•  » » 8 years ago, # ^ |   0 Div.1s can see those submissions. you need to get promoted, so do i:)
•  » » » 8 years ago, # ^ |   0 Really, thanks :))
 » 8 years ago, # |   0 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))? ;)