ROCKET_PACK - Editorial

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';
	}
}
2 Likes

I used segment tree to solve it. It’s range-query and point-update.
dis[x_i+y_i] = min(dis[x_i+y_i],...,dis[inf]),then update dis[x_i+y_i+E_i] with dis[x_i+y_i]+C_i.
The only thing I want to mention is that I got pass at 2:59:56…

2 Likes

I thought of using segment tree with dp. I noticed that hi <= hj + ej (energy) and in an optimal solution, hj+ej would have to be increasing. So, I sorted the points by hj+ej and did dp with segment tree to find furthest point back for which hk+ek>=hj, but I get WA. Is this assumption wrong?

There may be some issues in the Editorialist’s code. Since x and y in this problems are less than 2e9 in this problem, so x +y may overflow in int range.

You are correct, the code I linked there is indeed slightly wrong.

In fact, an earlier version of the problem had the limits as 10^9, and my code is for that version. The limits were updated just before the contest started because the test data was found to be a bit weak and more tests were added, which I didn’t notice while writing the editorial.

At any rate, thanks for noticing this. I’ve updated my code to be correct.

1 Like

Never mind, there was integer overflow in my code.

Nice question!

Can this problem be solved using DP and binary search?
My solution is O(n * n), just want to confirm wether my approach is correct or not?
My submission

The solution detailed in the editorial indeed uses dp and binary search, but you need something more to reduce the complexity from \mathcal{O}(N^2) to \mathcal{O}(N\log N).