PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
2896
PREREQUISITES:
Sorting, sweep line and/or Dijkstra’s algorithm
PROBLEM:
There are k points on the 2-D plane. The i-th point has a cost of c_i and energy e_i. You start at (0, 0) and want to reach (N, M).
Moving one step up or right reduces energy by 1, while moving left or down increases it by 1. At the i-th of the the N points above, you can also choose to pay c_i and reset your energy to e_i.
Find the minimum cost to reach (N, M) while ensuring that your energy never becomes negative.
EXPLANATION:
Let us define the height of the point (x, y) to be x+y.
Note that moving from a point with height h_1 to a point with height h_2 will change your energy by exactly h_2-h_1. In particular, if h_2 \lt h_1 it is always possible to make this movement without your energy falling negative.
A simple interpretation of the statement is to treat the points and costs as a weighted graph: create a graph with k+1 vertices (where the first k are the given points and the k+1-th is the destination), and edges as follows:
- Let h_i denote the height of the i-th point, as defined above.
- For 1 \leq u, v \leq k+1, if h_v \leq h_u + e_u, create an edge from u to v with weight c_u. Essentially, this says that we can move directly from u to v without having to reset energy at a different point.
The answer is now the shortest path from (0, 0) to (N, M) in this graph.
However, this graph can have \mathcal{\Omega}(k^2) edges, which is too many. We need to optimize the above solution a bit.
Let dist_i denote the shortest distance to point i. Let us also sort the points in increasing height.
We have the following observation:
- Under the above sort, dist_i \leq dist_j for i \leq j. This follows immediately from the very first point made, since we can always go to a lower height for no cost.
- Next, let’s look at how dijkstra would work on this graph. When at i, we only need to update some vertices greater than i. But, since vertices are sorted by height, we in fact update a contiguous range of indices, starting from i+1 - and all these updates are of the same value (namely, dist_i + c_i).
Updates of this form can be done with the help of a sweepline algorithm.
When we are at index i, we need to do the following:
- Find the largest index j such that h_j \leq h_i + e_i. This can be done with binary search.
- Now, for each i+1 \leq k \leq j, we need to set dist_k \gets \min(dist_k, dist_i + c_i).
- Looking at it differently, when we are at index i, dist_i is the minimum value over all updates that cover index i.
- So, we can maintain a set of the current updates and the expiry time of the update (i.e, the last position it is valid for, j in the first step). At position i, we do the following:
- Remove all updates from the set that have already expired before i.
- Set dist_i to be the minimum value among the updates set.
- Compute j as described in the first step.
- Insert dist_i + c_i to the updates set, and set it to expire at j+1
This solves the problem in \mathcal{O}(k\log k).
TIME COMPLEXITY
\mathcal{O}(k\log k) per test case.
CODE:
Setter's code (C++)
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
int T,n,m,k,x,y,c,e;
struct rocket
{
int h,e;
ll c;
rocket(){}
rocket(int h,ll c,int e):h(h),c(c),e(e) {}
};
struct cmp1
{
bool operator () (rocket x,rocket y)
{
return x.c>y.c;
}
};
struct cmp2
{
bool operator () (rocket x,rocket y)
{
return x.h>y.h;
}
};
priority_queue<rocket,vector<rocket>,cmp1> Q1;
priority_queue<rocket,vector<rocket>,cmp2> Q2;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
while(!Q1.empty()) Q1.pop();
while(!Q2.empty()) Q2.pop();
for(int i=1;i<=k;i++)
{
scanf("%d%d%d%d",&x,&y,&c,&e);
if(x+y) Q2.push(rocket(x+y,c,e));
else Q1.push(rocket(x+y,c,e));
}
while(!Q1.empty())
{
rocket x=Q1.top(),y;
if((ll)x.h+x.e>=n+m)
{
printf("%lld\n",x.c);
break;
}
Q1.pop();
if(Q2.empty()) continue;
y=Q2.top();
while((ll)x.h+x.e>=y.h)
{
Q2.pop();
y.c+=x.c;
Q1.push(y);
if(Q2.empty()) break;
else y=Q2.top();
}
}
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct rocket {
long long int x,y,c,e;
};
bool cmp(rocket &r1, rocket &r2) {
return ((r1.x + r1.y) < (r2.x + r2.y));
}
int main() {
int t;
cin >> t;
while(t--) {
long long int n, m, k;
cin >> n >> m >> k;
vector<rocket> v(k);
for(int i = 0; i < k; i++)
cin >> v[i].x >> v[i].y >> v[i].c >> v[i].e;
sort(v.begin(), v.end(), cmp);
assert(!v[0].x && !v[0].y);
priority_queue<pair<long long int, int>> pq;
int now = 0;
while(now < k && v[now].x + v[now].y == 0)
pq.push({-v[now].c, now}), now++;
long long int ans = 0;
while(!pq.empty()) {
long long int cost = -pq.top().first;
int id = pq.top().second;
pq.pop();
long long int mx = min(n + m, v[id].x + v[id].y + v[id].e);
if(mx == n + m) {
ans = cost;
break;
}
while(now < k && v[now].x + v[now].y <= mx) {
pq.push({-(cost + v[now].c), now});
now++;
}
}
cout << ans << "\n";
}
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m, k; cin >> n >> m >> k;
vector<array<ll, 3>> events;
for (int i = 0; i < k; ++i) {
ll x, y, c, e; cin >> x >> y >> c >> e;
events.push_back({x+y, c, e});
}
events.push_back({n+m, 0, 0});
sort(begin(events), end(events));
set<array<ll, 2>> active = {{0, 1}}, to_rem = {{1, 0}};
ll ans = 0;
for (auto [s, c, e] : events) {
while (!to_rem.empty()) {
auto [tm, val] = *to_rem.begin();
if (tm <= s) {
to_rem.erase(to_rem.begin());
active.erase({val, tm});
}
else break;
}
assert(!active.empty());
auto it = *active.begin();
if (s == n+m) {
ans = it[0];
break;
}
ll nxt = it[0] + c;
// from s+1 to s+e
active.insert({nxt, s+e+1});
to_rem.insert({s+e+1, nxt});
}
cout << ans << '\n';
}
}