GreedyProblem 28 of 35

Picking Up Chicks

Brute Force
Time: O(n × 2^n)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(n)

Problem Statement

Google Code Jam - Picking Up Chicks

There are n chicks on a road, each at position x[i] and moving towards a barn at position b with speed v[i]. You have t seconds to get at least k chicks into the barn.

You can swap any two adjacent chicks, but each swap takes time. Find the minimum number of swaps needed, or return "IMPOSSIBLE" if it can't be done.

Key Rule: A chick can only enter the barn if it reaches position b within time t.

Constraints:

  • 1 ≤ n ≤ 50
  • 1 ≤ k ≤ n
  • 0 ≤ x[i] < b
  • 1 ≤ v[i] ≤ 100
  • 1 ≤ t ≤ 1000

Example:

  • Input: n=5, k=3, b=10, t=5, x=[0,2,5,6,7], v=[1,1,4,1,1]
  • Output: 0
  • Explanation: Chicks at positions 0, 2, 5 can reach barn (5 needs 5×4=20 distance possible, has 5 to cover, OK). Wait, let me recalculate...

Example 2:

  • Input: n=5, k=3, b=10, t=5, x=[0,2,3,5,7], v=[2,1,1,1,4]
  • Output: 2

Approach 1: Brute Force (Try All Combinations)

Intuition

For each subset of k chicks, check if they can all reach the barn. For each valid subset, calculate minimum swaps needed to let them through. This approach explores all possibilities.

Algorithm

  1. Identify chicks that CAN reach the barn (distance ≤ v[i] × t)
  2. Generate all combinations of k such chicks
  3. For each combination, calculate swaps needed
  4. Return minimum swaps or IMPOSSIBLE
java
import java.util.*;

public class Solution {
    private int minSwaps = Integer.MAX_VALUE;
    
    public int pickingUpChicks(int n, int k, int b, int t, int[] x, int[] v) {
        // Find chicks that can reach barn
        List<Integer> reachable = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int distance = b - x[i];
            if ((long)v[i] * t >= distance) {
                reachable.add(i);
            }
        }
        
        if (reachable.size() < k) return -1;  // IMPOSSIBLE
        
        minSwaps = Integer.MAX_VALUE;
        findCombinations(reachable, 0, k, new ArrayList<>(), x, v, b, t);
        
        return minSwaps;
    }
    
    private void findCombinations(List<Integer> reachable, int idx, int k,
                                   List<Integer> current, int[] x, int[] v, int b, int t) {
        if (current.size() == k) {
            int swaps = calculateSwaps(current, reachable, x, v, b, t);
            minSwaps = Math.min(minSwaps, swaps);
            return;
        }
        
        if (idx >= reachable.size()) return;
        
        current.add(reachable.get(idx));
        findCombinations(reachable, idx + 1, k, current, x, v, b, t);
        current.remove(current.size() - 1);
        findCombinations(reachable, idx + 1, k, current, x, v, b, t);
    }
    
    private int calculateSwaps(List<Integer> selected, List<Integer> reachable,
                                int[] x, int[] v, int b, int t) {
        int swaps = 0;
        Set<Integer> selectedSet = new HashSet<>(selected);
        
        for (int i : reachable) {
            if (!selectedSet.contains(i)) {
                // Count how many selected chicks are behind this one
                for (int s : selected) {
                    if (s > i) swaps++;
                }
            }
        }
        
        return swaps;
    }
}

Complexity Analysis

  • Time Complexity: O(n × 2^n) - All subsets with calculations
  • Space Complexity: O(n) - For storing combinations

Approach 2: Greedy (Optimal)

Intuition

