Skip to content

3385. Minimum Time to Break Locks II 👍

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
 public:
  int findMinimumTime(vector<int>& strength) {
    vector<vector<int>> costs;

    for (int turn = 1; turn <= strength.size(); ++turn) {
      vector<int> cost;
      for (const int s : strength)
        cost.push_back((s + turn - 1) / turn);
      costs.push_back(cost);
    }

    return hungarian(costs).back();
  }

 private:
  // Updates the currentMinimum if potentialMinimum is smaller and returns true.
  bool updateMinimum(int& currentMinimum, const int& potentialMinimum) {
    if (potentialMinimum < currentMinimum) {
      currentMinimum = potentialMinimum;
      return true;
    }
    return false;
  }

  // Returns an array `res` of length n (costs.length), with `res[i]` equaling
  // the minimum cost to assign the first (i + 1) turns to the first (i + 1)
  // locks using Hungarian algorithm, where costs[i][j] is the energy required
  // to break j-th lock in i-th turn.
  //
  // https://en.wikipedia.org/wiki/Hungarian_algorithm
  vector<int> hungarian(const vector<vector<int>>& costs) {
    const int numLocks = costs.size();
    vector<int> res;
    vector<int> lockAssignments(numLocks + 1, -1);
    vector<int> turnPotentials(numLocks);
    vector<int> lockPotentials(numLocks + 1);

    for (int currentTurn = 0; currentTurn < numLocks; ++currentTurn) {
      int currentLock = numLocks;
      lockAssignments[currentLock] = currentTurn;
      vector<int> minReducedCosts(numLocks + 1, INT_MAX);
      vector<int> previousLockAssignments(numLocks + 1, -1);
      vector<bool> locksInOptimalPath(numLocks + 1);

      while (lockAssignments[currentLock] != -1) {
        locksInOptimalPath[currentLock] = true;
        const int assignedTurn = lockAssignments[currentLock];
        int minCostDelta = INT_MAX;
        int nextLock;

        for (int lock = 0; lock < numLocks; ++lock)
          if (!locksInOptimalPath[lock]) {
            const int reducedCost = costs[assignedTurn][lock] -
                                    turnPotentials[assignedTurn] -
                                    lockPotentials[lock];
            if (updateMinimum(minReducedCosts[lock], reducedCost))
              previousLockAssignments[lock] = currentLock;
            if (updateMinimum(minCostDelta, minReducedCosts[lock]))
              nextLock = lock;
          }

        for (int lock = 0; lock <= numLocks; ++lock)
          if (locksInOptimalPath[lock]) {
            turnPotentials[lockAssignments[lock]] += minCostDelta;
            lockPotentials[lock] -= minCostDelta;
          } else {
            minReducedCosts[lock] -= minCostDelta;
          }

        currentLock = nextLock;
      }

      for (int lock; currentLock != numLocks; currentLock = lock)
        lockAssignments[currentLock] =
            lockAssignments[lock = previousLockAssignments[currentLock]];

      res.push_back(-lockPotentials[numLocks]);
    }

    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
  public int findMinimumTime(int[] strength) {
    int[][] costs = new int[strength.length][strength.length];
    for (int turn = 1; turn <= strength.length; ++turn)
      for (int j = 0; j < strength.length; j++)
        costs[turn - 1][j] = (strength[j] + turn - 1) / turn;
    return hungarian(costs)[costs.length - 1];
  }

  // Updates the currentMinimum if potentialMinimum is smaller and returns true.
  private boolean updateMinimum(int[] currentMinimum, int potentialMinimum, int index) {
    if (potentialMinimum < currentMinimum[index]) {
      currentMinimum[index] = potentialMinimum;
      return true;
    }
    return false;
  }

  // Returns an array `res` of length n (costs.length), with `res[i]` equaling
  // the minimum cost to assign the first (i + 1) turns to the first (i + 1)
  // locks using the Hungarian algorithm, where costs[i][j] is the energy required
  // to break j-th lock in i-th turn.
  //
  // https://en.wikipedia.org/wiki/Hungarian_algorithm
  private int[] hungarian(int[][] costs) {
    final int numLocks = costs.length;
    int[] res = new int[numLocks];
    int[] turnPotentials = new int[numLocks];
    int[] lockPotentials = new int[numLocks + 1];
    int[] lockAssignments = new int[numLocks + 1];
    Arrays.fill(lockAssignments, -1);

    for (int currentTurn = 0; currentTurn < numLocks; ++currentTurn) {
      int currentLock = numLocks;
      lockAssignments[currentLock] = currentTurn;
      int[] minReducedCosts = new int[numLocks + 1];
      Arrays.fill(minReducedCosts, Integer.MAX_VALUE);
      int[] previousLockAssignments = new int[numLocks + 1];
      boolean[] locksInOptimalPath = new boolean[numLocks + 1];

      while (lockAssignments[currentLock] != -1) {
        locksInOptimalPath[currentLock] = true;
        int assignedTurn = lockAssignments[currentLock];
        int minCostDelta = Integer.MAX_VALUE;
        int nextLock = -1;

        for (int lock = 0; lock < numLocks; ++lock)
          if (!locksInOptimalPath[lock]) {
            final int reducedCost =
                costs[assignedTurn][lock] - turnPotentials[assignedTurn] - lockPotentials[lock];
            if (updateMinimum(minReducedCosts, reducedCost, lock))
              previousLockAssignments[lock] = currentLock;
            if (minReducedCosts[lock] < minCostDelta) {
              minCostDelta = minReducedCosts[lock];
              nextLock = lock;
            }
          }

        for (int lock = 0; lock <= numLocks; ++lock)
          if (locksInOptimalPath[lock]) {
            turnPotentials[lockAssignments[lock]] += minCostDelta;
            lockPotentials[lock] -= minCostDelta;
          } else {
            minReducedCosts[lock] -= minCostDelta;
          }

        currentLock = nextLock;
      }

      for (int lock; currentLock != numLocks; currentLock = lock)
        lockAssignments[currentLock] = lockAssignments[lock = previousLockAssignments[currentLock]];

      res[currentTurn] = -lockPotentials[numLocks];
    }

    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution:
  def findMinimumTime(self, strength: list[int]) -> int:
    costs = [[(s + turn - 1) // turn
             for s in strength]
             for turn in range(1, len(strength) + 1)]
    return self._hungarian(costs)[-1]

  def _hungarian(self, costs):
    """
    Returns an array `res` of length n (costs.length), with `res[i]` equaling
    the minimum cost to assign the first (i + 1) turns to the first (i + 1)
    locks using Hungarian algorithm, where costs[i][j] is the energy required
    to break j-th lock in i-th turn.

    https://en.wikipedia.org/wiki/Hungarian_algorithm
    """
    numLocks = len(costs)
    turnPotentials = [0] * numLocks
    lockPotentials = [0] * (numLocks + 1)
    lockAssignments = [-1] * (numLocks + 1)
    res = []

    for currentTurn in range(numLocks):
      currentLock = numLocks
      lockAssignments[currentLock] = currentTurn
      minReducedCosts = [math.inf] * (numLocks + 1)
      previousLockAssignments = [-1] * (numLocks + 1)
      locksInOptimalPath = [False] * (numLocks + 1)

      while lockAssignments[currentLock] != -1:
        locksInOptimalPath[currentLock] = True
        assignedTurn = lockAssignments[currentLock]
        minCostDelta = math.inf
        nextLock = None

        for lock in range(numLocks):
          if not locksInOptimalPath[lock]:
            reducedCost = (
                costs[assignedTurn][lock] -
                turnPotentials[assignedTurn] -
                lockPotentials[lock]
            )
            oldMin = minReducedCosts[lock]
            minReducedCosts[lock] = min(oldMin, reducedCost)
            if minReducedCosts[lock] < oldMin:
              previousLockAssignments[lock] = currentLock
            if minReducedCosts[lock] < minCostDelta:
              minCostDelta = minReducedCosts[lock]
              nextLock = lock

        for lock in range(numLocks + 1):
          if locksInOptimalPath[lock]:
            turnPotentials[lockAssignments[lock]] += minCostDelta
            lockPotentials[lock] -= minCostDelta
          else:
            minReducedCosts[lock] -= minCostDelta

        currentLock = nextLock

      while currentLock != numLocks:
        lockAssignments[currentLock] = lockAssignments[previousLockAssignments[currentLock]]
        currentLock = previousLockAssignments[currentLock]

      res.append(-lockPotentials[numLocks])

    return res