Here is an interesting problem for Vietnam Informatics Competition for Youth:
Given a board $$$m \times n \ (m, n \leq 10^6)$$$. You know $$$q (q \leq 10^6)$$$ information: square $$$(x_i, y_i)$$$ contains $$$a_i \ (a_i \leq 10^9)$$$ stones. Other unlisted squares contain $$$0$$$ stones. In one step, you could move one stone to an adjacent square, which shares an edge with the current square. The task is to spread stones equally to every square. For example, it takes 2 steps to make [[0, 0], [2, 2]] become [[1, 1], [1, 1]].
I could only model this as a min-cost max-flow problem and solve for small $$$m, n$$$. How to solve the full problem?
Auto comment: topic has been updated by cuom1999 (previous revision, new revision, compare).
Auto comment: topic has been updated by cuom1999 (previous revision, new revision, compare).
Isn’t the problem independent on the two dimensions (i.e., spreading elements evenly on all rows/columne)? If so, it gets reduced to 1D version, which can be solved pretty easily using greedy approach.
What do you mean? What if the only stones are on the bottom right square?
He means you can solve for x and y coordinates independently, not that you spread them evenly across all rows and columns (I think).
It was also my first thought, but $$$[[2, 0], [0, 2]]$$$
Thank you. Didn't notice your comment then. Any solution idea? I'm still struggling on this problem.
similar tasks.
https://atcoder.jp/contests/joi2019ho/tasks/joi2019ho_d
https://cses.fi/problemset/task/2180
https://codeforces.net/contest/1700/problem/F