Introduction to DP: Angry Cows

Problems and Contests
#1

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] ?
Need help in understanding USACO GOLD Angry Cow's solution
#2

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
#3

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
#4 
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
#5

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)

1 Like
#6

Would it be possible to elaborate on how you go from bs to 2p here? I’m sorry if I’m asking a very dumb question but I’ve spent more than an hour trying to prove it to myself to no avail.

#7

Do you get why this is true?

#8

Hey, thanks for the reply. Yes I understand why it’s true - if you could explode at j and bring down everything from 0 to i < j then the blast at i would have been at most of the same power so we have an upper bound there, i.e. dp[0][i] is non-decreasing in i (i presume you didn’t claim it was strictly increasing).

I got to a point where I can run two for loops - one for i and a pointer on the right side maximizing the right explosion requiring at most the same power (effectively trying out all possible indices for the left-most initially blasted cow along with the most optimal right cow). I also did the symmetric thing on the right with a pointer on the left. Both are linear time and I can make sense of this - intuitively the optimal blast will affect [l, r] and one of the dp values will be larger (or equal) than the other so it’s provably true that the above approach will stumble on either l (if it had the greater dp value) or r (if not).

What I do not get is how walking both on the left and right guarantees we will always find the optimal positions.

#9

Isn’t that equivalent to the solution with one for loop? Whenever you move the right pointer to the left in the one for loop solution, that’s equivalent to moving the right pointer to the left in your first loop (and symmetrically for the other direction).

#10

My stumbling block here is precisely proving that it is ok to not have tried combinations with the right pointer at any of the values we skipped by moving it left. In other words, if we are a high dp value on the left, we will skip many right values potentially. In the two loop solution we would nevertheless check to see what blasts are possible with the right being at each of these values with the most optimal yet lower left dp value. I can imagine why the two pointers solution might work but I lack both proof and complete intuition.

My attempts at proof have begun by assuming the optimal blast is between l and r and wlog assuming we first reach l in the 2p one loop approach (we are narrowing down r-l with each step so we must eventually cross either l or r; we want to prove we will provably cross both)

Now, having reached l first, the previous step must have judged that moving whatever the right pointer at the time is, call it r1, would have led to a bigger dp value on the right than the dp value at l, i.e. dp[0][i] < dp[1][r1-1].

We must now observe that r < r1 for sure (basically because we otherwise wouldn’t have reached i first)

My problem now is proving that we will reach r on the right while still staying out at i. Clearly the right dp value at r would be bigger than the left one at l by the above, but what guarantees that on the way to r we will not move i.

The two loop solution is intuitive to me because it essentially explores the possibilities that the at the optimal solution the max(left radius, right radius) comes from the left or from the right. First loop assumes it’s from the left and maximizes the right radius as long as it stays below (we can only improve the distance factor this way). But the one loop approach doesn’t have this nice interpretation

#11

if you end up moving l to the right before you get to r, that means that dp[0][l+1] < dp[1][r], in which case (l+1,r) is also an optimal solution.

Think of it as being equivalent to the binary search solution. The two pointers method will check all pairs $$(l,r)=(i,j)$$ that are considered by this algorithm as $$R$$ takes on all possible values: