Recently I was solving a gym contest and came across this problem:http://codeforces.me/gym/100739/problem/D. I have absolutely no idea as to how to solve it? Could someone give some ideas regarding the solution?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Recently I was solving a gym contest and came across this problem:http://codeforces.me/gym/100739/problem/D. I have absolutely no idea as to how to solve it? Could someone give some ideas regarding the solution?
Name |
---|
Why can't we view submission in gym? Does someone know the reason? If we can, then this problem will be solved, too.
Div.1s can see those submissions. you need to get promoted, so do i:)
Really, thanks :))
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))? ;)