PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sky_nik
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix minimums
PROBLEM:
You are given an array A.
Consider a graph on N vertices, where there is an edge between vertices i and j with weight |i-j|\cdot \max(A_i,A_j).
Find the minimum weight of a path from vertex 1 to vertex N.
EXPLANATION:
As an obvious first step, observe that in an optimal solution, we’ll never use an edge i\to j such that i\gt j; in other words, we’ll never move backwards.
Proof
Suppose we move i\to j at some point, where i\gt j.
Let this be the first such backward move.
There are two possibilities:
- If A_j \geq A_i, then no matter what the next move j\to k is, it’ll be not more expensive to replace i\to j \to k with the direct i\to k, and end up in the same situation.
- If A_j \lt A_i, then no matter what the previous move k\to i was, it’ll be not more expensive to replace k\to i\to j with the direct k\to j.
Either way, we’ve removed one backward move without increasing the cost, so we can repeatedly do this till no backward moves remain.
Next, let’s try to eliminate several ‘useless’ edges from consideration.
In particular, suppose there are three indices i \lt j \lt k such that A_j \leq \max(A_i, A_k). Then, we don’t need to consider the edge i\to k at all!
Why?
Suppose A_i \leq A_k. Since we assumed A_j \leq \max(A_i, A_k), this also means A_j \leq A_k.
Moving directly from i to k has a cost of A_k\cdot (k-i).
Moving i\to j and then j\to k has a cost of \max(A_i, A_j)\cdot (j-i) + A_k\cdot (k-j).
However, \max(A_i, A_j) \leq A_k, and so this certainly isn’t more than the cost of moving from i to k directly (and will in fact be lower, if both A_i and A_j are strictly less than A_k), which proves our claim that the i\to k edge is useless.
With this in mind, let’s try to decide which edges should be taken.
Suppose we’re at index 1.
There are two possibilities:
- Suppose there exists an index i\gt 1 such that A_i \leq A_1. In particular, choose the leftmost such index and call it i_L.
In this case, it’s always optimal to move from 1 to i_L, with a cost of A_1\cdot (i_L - 1).
It’s not hard to see why: since A_{i_L} \leq A_1, our earlier observation tells us that moving from 1 to anything beyond i_L is not optimal. Further, everything before index i_L is strictly larger than A_1, so instead of moving several steps with a cost that’s larger than A_1, it’s better to just take the cost of A_1 and reach i_L. - Suppose A_1 \lt A_i for every i\gt 1.
In this case, let i_L be the index of the minimum element other than A_1 (if there are multiple minimums, choose the leftmost one).
Again, it can be seen that it’s optimal to move to this i_L, with a cost of A_{i_L}\cdot (i_L - 1).
The reason is similar: jumping directly beyond i_L is not optimal since A_{i_L} will be in the middle and smaller; and jumping somewhere to its left is not optimal since it’ll incur a higher cost than A_{i_L} for moving some steps, when we could’ve taken A_{i_L} for them instead.
With this, we know the optimal jump from index 1. Make this jump, then repeat this process for the remaining array.
Implementing this directly will run into a complexity of \mathcal{O}(N^2), of course. However, note that:
- The first step has us repeatedly move to the next smaller element; which is just a prefix minimum.
- The second step has us repeatedly move to the smallest element of a suffix; so a suffix minimum.
So, by simply precomputing prefix and suffix minima, each jump can be made in constant time, leading to a solution that’s \mathcal{O}(N) overall.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
int last = 0;
int ans = 0;
for (int i = 1; i < n; i++){
if (a[i] < a[last]){
ans += (i - last) * a[last];
last = i;
}
}
reverse(a.begin(), a.end());
last = 0;
for (int i = 1; i < n; i++){
if (a[i] <= a[last]){
ans += (i - last) * a[last];
last = i;
}
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& ai : a) {
cin >> ai;
}
vector<int> pref_min(n), suff_min(n);
const auto min_of = [&](auto a, auto b) { return min(a, b); };
partial_sum(a.cbegin(), a.cend(), pref_min.begin(), min_of);
partial_sum(a.crbegin(), a.crend(), suff_min.rbegin(), min_of);
int64_t ans = 0;
for (int i = 1; i < n; ++i) {
ans += max(pref_min[i - 1], suff_min[i]);
}
cout << ans << '\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pmin, smin = a[:], a[:]
for i in range(1, n):
pmin[i] = min(a[i], pmin[i-1])
smin[n-1-i] = min(a[n-1-i], smin[n-i])
x = ans = 0
for i in range(1, n):
if a[i] == pmin[i] or a[i] == smin[i]:
ans += (i-x)*max(a[i], a[x])
x = i
print(ans)