Problem: running_on_fumes_ch1 (2020 quals)

**Note: This problem shares similarities with [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2020/qualification-round/problems/D2). The solution to either chapter may help with solving the other, so please consider reading both first.**

You just landed yourself a gig as a delivery driver for a nationwide supply chain. You've been assigned a series of long-haul jobs, so it's time to get to work.

For each job, you will be provided with a map of the relevant region, which includes \(N\) cities (numbered from 1 to \(N\)) and \(N-1\) two-way roads running amongst them. **The cities are connected by roads in a single line**, such that there's a road between each pair of consecutive cities. In other words, cities \(i\) and \(j\) are directly connected by a road if and only if \(|i - j| = 1\).

You will begin in city \(1\) with a shipment of supplies to be delivered to city \(N\), and with a full gas tank having a capacity of \(M\) gallons. You will then have two options at each point in time:

  1. Drive along a road from your current city to an adjacent one, using up 1 gallon of gas. You may not do this if your tank is empty, but it's fine if your tank becomes empty as a result.
  2. Fill your tank all the way back up to \(M\) gallons of gas at a cost of \(C_i\) dollars, where \(i\) is your current city. Note that the cost is independent of how much gas your tank had before refueling. You may not do this if city \(i\) has no gas station (indicated with \(C_i = 0\)).

Determine the minimum cost required to arrive at city \(N\), if it's possible at all.

# Input

Input begins with an integer \(T\), the number of long-haul jobs you've been assigned. For each job there is first a line containing the space-separated integers \(N\) and \(M\). Then, \(N\) lines follow, the \(i\)th of which contains the single integer \(C_i\).

# Output

For the \(i\)th job, output a line containing *"Case #i: "* followed by a single integer, the minimum cost in dollars to get from city 1 to city \(N\), or \(-1\) if it's impossible.

# Constraints

\(1 \le T \le 85\)
\(2 \le N \le 1,000,000\)
\(1 \le M \le N\)
\(0 \le C_i \le 1,000,000,000\)

The sum of \(N\) across all jobs is at most 4,000,000.

# Sample Explanation

In the first job, you will begin in city 1 with 3 gallons of gas. You cannot drive all the way to your destination (city 5) without refueling along the way, as that would require a total of 4 gallons of gas. The cheapest option is to drive to city 2, top up your tank for a cost of $20, and then drive through cities 3 and 4 before reaching city 5 with no more gas to spare.

In the second job, your gas tank only has a capacity of 2 gallons. In this case, the cheapest strategy involves depleting all of your gas to drive to city 3, refueling there for $30, and then depleting all of your gas to reach city 5.

In the third job, your gas tank only has a capacity of 1 gallon. No matter what you do, you will deplete all of your gas in the drive from city 3 to city 4, where there will be no way to refuel to reach city 5.


Sample input:
7
5 3
0
20
30
0
10
5 2
0
20
30
0
10
5 1
0
20
30
0
10
4 1
99
88
77
66
4 4
99
88
77
66
6 2
0
0
20
30
0
10
12 3
0
1
4
7
0
5
9
8
0
3
0
6


Sample output:
Case #1: 20
Case #2: 30
Case #3: -1
Case #4: 165
Case #5: 0
Case #6: 50
Case #7: 19


Solution: We first observe that it's never beneficial to move back to a lower-indexed city — we'll only move forwards through the \(N\) cities in order.
 
Let \(F_i\) be the minimum cost required to be at city \(i\) with a full tank of gas, and \(G_i\) be the minimum cost required to arrive at city \(i\) at all (with each equal to \(\infty\) if unachievable). Our answer will be \(G_N\).

We know that \(F_1 = G_1 = 0\). For each \(i > 1\), \(G_i\) is equal to the minimum value of \(F_j\) across all cities \(j\) such that it's possible to drive directly from \(j\) to \(i\) on a single tank of gas (in other words, such that \(max(i-M,1) \le j < i\)). \(F_i\) is then simply equal to \(G_i + C_i\) if \(C_i \ne 0\), or is equal to \(\infty\) otherwise.

Since each \(G\) and \(F\) value only depends on previous ones, this suggests an approach involving iterating over the cities in order from \(1\) to \(N\) and simply computing their \(G\) and \(F\) values along the way. However, a direct implementation of the above would be too inefficient, involving considering up to \(M\) prior \(F\) values in order to compute each \(G\) value and yielding a time complexity of \(O(N*M)\).

We can improve on this through observations around which \(F\) values may be relevant when computing subsequent \(G\) values. If there exists a pair of cities \(i\) and \(j\) such that \(i < j\) and \(F_i \ge F_j\), then we can disregard \(F_i\) going forward, as \(F_j\) will always be at least as beneficial.

This suggests that we can maintain an ordered list \(L\) of cities which may ever be relevant, which have both increasing indices and increasing \(F\) values. As we iterate over the \(N\) cities, we should remove the earliest cities from \(L\) once they become too far back to still be used for the current city's \(G\) value, we should append new cities onto the end of \(L\) when we compute their \(F\) values, and right before appending each such city, we should remove cities from \(L\) which will never be relevant anymore (due to having an \(F\) value larger than or equal to the new city). We can then compute each current city's \(G\) value in just \(O(1)\) time (by using the \(F\) value of the earliest city in \(L\), which must be the minimum one). Given the operations involved, representing \(L\) as a deque is most convenient.

Every city will be added to and removed from \(L\) at most once, and we'll perform only a constant number of other operations while computing each city's \(F\) and \(G\) values. Therefore, the time complexity of this solution is \(O(N)\).


Code: // Running on Fumes - Chapter 1
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x)
{
  char c, r = 0, n = 0;
  x = 0;
  for (;;)
  {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else
      if ((c >= '0') && (c <= '9'))
        x = x * 10 + c - '0', r = 1;
      else
        if (r)
          break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 1000008
#define IMP 1e18

int N, M;
int C[LIM];
deque<pair<int, LL>> D; // <city, min. cost to be there with full tank>

LL ProcessCase()
{
  int i;
  // input
  Read(N), Read(M);
  Fox(i, N)
    Read(C[i]);
  // iterate over cities while maintaining deque of min. costs
  D.clear();
  D.push_back(mp(0, 0));
  Fox(i, N)
  {
    // remove entries too far back to reach current city
    while (!D.empty() && D.front().x < i - M)
      D.pop_front();
    // impossible to make it this far?
    if (D.empty())
      return(-1);
    // consider refueling here
    if (C[i])
    {
      LL d = D.front().y + C[i];
      // remove no-longer-relevant entries
      while (!D.empty() && d <= D.back().y)
        D.pop_back();
      D.push_back(mp(i, d));
    }
  }
  return(D.front().y);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %lld\n", t, ProcessCase());
  return(0);
}