USACO 2021 January Contest, Platinum Problem 2. Minimum Cost Paths

USACO 2021 January Contest, Platinum Problem 2. Minimum Cost Paths

Farmer John's pasture can be regarded as an N×MN×M (2≤N≤1092≤N≤109, 2≤M≤2⋅1052≤M≤2⋅105) 2D grid of square "cells" (picture a huge chessboard). The cell at the xx-th row from the top and yy-th column from the right is denoted by (x,y)(x,y) for each x∈[1,N],y∈[1,M]x∈[1,N],y∈[1,M]. Furthermore, for each y∈[1,M]y∈[1,M], the yy-th column is associated with the cost cycy (1≤cy≤1091≤cy≤109).

Bessie starts at the cell (1,1)(1,1). If she is currently located at the cell (x,y)(x,y), then she may perform one of the following actions:

 

• If y<My<M, Bessie may move to the next column (increasing yy by one) for a cost of x2x2.
• If x<Nx<N, Bessie may move to the next row (increasing xx by one) for a cost of cycy.

Given QQ (1≤Q≤2⋅1051≤Q≤2⋅105) independent queries each of the form (xi,yi)(xi,yi) (xi∈[1,N],yi∈[1,M]xi∈[1,N],yi∈[1,M]), compute the minimum possible total cost for Bessie to move from (1,1)(1,1) to (xi,yi)(xi,yi).

 

 

 

SAMPLE INPUT:

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

SAMPLE OUTPUT:

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

The output in grid format:

 

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

 

 

Problem credits: Benjamin Qi

 USACO 2021 January Contest, Platinum Problem 2. Minimum Cost Paths 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Let ansy(x)ansy(x) denote the minimum cost to go from (1,1)(1,1) to (x,y)(x,y). The key observation is that for a fixed yy, the function ansyansy is concave up. Specifically, ansy[x]−ansy[x−1]≤ansy[x+1]−ansy[x]ansy[x]−ansy[x−1]≤ansy[x+1]−ansy[x].

To get ansy+1ansy+1 from ansyansy, we must

 

1. Set ansy+1(x)=ansy(x)+x2ansy+1(x)=ansy(x)+x2 for all xx.
2. Set ansy+1(x)=min(ansy+1(x),ansy+1(x−1)+cx)ansy+1(x)=min(ansy+1(x),ansy+1(x−1)+cx) for all xx.

The latter operation is equivalent to replacing a suffix of ansy+1ansy+1 with a straight line.

We can maintain the piecewise quadratic function ansyansy with a stack (similarly to convex hull trick). Whenever we perform the second operation, we pop some elements off the top of the stack and add a new element. To answer a query (x,y)(x,y), binary search on the stack corresponding to ansyansy to find the piece of the function that corresponds to xx and evaluate it.

 

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define f first 
#define s second

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}

ll sq(ll x) { return x*x; }

int N,M;
vector<pair<int,int>> todo[200005];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	vector<ll> C(M); for (ll& t: C) cin >> t;
	int Q; cin >> Q;
	vector<ll> ans(Q);
	for (int i = 0; i < Q; ++i) {
		int x,y; cin >> x >> y; --y;
		todo[y].push_back({x,i});
	}
	vector<pair<int,pair<int,ll>>> stk;
	for (int col = 0; col < M; ++col) {
		auto eval_pair = [&](const pair<int,ll>& a, ll x) {
			int pre_col = a.f;
			return sq(x)*(col-pre_col)+x*C[pre_col]+a.s;
		};
		auto eval = [&](int x) -> ll { // binary search to find corresponding stack element
			int fst_ind = fstTrue(0,(int)stk.size()-1,[&](int ind) {
				return stk[ind].f >= x; });
			return eval_pair(stk[fst_ind].s,x); // evaluate stack element at x
		};
		if (col) {
			while (stk.size() > 1) { // pop off stack
				int x = end(stk)[-2].f;
				pair<int,ll> lst = stk.back().s;
				ll val_at_x =          eval_pair(lst,x);
				ll val_at_x_plus_one = eval_pair(lst,x+1);
				if (val_at_x+C[col] < val_at_x_plus_one) {
					stk.pop_back();
					continue;
				}
				stk.back().f = fstTrue(x+1,stk.back().f-1,[&](int mid) {
					return eval_pair(lst,mid)+C[col] < eval_pair(lst,mid+1); });
				break;
			}
			if (stk.back().f < N) { // add to stack
				int x = stk.back().f;
				stk.push_back({N,{col,eval_pair(stk.back().s,x)-x*C[col]}});
			}
		} else { // initialize stack
			stk.push_back({1,{0,-C[0]}});
			stk.push_back({N,{0,-C[0]}});
		}
		for (pair<int,int> t: todo[col]) // answer all queries with y=col+1
			ans[t.s] = eval(t.f);
	}
	for (ll t: ans) cout << t << "\n";
}

[/hide]