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) time complexity and scores 30\% of points.

For 100\% of points, we use dynamic programming in \mathcal O(RS) time complexity. First, we find the sum of distances between all kings with coordinates X_1 \le X_2 and Y_1 \le Y_2, and on the second pass with X_1 > X_2 and Y_1 < Y_2. To find the sum, we start at (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, Y = Y_i and the sum of distances to the field 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 and 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) is 1 if the field (X, Y) contains the figure of the current player, and 0 otherwise.

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

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


  • 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.