Official Analysis (C++)

Video Solution

By Vivian Han

Explanation

Suppose that early in the hike, there is a rest stop with tastiness $A$, but later there is a rest stop with tastiness $B$ where $B>A$. Then, it is never optimal for Bessie to spend any time at the first rest stop with tastiness $A$. If she did, she could spend the same amount of time at the later rest stop instead and earn more tastiness units; she would still never be behind Farmer John. So, the only rest stops that Bessie might stop at are those that have more tastiness than any subsequent rest stops.

We can find these "right-maximal" rest stops in a single right-to-left (or end-to-start) scan, keeping track of the largest tastiness seen so far. If the current stop exceeds the largest value seen so far, it is "right-maximal."

Now, we can perform a greedy algorithm: never stop at non-right-maximal rest stops. Bessie should stop at a right-maximal rest stop as long as possible (i.e., until Farmer John catches up with her). Then she proceeds until the next right-maximal rest stop.

To see the correctness of this greedy algorithm, suppose Bessie did not spend as long as possible at some right-maximal rest stop $R$. Then she would leave this rest stop $t$ seconds early, for some positive $t$. Suppose the next place Bessie stops is rest stop $r$. We could improve Bessie's tastiness intake by having her spend $1$ less second at $r$, and $1$ more second at rest stop $R$. It can be verified that Bessie will still never be behind Farmer John, and since the tastiness at $R$ is greater than the tastiness at $r$, we improved Bessie's outcome. Therefore no optimal solution will leave a right-maximal rest stop early, and our greedy algorithm is correct.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	ifstream in("reststops.in");

	int trail_len;  // not used

Copy
import java.io.*;

public class RestStops {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("reststops.in"));

		String[] line = br.readLine().split(" ");
		int trailLen = Integer.parseInt(line[0]);  // never used
		int stopNum = Integer.parseInt(line[1]);
		int fRate = Integer.parseInt(line[2]);

Copy
with open("reststops.in") as read:
	# trail_len won't be used
	trail_len, stop_num, f_rate, b_rate = [int(i) for i in read.readline().split()]

	x = []  # position of each stop
	c = []  # tastiness value of each stop
	for _ in range(stop_num):
		a, b = [int(i) for i in read.readline().split()]
		x.append(a)
		c.append(b)