The goal of this blog is to provide an alternative editorial to AtCoder Regular Contest 231 Problem A which will hopefully be easier, for at least some people, to reason about compared to the official editorial.↵
↵
For the sake of simplicity, we will have that the $ \min $ of the empty set is $ 10^{100} $ as a convention.↵
↵
First, let us define a sequence $ ( a_0, a_1, \ldots, a_N ) $ as follows: $ a_0 = 0 $, and for $ k > 0 $, $ a_k $ is the minimum possible total cost immediately after event $ k $ on the condition that the sword is used on event $ k $.↵
The answer is then↵
$$ \min_{ k \in \{0, 1, \ldots, N\} } \left\{ a_k + \sum_{j > k} Z_j \right\} \text{.} $$↵
↵
Now, let $ (X_0, Y_0) = (0, 0) $.↵
For $ k > 0 $, we have↵
$$ ↵
\begin{aligned}↵
a_k &= \min_{j < k} \left\{ a_j + \left( \sum_{ i \in \{ j+1, j+2, \ldots, k-1 \} } Z_i \right) + (X_i - X_j)^2 + (Y_i - Y_j)^2 \right\}$$↵
$$\\ ↵
&= \left( \sum_{ i < k } Z_i \right) + \min_{j < k} \left\{ a_j - \left( \sum_{ i \leq j } Z_i \right) + (X_k - X_j)^2 + (Y_k - Y_j)^2 \right\} ↵
\end{aligned}↵
$$↵
which can be seen by considering the cases when the sword was most recently used on event $ j $ (with $ j > 0 $), or the sword was never used previously with $ j = 0 $.↵
If we try to naively implement this into a program, we will probably end up with a time complexity that is quadratic in $ N $, which is too slow.↵
To help with this, we define a family of functions $ g_{k, X} $ as follows:↵
$$ g_{k, X}(Y) = \min_{j < k} \left\{ a_j - \left( \sum_{ i \leq j } Z_i \right) + (Y_j - Y)^2 : X_j = X \right\} $$↵
for $ X \in \\{ 0, 1, \ldots, 499 \\} $ and $ k \in \\{ 0, 1, \ldots, N \\} $.↵
Then for $ k > 0 $, we have↵
$$ a_k = \left( \sum_{ i < k } Z_i \right) + \min_{X \in \{ 0, 1, \ldots, 499 \} } \left\{ (X_k - X)^2 + g_{k, X}(Y_k) \right\} $$↵
so if we can compute $ g_{k, X}(Y_k) $ in constant time, we are done.↵
The trick is to notice that for $ k < N $, we have↵
$$ g_{k+1, X} = g_{k, X} $$↵
when $ X \neq X_k $, and↵
$$ g_{k+1, X_k}(Y) = \min \left\{ g_{k, X_k}(Y) , \left( a_k - \left( \sum_{ j \leq k } Z_j \right) + (Y_k - Y)^2 \right) \right\} $$↵
for $ Y \in \\{ 0, 1, \ldots, 499 \\} $.↵
↵
Below is an implementation that uses this idea.↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
long long a[250001];↵
long long gx[500][500];↵
↵
long long INF = 1e18;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
for (int i = 1; i != 250001; ++i) {↵
a[i] = INF;↵
}↵
for (int i = 0; i != 500; ++i) for (int j = 0; j != 500; ++j) gx[i][j] = ((i == 0) ? j * j : INF);↵
↵
queue<int> Z;↵
long long sumz = 0;↵
for (int k = 1; k <= n; ++k) {↵
long long x, y, z;↵
cin >> x >> y >> z;↵
Z.push(z);↵
↵
long long mi = INF;↵
for (int X = 0; X != 500; ++X) mi = min(mi, (X - x) * (X - x) + gx[X][y]);↵
a[k] = sumz + mi;↵
↵
sumz += z;↵
for (int Y = 0; Y != 500; ++Y) gx[x][Y] = min(gx[x][Y], a[k] - sumz + (Y - y) * (Y - y));↵
}↵
↵
long long ans = sumz;↵
for (int k = 1; k <= n; ++k) {↵
sumz -= Z.front();↵
ans = min(ans, a[k] + sumz);↵
Z.pop();↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
signed main() {↵
int t;↵
cin >> t;↵
↵
while (t--) solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
For the sake of simplicity, we will have that the $ \min $ of the empty set is $ 10^{100} $ as a convention.↵
↵
First, let us define a sequence $ ( a_0, a_1, \ldots, a_N ) $ as follows: $ a_0 = 0 $, and for $ k > 0 $, $ a_k $ is the minimum possible total cost immediately after event $ k $ on the condition that the sword is used on event $ k $.↵
The answer is then↵
$$ \min_{ k \in \{0, 1, \ldots, N\} } \left\{ a_k + \sum_{j > k} Z_j \right\} \text{.} $$↵
↵
Now, let $ (X_0, Y_0) = (0, 0) $.↵
For $ k > 0 $, we have↵
$$
\begin{aligned}↵
a_k &= \min_{j < k} \left\{ a_j + \left( \sum_{ i \in \{ j+1, j+2, \ldots, k-1 \} } Z_i \right) + (X_i - X_j)^2 + (Y_i - Y_j)^2 \right\}
$$
&= \left( \sum_{ i < k } Z_i \right) + \min_{j < k} \left\{ a_j - \left( \sum_{ i \leq j } Z_i \right) + (X_k - X_j)^2 + (Y_k - Y_j)^2 \right\}
\end{aligned}↵
$$↵
which can be seen by considering the cases when the sword was most recently used on event $ j $ (with $ j > 0 $), or the sword was never used previously with $ j = 0 $.↵
If we try to naively implement this into a program, we will probably end up with a time complexity that is quadratic in $ N $, which is too slow.↵
To help with this, we define a family of functions $ g_{k, X} $ as follows:↵
$$ g_{k, X}(Y) = \min_{j < k} \left\{ a_j - \left( \sum_{ i \leq j } Z_i \right) + (Y_j - Y)^2 : X_j = X \right\} $$↵
for $ X \in \\{ 0, 1, \ldots, 499 \\} $ and $ k \in \\{ 0, 1, \ldots, N \\} $.↵
Then for $ k > 0 $, we have↵
$$ a_k = \left( \sum_{ i < k } Z_i \right) + \min_{X \in \{ 0, 1, \ldots, 499 \} } \left\{ (X_k - X)^2 + g_{k, X}(Y_k) \right\} $$↵
so if we can compute $ g_{k, X}(Y_k) $ in constant time, we are done.↵
The trick is to notice that for $ k < N $, we have↵
$$ g_{k+1, X} = g_{k, X} $$↵
when $ X \neq X_k $, and↵
$$ g_{k+1, X_k}(Y) = \min \left\{ g_{k, X_k}(Y) , \left( a_k - \left( \sum_{ j \leq k } Z_j \right) + (Y_k - Y)^2 \right) \right\} $$↵
for $ Y \in \\{ 0, 1, \ldots, 499 \\} $.↵
↵
Below is an implementation that uses this idea.↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
long long a[250001];↵
long long gx[500][500];↵
↵
long long INF = 1e18;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
for (int i = 1; i != 250001; ++i) {↵
a[i] = INF;↵
}↵
for (int i = 0; i != 500; ++i) for (int j = 0; j != 500; ++j) gx[i][j] = ((i == 0) ? j * j : INF);↵
↵
queue<int> Z;↵
long long sumz = 0;↵
for (int k = 1; k <= n; ++k) {↵
long long x, y, z;↵
cin >> x >> y >> z;↵
Z.push(z);↵
↵
long long mi = INF;↵
for (int X = 0; X != 500; ++X) mi = min(mi, (X - x) * (X - x) + gx[X][y]);↵
a[k] = sumz + mi;↵
↵
sumz += z;↵
for (int Y = 0; Y != 500; ++Y) gx[x][Y] = min(gx[x][Y], a[k] - sumz + (Y - y) * (Y - y));↵
}↵
↵
long long ans = sumz;↵
for (int k = 1; k <= n; ++k) {↵
sumz -= Z.front();↵
ans = min(ans, a[k] + sumz);↵
Z.pop();↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
signed main() {↵
int t;↵
cin >> t;↵
↵
while (t--) solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
