F - Rooks Editorial by Errichto
If you want a short editorial, scroll down to Full Problem section.
Hints/Subtasks
Here’s an unusual hint: just try to solve these three easier versions of a problem:
P1. \(N \leq 3000\)
P2. Same as full problem but the input is monotonic (\(x[i] < x[i+1]\), \(y[i] < y[i+1]\)).
P3. Same as full problem but you only need to consider the scenario of replacing rook 1.
P1. \(N \leq 3000\)
Let’s assume that rooks are sorted by \(x\)-coordinate. At any moment, the rooks beaten so far form an interval of indices \([L, R]\) and our last move was to beat rook \(L\) or rook \(R\). The next move must be to beat rook \(L-1\) or rook \(R+1\) and that’s allowed only if such a next rook isn’t blocked by another rook that has \(y\)-coordinate closer to our current position. In order to check that in \(O(1)\), let’s also maintain the current interval of available \(y\)-coordinates (you can compress \(y\)’s first).
For fixed starting position, let \(dp[L][R][isLeft]\) denote minimum time to beat interval of rooks \([L, R]\) and finish at left/right end of this interval. We transition from \(dp[L][R][0/1]\) to \(dp[L-1][R][0]\) and to \(dp[L][R+1][1]\). Running this dp for every starting position gives \(O(N^3)\) in total.
Even better, let \(dp[L][R][isLeft]\) denote the minimum remaining time to finish the process optimally if we are now at state \((L, R, isLeft)\). We can run this dp once and then \(dp[i][i][0/1]\) is the answer for \(i\)-th starting position. Time complexity is \(O(N^2)\).
P2. Monotonic Input
You need \(|x_1-x_2|+|y_1-y_2|-1\) steps to get from \((x_1, y_1)\) to rook at \((x_2, y_2)\). You can treat the distance between two rooks as the manhattan distance \(|x_1-x_2|+|y_1-y_2|\) and just subtract \(countBeatenRooks\) when printing.
Let \(dist(i, j)\) denote manhattan distance between rooks \(i\) and \(j\).
Lemma: \(dist(a, b) + dist(b, c) = dist(a, c)\) for \(a < b < c\).
This implies that when we go e.g. from rook \(4\) to rook \(8\), we can just go through positions of already-beaten rooks \(5, 6, 7\). Hence:
Important Lemma: starting from rook \(s\), there are two possible optimal paths: \(s \rightarrow 1 \rightarrow n\) or \(s \rightarrow n \rightarrow 1\).
(That is, just keep going left and then keep going right, or the other way around.)
If \(x\)’s and \(y\)’s are sorted in the input, we have
\[answer[i] = min(dist(i, 1) + dist(1, n), dist(i, n) + dist(n, 1))\]
This property wouldn’t hold if the king could move in all 8 directions.
P3. One Starting Position & Full Problem
See the video analysis here https://www.youtube.com/watch?v=SN0dyP2kJgo&t=22m
The solution will be later written down here as well.
code
#include // Rooks, by Errichto
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge range(c i, c j) { return rge{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
struct Rook {
int x, y, id;
bool operator <(const Rook& other) const {
return x < other.x;
}
};
long long hack;
int main() {
int n;
scanf("%d", &n);
assert(2 <= n && n <= 200 * 1000);
vector rooks(n);
for(int i = 0; i < n; ++i) {
rooks[i].id = i;
scanf("%d%d", &rooks[i].x, &rooks[i].y);
assert(1 <= min(rooks[i].x, rooks[i].y) && max(rooks[i].x, rooks[i].y) <= 1000 * 1000);
}
sort(rooks.begin(), rooks.end());
vector ys{INT_MIN, INT_MAX}; // two sentinels for convenience
for(int i = 0; i < n; ++i) {
ys.push_back(rooks[i].y);
}
sort(ys.begin(), ys.end());
for(int i = 0; i < n - 1; ++i) {
assert(ys[i] != ys[i+1]);
assert(rooks[i].x != rooks[i+1].x);
}
vector> answer(n, {-1, -1});
for(int start = 0; start < n; ++start) {
if(answer[rooks[start].id].first != -1) {
continue;
}
int start_y = lower_bound(ys.begin(), ys.end(), rooks[start].y) - ys.begin();
int y1 = start_y - 1, y2 = start_y + 1;
int L = start, R = start;
int prev_dir = -1;
vector> intervals;
while(true) {
bool found = false;
for(int i : {L - 1, R + 1}) {
if(0 <= i && i < n) {
bool prev_y = (ys[y1] == rooks[i].y);
bool next_y = (ys[y2] == rooks[i].y);
if(prev_y || next_y) {
int direction = (prev_y == (i == L - 1)); // 0 or 1
// debug() << imie(start) imie(i) imie(direction);
if(prev_dir == -1) {
prev_dir = direction;
}
if(prev_dir != direction) {
intervals.emplace_back(L, R);
prev_dir = direction;
}
prev_y ? y1-- : y2++;
i == L-1 ? L-- : R++;
found = true;
break;
}
}
}
if(!found) {
break;
}
}
if(intervals.empty() || intervals.back() != make_pair(L, R)) {
intervals.emplace_back(L, R);
}
const int s = intervals.size();
debug() << imie(start) imie(intervals);
{ // complexity check
static int sum_s = 0, sum_len = 0;
if(s > 1) sum_s += s;
assert(sum_s <= n);
sum_len += R - L + 1;
assert(sum_len <= 3 * n); // N + out + 2 * border ('out' and 'border' are disjoint)
static vector basic(n), out(n), border(n);
pair i_basic = intervals[0], i_out = intervals[max(0,s-2)], i_border = intervals.back();
for(int i = i_border.first; i <= i_border.second; ++i) {
if(i_basic.first <= i && i <= i_basic.second) {
assert(++basic[i] == 1);
}
else if(i_out.first <= i && i <= i_out.second) {
assert(++out[i] == 1 && border[i] == 0);
}
else {
assert(++border[i] <= 2 && out[i] == 0);
}
}
}
const long long INF = 1e18L + 5;
auto min_self = [&](long long& a, long long b) {
a = min(a, b);
};
auto f = [&](int i, int j) { // manhattan distance between two rooks
return abs(rooks[i].x - rooks[j].x) + abs(rooks[i].y - rooks[j].y);
};
vector> dp(s, vector(2, INF));
// dp[i][0] is minimum number of REMAINING operations if we did interval i and we are at its left end
// dp[i][1] -- same but right end
dp[s-1][0] = dp[s-1][1] = 0;
for(int who = s - 1; who >= 1; --who) {
// [L1, [L2, R1], R2]
int L1 = intervals[who].first;
int L2 = intervals[who-1].first;
int R1 = intervals[who-1].second;
int R2 = intervals[who].second;
hack += (long long) (L2 - L1) * (R2 - R1);
min_self(dp[who-1][0], dp[who][0] + (R1 == R2 ? f(L1, L2) : f(L1, R2) + f(R2, L2)));
min_self(dp[who-1][1], dp[who][0] + f(L1, R2) + f(R2, R1));
min_self(dp[who-1][0], dp[who][1] + f(R2, L1) + f(L1, L2));
min_self(dp[who-1][1], dp[who][1] + (L1 == L2 ? f(R1, R2) : f(R2, L1) + f(L1, R1)));
}
int low = intervals[0].first, high = intervals[0].second;
for(int i = low; i <= high; ++i) {
assert(answer[rooks[i].id] == make_pair(-1, -1LL));
answer[rooks[i].id] = {
R - L,
min(dp[0][0] + f(low, high) + f(high, i), dp[0][1] + f(high, low) + f(low, i))
};
}
}
for(pair p : answer) {
// printf("%d %lld\n", p.first, p.second - p.first);
printf("%lld\n", p.second - p.first);
}
cerr << "hack = " << hack << endl;
}
posted:
last update: