javaalgorithm

Minimize Total Blocks Carried Before All Robots Shut Down


Here's the coding task:

You are commanding a team of robots. Each robot:

Can carry a certain number of blocks per second (carry[i])

Has a battery with some initial level (battery[i])

You also have a zapper that can target one robot per second, reducing its battery by k units. If a robot’s battery reaches 0 or below, it stops working and no longer contributes to the block carrying.

Each second:

You zap one robot (your choice).

All working robots carry blocks.

The goal is to zap robots in such a way that the total number of blocks carried before they all shut down (plus one final block to finish the mission) is minimized.

Example:
n = 2
carry   = [3, 4]
battery = [4, 6]
k = 3

One possible strategy:

Time    Blocks Carried  Zapped Robot    New Battery
1       3 + 4 = 7        B              6 → 3
2       3 + 4 = 7        B              3 → 0 ❌
3       3                A              4 → 1
4       3                A              1 → -2 ❌
5       1 (final)        —              —

Total blocks carried: 7 + 7 + 3 + 3 + 1 = 21

Rules: You can zap one robot per second

Robots stop working when battery ≤ 0

All working robots carry blocks every second

After all robots stop, you must carry one final block to complete the mission

Constraints:

1 ≤ n ≤ 10^5 (number of robots)

1 ≤ carry[i], battery[i] ≤ 5000

1 ≤ k ≤ 5000

This is an interview question asked in hackerrank, I dn't have a link of it to share here.

This is what I tried, but my code passed only 5 test cases out of 15 and remaining 10 test cases failed with wrong answer.

import java.util.*;

public class Main {
    public static long solve(List<Integer> carry, List<Integer> battery, int k) {
        int n = carry.size();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int c = carry.get(i);
            int b = battery.get(i);
            int t = (b + k - 1) / k; // ceil(h / k)
            list.add(new int[]{c, t});
        }
        
        list.sort((a, b) -> Integer.compare(b[0], a[0]));
        
        long result = 0;
        long currentActiveTime = 0;
        
        for (int[] e : list) {
            currentActiveTime += e[1];
            result += e[0] * currentActiveTime;
        }
        // Add the final concluding point
        result += 1;
        
        return result;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(3, 4), Arrays.asList(4, 6), 3)); // Should print 21
        
        System.out.println(solve(Arrays.asList(1, 2, 3), Arrays.asList(3, 2, 1), 2)); // Should print 12
        System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80), 
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // wrong output 17712
    }
}

I added some test cases in the main method with the expected answer, I added one sample test case, which is failing:

System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80), 
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // wrong output 17712

In log messages, I just found the input and output values, but the actual expected output is hidden for this test case.

Question: How can I minimize the total number of blocks carried before all robots stop (including the one final block)? Is there an efficient greedy or priority queue-based approach to solve this?


Solution

  • Consider 2 robots. The first has carrying capacity c1 and takes b1 zaps to kill. The second has carrying capacity c2 and take b2 zaps to kill.

    If we kill robot 1 first, and then immediately kill robot 2, the total blocks carried by those robots during the killing time is:

    c1 * b1 + c2 * (b1 + b2)

    On the other hand, if will kill robot 2 first and then immediately kill robot 1, the total blocks carried is:

    c1 * (b1 + b2) + c2 * b2

    It's advantageous to kill robot 1 first if:

    c1 * b1 + c2 * (b1 + b2) < c1 * (b1 + b2) + c2 * b2

    <=> c2 * b1 < c1 * b2

    <=> c1/b1 > c2/b2

    So for any two robots killed adjacently, we should kill the one with the highest capacity:battery ratio first, where battery is measured in zaps-to-kill.

    Since this relation is transitive (c1/b1 < c2/b2 and c2/b2 < c3/b3 => c1/b1 < c3/b3), establishing the proper order for each adjacent pair establishes the proper order for the whole list...

    Sort the robots in order of decreasing capacity:battery ratio, and kill them in that order.