Minimum steps to spread stones on a grid

Правка en3, от cuom1999, 2020-11-11 22:41:20

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$$$ 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский cuom1999 2020-11-12 00:36:35 14 Tiny change: 'ou know $q$ informat' -> 'ou know $q (q \leq 10^6)$ informat'
en3 Английский cuom1999 2020-11-11 22:41:20 8
en2 Английский cuom1999 2020-11-11 22:40:46 9 Tiny change: 'es. Other squares c' -> 'es. Other unlisted squares c'
en1 Английский cuom1999 2020-11-11 22:40:05 638 Initial revision (published)