DIEHARD - DIE HARD

The problem, simply

You start with health H and armor A. Every unit of time you must jump to one of three places, and you can never stay in the same place two units of time in a row:

• Air: health +3, armor +2.
• Water: health -5, armor -10.
• Fire: health -20, armor +5.

You die as soon as health or armor reaches 0 or less. Give back the largest number of jumps you can make and still be alive. (This is SPOJ DIEHARD.)

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every path, and remember answers you already worked out. From a state (health, armor, last place), try each place you may jump to. If you survive the jump, the answer is one more than the best answer from the new state.

class Solution {
    private static final int[] DH = {3, -5, -20};   // air, water, fire
    private static final int[] DA = {2, -10, 5};
    private final Map<Long, Integer> memo = new HashMap<>();

    public int maxTime(int H, int A) {
        return best(H, A, 3);                        // 3 means "not anywhere yet"
    }

    private int best(int h, int a, int last) {
        long key = ((long) h * 100000 + a) * 4 + last;
        Integer known = memo.get(key);
        if (known != null) return known;
        int ans = 0;
        for (int p = 0; p < 3; p++) {
            if (p == last) continue;                 // cannot stay in the same place
            int nh = h + DH[p], na = a + DA[p];
            if (nh > 0 && na > 0) ans = Math.max(ans, 1 + best(nh, na, p));
        }
        memo.put(key, ans);
        return ans;
    }
}

How long it takes: each different (health, armor, place) is solved once. There are about O(H * A) of them. Extra room: the memo table and the recursion, O(H * A).

Way 2: the clever way

Two facts make the choice easy.

1. Air is the only place that helps, and you can never be in air twice in a row. So the best plan is air, something, air, something, and so on. Start with air.
2. After air, pick water if you survive it (health above 5 and armor above 10 before the jump), because it costs less health than fire. Otherwise pick fire if health is above 20. Otherwise you are done.

Count the jumps as you go.

class Solution {
    public int maxTime(int H, int A) {
        int h = H, a = A, time = 0;
        while (true) {
            h += 3; a += 2; time++;                 // air: always safe and always first
            if (h > 5 && a > 10) {                  // water costs less, use it if we survive
                h -= 5; a -= 10; time++;
            } else if (h > 20) {                    // otherwise fire, if we survive
                h -= 20; a += 5; time++;
            } else {
                break;                              // nowhere safe to go
            }
        }
        return time;
    }
}

How long it takes: every air plus water or air plus fire round lowers health by at least 2, so there are at most about H / 2 rounds, O(H). Extra room: O(1).

Watch out for

• Dying means health or armor at 0 or below, so the checks are h > 5 (not >= 5) and a > 10.
• The first jump is always air, and it always works because you start with at least 1 of each.
• You count jumps, including the last air jump, even though nothing safe comes after it.

What interviewers ask next

• Prove the greedy is right. Any two jumps in a row must include at most one air. Replacing a fire by a water (when water is safe) leaves more health, and health is what runs out. A memo search over all states, like Way 1, agrees with the greedy on every start up to a few hundred.
• What if the numbers for each place were different? Then the greedy may not hold. Use the memo search, which works for any numbers.
• Could you write a formula? With these exact numbers, people have found closed forms, but the loop is already O(H) and much safer to get right.
• What if staying in place were allowed? Then you would sit in air forever, so the answer is infinite. The "must move" rule is what makes the problem.

Remember this

Grown-up words: the cushions are states of a small graph, remembering answers is memoization, and always taking the gentlest safe move is a greedy choice backed up by checking against the full search.