Introduction to DP: Angry Cows

Link to usaco page

Link to external sol

I understand everything up until
Finally, by scanning through the list of hay bales, we can use these two numbers to identify the best “crossover” point where we should set the initial explosion.
This part of the solution is given as follows:

int i = 0;
  int j = N - 1;
  int result = INF;
  while (i < j) {
    result = min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j])));
    if (DP[0][i + 1] < DP[1][j - 1]) {
      i++;
    } else {
      j--;
    }
  }

This code finds the best crossover point.
I don’t understand how this finds the best point.

  • How is min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j]))) supposed to end up being the answer?
  • Why is i incremented when it according to DP[0][i + 1] < DP[1][j - 1] ?

min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j]))) is the min blast radius you need if you say that the first blast engulfs cows i\ldots j.

To check whether a blast radius R works, consider the following algorithm:

  • find the maximum i such that DP[0][i] <= R-1
  • find the minimum j such that DP[1][j] <= R-1
  • check whether (A[j]-A[i])/2 <= R.

You can find the minimum such R by binary searching, or by using two pointers as the code above does (it works as because DP[0][i] increases as i increases; similarly, DP[0][j] increases as j decreases).

1 Like

Unrelated thoughts:

  • why is this in the DP section? I think it’s more accurately classified as greedy + two pointers despite the first solution using an array named “DP” :slight_smile:
  • why is this marked as “easy”? only had two USA pre-college fullsolves
  • both the second and third solutions in the analysis fail on the following test case:
2
0
1

The second one gives the wrong answer, the third gives runtime error.

1 Like
import java.io.*;
import java.util.*;

// 2016 jan gold
public final class GoldenFury {
    public static void main(String[] args) throws IOException {
        long start = System.currentTimeMillis();
        BufferedReader read = new BufferedReader(new FileReader("angry.in"));
        int hayNum = Integer.parseInt(read.readLine());
        TreeSet<Double> haybales = new TreeSet<>();
        for (int h = 0; h < hayNum; h++) {
            haybales.add(Double.parseDouble(read.readLine()));
        }

        double valid = -1;  // not taking any chances with floating point (greater precision)
        long loPower = 0;
        long hiPower = (long) (haybales.last() - haybales.first()) * 10L;
        while (loPower <= hiPower) {
            long midPower = (loPower + hiPower) / 2;
            if (canKillAll(midPower / 10.0, haybales)) {
                hiPower = midPower - 1;
                valid = midPower / 10.0;
            } else {
                loPower = midPower + 1;
            }
        }

        PrintWriter written = new PrintWriter("angry.out");
        written.printf("%.1f%n", valid);
        written.close();
        System.out.printf("%.1f%n", valid);
        System.out.printf("%d ms. boom.%n", System.currentTimeMillis() - start);
    }

    private static boolean canKillAll(double power, TreeSet<Double> haybales) {
        long lowerLoc = (long) ((double) haybales.first()) * 10L;
        long upperLoc = (long) ((double) haybales.last()) * 10L;
        while (lowerLoc <= upperLoc) {
            long mid = (lowerLoc + upperLoc) / 2;
            boolean leftValid = leftWipeout(power, mid / 10.0, haybales);
            boolean rightValid = rightWipeout(power, mid / 10.0, haybales);
            if (leftValid && rightValid) {
                return true;
            } else if (!leftValid) {
                upperLoc = mid - 1;
            } else {
                lowerLoc = mid + 1;
            }
        }
        return false;
    }

    private static boolean leftWipeout(double power, double pos, TreeSet<Double> haybales) {
        double firstBale = haybales.first();
        while (power > 0) {
            double leftest = haybales.ceiling(pos - power);
            if (leftest == firstBale) {
                return true;
            }
            if (pos <= leftest) {
                return false;
            }
            pos = leftest;
            power--;
        }
        return false;
    }

    private static boolean rightWipeout(double power, double pos, TreeSet<Double> haybales) {
        double lastBale = haybales.last();
        while (power > 0) {
            double righest = haybales.floor(pos + power);
            if (righest == lastBale) {
                return true;
            }
            if (righest <= pos) {
                return false;
            }
            pos = righest;
            power--;
        }
        return false;
    }
}

My solution uses essentially the same philosophy as the third solution and it still outputs the correct answer.

1 Like

The problem is no longer in intro to dp, it has been moved to silver => binary search.

New link, (for anyone in the future wanting to find it)