Process chicks from right to left (closest to barn first). For each chick that can reach the barn, count how many slower chicks (that can't reach) are ahead of it and need to be swapped past.

Key Insight:

  • Chicks closer to barn should be prioritized
  • A chick that can't reach the barn must be swapped with all chicks behind it that we want to save
  • Process from right to left, greedily picking the rightmost k reachable chicks

Algorithm

  1. Process chicks from right (closest to barn) to left
  2. For each chick, check if it can reach barn
  3. If YES and we need more chicks: add swaps for blocking chicks, increment count
  4. If YES and count reached k: return swaps
  5. If NO: increment blocking count
  6. If we can't find k chicks: return IMPOSSIBLE
java
public class Solution {
    public String pickingUpChicks(int n, int k, int b, int t, int[] x, int[] v) {
        int swaps = 0;
        int count = 0;
        int blocking = 0;
        
        // Process from right to left
        for (int i = n - 1; i >= 0 && count < k; i--) {
            long distance = b - x[i];
            
            if ((long)v[i] * t >= distance) {
                swaps += blocking;
                count++;
            } else {
                blocking++;
            }
        }
        
        if (count < k) {
            return "IMPOSSIBLE";
        }
        
        return String.valueOf(swaps);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] x = {0, 2, 5, 6, 7};
        int[] v = {1, 1, 4, 1, 1};
        System.out.println(sol.pickingUpChicks(5, 3, 10, 5, x, v));
    }
}

Dry Run Example

n=5, k=3, b=10, t=5 x = [0, 2, 5, 6, 7] v = [1, 1, 4, 1, 1] Check which chicks can reach barn (distance ≤ v[i] × t): - Chick 0: distance = 10-0 = 10, v×t = 1×5 = 5. 10 > 5, CAN'T reach - Chick 1: distance = 10-2 = 8, v×t = 1×5 = 5. 8 > 5, CAN'T reach - Chick 2: distance = 10-5 = 5, v×t = 4×5 = 20. 5 ≤ 20, CAN reach - Chick 3: distance = 10-6 = 4, v×t = 1×5 = 5. 4 ≤ 5, CAN reach - Chick 4: distance = 10-7 = 3, v×t = 1×5 = 5. 3 ≤ 5, CAN reach Process from right to left: i=4: Can reach. blocking=0, swaps+=0, count=1 i=3: Can reach. blocking=0, swaps+=0, count=2 i=2: Can reach. blocking=0, swaps+=0, count=3 count=3=k, done! Result: 0 swaps --- Example 2: n=5, k=3, b=10, t=5 x = [0, 2, 3, 5, 7] v = [2, 1, 1, 1, 4] Check reachability: - Chick 0: dist=10, v×t=10. CAN reach - Chick 1: dist=8, v×t=5. CAN'T reach - Chick 2: dist=7, v×t=5. CAN'T reach - Chick 3: dist=5, v×t=5. CAN reach - Chick 4: dist=3, v×t=20. CAN reach Process from right to left: i=4: Can reach. blocking=0, swaps=0, count=1 i=3: Can reach. blocking=0, swaps=0, count=2 i=2: Can't reach. blocking=1 i=1: Can't reach. blocking=2 i=0: Can reach. blocking=2, swaps+=2=2, count=3 count=3=k, done! Result: 2 swaps The two chicks at positions 2 and 3 that can't reach must be swapped past chick at position 0.

Complexity Analysis

  • Time Complexity: O(n) - Single pass through chicks
  • Space Complexity: O(1) - Only using constant extra space

Complete Code Jam Solution

Key Takeaways

  1. Greedy Ordering: Process chicks from closest to farthest from barn
  2. Blocking Concept: Track chicks that can't reach and block others
  3. Linear Solution: O(n) by processing right to left
  4. Reachability Check: distance ≤ speed × time
  5. Swap Counting: Each reachable chick must pass all blocking chicks behind it
  6. Early Termination: Stop once k reachable chicks are found
  7. Code Jam Format: Handle test cases with "Case #X:" prefix
Previous
GERGOVIA - Wine trading in Gergovia
Next
CHOCOLA - Chocolate