#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/d

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/d

Repovive

Kings on Diagram - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3D. Kings on Diagram

2000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

First assume the board contains exactly $n$ kings. We want to assign each diagonal cell $(i,i)$ to a distinct king, and move each king there.

For a king starting at $(x,y)$ , the minimum number of moves to reach $(i,i)$ (ignoring other kings) is $d((x,y),(i,i)) = \max(|x-i|, |y-i|)$ , because in one move both coordinates can change by at most $1$ .

Let $a \le b$ be two diagonal indices, and let $p=(x_1,y_1)$ , $q=(x_2,y_2)$ be two kings with $(x_1+y_1) \le (x_2+y_2)$ . Then it is never worse to match $p \to (a,a)$ and $q \to (b,b)$ than to match $p \to (b,b)$ and $q \to (a,a)$ .

This means there exists an optimal assignment where, after sorting kings by $(x+y)$ , the matched diagonal indices are nondecreasing. In the special case of exactly $n$ kings, the optimal assignment is simply: the $i$ -th king in sorted order is matched to diagonal cell $(i,i)$ . So the answer becomes $\sum_{i=1}^n \max(|x_i-i|,|y_i-i|)$ after sorting by $(x_i+y_i)$ .

First assume the board contains exactly $n$ kings. We want to assign each diagonal cell $(i,i)$ to a distinct king, and move each king there.