Editorial for COCI '09 Contest 7 #5 Kraljevi

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To start, note that simply calculating all pairs of distances is $\mathcal O(N^2)$ ~\mathcal O(N^2)~ time complexity and scores $30\%$ ~30\%~ of points.

For $100\%$ ~100\%~ of points, we use dynamic programming in $\mathcal O(RS)$ ~\mathcal O(RS)~ time complexity. First, we find the sum of distances between all kings with coordinates $X_1 \le X_2$ ~X_1 \le X_2~ and $Y_1 \le Y_2$ ~Y_1 \le Y_2~, and on the second pass with $X_1 > X_2$ ~X_1 > X_2~ and $Y_1 < Y_2$ ~Y_1 < Y_2~. To find the sum, we start at $(0, 0)$ ~(0, 0)~ and work left to right / top to bottom. We need the following:

row_count(X, Y), row_sum(X, Y) - number of pieces in the fields with coordinates $X_i < X$ ~X_i < X~, $Y = Y_i$ ~Y = Y_i~ and the sum of distances to the field $X, Y$ ~X, Y~.
col_count(X, Y), col_sum(X, Y) - same as row but for columns
dp_count(X, Y), dp_sum(X, Y) - same but for the lower left part of the board, in other words for fields $X_i \le X$ ~X_i \le X~ and $Y_i \le Y$ ~Y_i \le Y~.

For dynamic programming, we need the following relations:

row_sum(X, Y) = row_sum(X, Y-1) + row_count(X, Y-1)
row_count(X, Y) = row_count(X, Y-1) + B(X, Y)
col_sum(X, Y) = col_sum(X-1, Y) + col_count(X-1, Y)
col_count(X, Y) = col_count(X-1, Y) + B(X, Y)
dp_sum(X, Y) = dp_sum(X-1, Y-1) + dp_count(X-1, Y-1) + row_sum(X, Y) + col_sum(X, Y) + B(X, Y)
dp_count(X, Y) = dp_count(X-1, Y-1) + row_count(X, Y) + col_count(X, Y) + B(X, Y)

Where $B(X, Y)$ ~B(X, Y)~ is $1$ ~1~ if the field $(X, Y)$ ~(X, Y)~ contains the figure of the current player, and $0$ ~0~ otherwise.

Now we can easily see that the sum of field $(X, Y)$ ~(X, Y)~ to other pieces is:

sum(X, Y) = dp_sum(X-1, Y-1) + row_sum(X, Y) + col_sum(X, Y)

Comments

1

thomas_li commented on Nov. 19, 2023, 6:49 p.m.

A simpler solution is to translate (x,y) -> (x+y,x-y) (or similar), so the problem becomes sum of Manhattan distances instead of Chebyshev. Then you can independently sum the contribution from x and y coordinates with sorting or brute force.