DIEHARD - DIE HARD

Problem Statement

SPOJ Problem - DIEHARD

A soldier has initial health h and armor a. The soldier can move between three places:

1. Fire: Health decreases by 5, Armor decreases by 10
2. Water: Health increases by 3, Armor increases by 2
3. Air: Health increases by 2, Armor increases by 3

The soldier cannot stay in the same place consecutively and cannot visit the same place in two consecutive moves. The soldier dies when health ≤ 0 OR armor ≤ 0.

Find the maximum time (number of moves) the soldier can survive.

Note: Initially the soldier is not at any place.

Constraints:

• 1 ≤ h ≤ 1000
• 1 ≤ a ≤ 1000

Example:

• Input: h = 20, a = 8
• Output: 5
• Explanation: Water(23,10) → Air(25,13) → Water(28,15) → Air(30,18) → Water(33,20) → Can't continue

Example 2:

• Input: h = 2, a = 10
• Output: 1

Approach 1: Brute Force (BFS/DFS Simulation)

Intuition

Simulate all possible sequences of moves using BFS or recursion. Track the maximum number of moves before the soldier dies.

Algorithm

1. Use BFS/DFS to explore all possible move sequences
2. At each state, track (health, armor, last_place, time)
3. Try all valid next moves (not same as last place)
4. Return maximum time achieved

import java.util.*;

public class Solution {
    private int[] dh = {-5, 3, 2};
    private int[] da = {-10, 2, 3};
    
    public int maxSurvivalTime(int h, int a) {
        int maxTime = 0;
        
        // BFS
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        // Start from any place
        for (int i = 0; i < 3; i++) {
            int nh = h + dh[i];
            int na = a + da[i];
            if (nh > 0 && na > 0) {
                queue.offer(new int[]{nh, na, i, 1});
            }
        }
        
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int health = state[0], armor = state[1];
            int lastPlace = state[2], time = state[3];
            
            String key = health + "," + armor + "," + lastPlace;
            if (visited.contains(key)) continue;
            visited.add(key);
            
            maxTime = Math.max(maxTime, time);
            
            for (int i = 0; i < 3; i++) {
                if (i == lastPlace) continue;
                
                int nh = health + dh[i];
                int na = armor + da[i];
                
                if (nh > 0 && na > 0) {
                    queue.offer(new int[]{nh, na, i, time + 1});
                }
            }
        }
        
        return maxTime;
    }
}

Complexity Analysis

• Time Complexity: O(h × w) - Bounded by distinct states
• Space Complexity: O(h × w) - Visited states

Approach 2: Greedy (Optimal Pattern)

Intuition

Key observation: Fire always decreases both health and armor significantly. The optimal strategy is to never visit Fire and alternate between Water and Air.

Analysis:

• Water: +3 health, +2 armor
• Air: +2 health, +3 armor
• Combined effect of Water + Air: +5 health, +5 armor

The soldier should alternate between Water and Air to maximize survival time. Start with the place that better addresses the weaker stat.

Algorithm

1. Never visit Fire (it's always harmful)
2. Alternate between Water and Air
3. Start with Water if armor is more critical, else Air
4. Count moves until either health or armor would go ≤ 0

Actually, let me reconsider. The original state matters, and we need a cleaner approach:

Wait, the problem says health/armor can only go positive, not start from there. Let me reread...

Actually, the soldier starts with h and a, and we need to count valid moves. Let me reconsider:

public class Solution {
    public int maxSurvivalTime(int h, int a) {
        int time = 0;
        
        while (true) {
            // Try water first
            int nh = h + 3, na = a + 2;
            if (nh > 0 && na > 0) {
                h = nh; a = na;
                time++;
                
                // Now try air
                nh = h + 2; na = a + 3;
                if (nh > 0 && na > 0) {
                    h = nh; a = na;
                    time++;
                } else {
                    break;
                }
            } else {
                // Try air first
                nh = h + 2; na = a + 3;
                if (nh > 0 && na > 0) {
                    h = nh; a = na;
                    time++;
                    
                    nh = h + 3; na = a + 2;
                    if (nh > 0 && na > 0) {
                        h = nh; a = na;
                        time++;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        
        return time;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxSurvivalTime(20, 8));  // Output: 5
    }
}

Mathematical Formula Approach

Since we're alternating between Water and Air:

• Every 2 moves: +5 health, +5 armor
• We can calculate how many complete cycles possible

Dry Run Example

Complexity Analysis

• Time Complexity: O(min(h, w)) - Linear in input size at worst
• Space Complexity: O(1) - Constant extra space

Key Takeaways

1. Greedy Choice: Avoid fire, alternate between water and air
2. Pattern Recognition: Identify beneficial and harmful actions
3. Simulation vs Formula: Sometimes direct simulation is cleaner
4. State Analysis: Health and armor must both remain positive
5. Edge Cases: Initial health or armor might not allow any moves
6. Cycle Detection: Two-place alternation creates predictable cycles
7. SPOJ Tip: Always verify exact problem constraints