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?

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | jiangly | 3740 |

3 | Radewoosh | 3652 |

4 | Benq | 3626 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3612 |

7 | ecnerwala | 3587 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3485 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 152 |

6 | cry | 151 |

7 | nor | 150 |

8 | SecondThread | 148 |

8 | -is-this-fft- | 148 |

10 | Petr | 147 |

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?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/12/2024 12:46:32 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

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))? ;)