Welcome to Subscribe On Youtube
3385. Minimum Time to Break Locks II 🔒
Description
Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the ith lock.
To break a lock, Bob uses a sword with the following characteristics:
- The initial energy of the sword is 0.
- The initial factor
Xby which the energy of the sword increases is 1. - Every minute, the energy of the sword increases by the current factor
X. - To break the
ithlock, the energy of the sword must reach at leaststrength[i]. - After breaking a lock, the energy of the sword resets to 0, and the factor
Xincreases by 1.
Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.
Return the minimum time required for Bob to break all n locks.
Example 1:
Input: strength = [3,4,1]
Output: 4
Explanation:
| Time | Energy | X | Action | Updated X |
|---|---|---|---|---|
| 0 | 0 | 1 | Nothing | 1 |
| 1 | 1 | 1 | Break 3rd Lock | 2 |
| 2 | 2 | 2 | Nothing | 2 |
| 3 | 4 | 2 | Break 2nd Lock | 3 |
| 4 | 3 | 3 | Break 1st Lock | 3 |
The locks cannot be broken in less than 4 minutes; thus, the answer is 4.
Example 2:
Input: strength = [2,5,4]
Output: 6
Explanation:
| Time | Energy | X | Action | Updated X |
|---|---|---|---|---|
| 0 | 0 | 1 | Nothing | 1 |
| 1 | 1 | 1 | Nothing | 1 |
| 2 | 2 | 1 | Break 1st Lock | 2 |
| 3 | 2 | 2 | Nothing | 2 |
| 4 | 4 | 2 | Break 3rd Lock | 3 |
| 5 | 3 | 3 | Nothing | 3 |
| 6 | 6 | 3 | Break 2nd Lock | 4 |
The locks cannot be broken in less than 6 minutes; thus, the answer is 6.
Constraints:
n == strength.length1 <= n <= 801 <= strength[i] <= 106n == strength.length
Solutions
Solution 1
-
class MCFGraph { static class Edge { int src, dst, cap, flow, cost; Edge(int src, int dst, int cap, int flow, int cost) { this.src = src; this.dst = dst; this.cap = cap; this.flow = flow; this.cost = cost; } } static class _Edge { int dst, cap, cost; _Edge rev; _Edge(int dst, int cap, int cost) { this.dst = dst; this.cap = cap; this.cost = cost; this.rev = null; } } private int n; private List<List<_Edge>> graph; private List<_Edge> edges; public MCFGraph(int n) { this.n = n; this.graph = new ArrayList<>(); this.edges = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } } public int addEdge(int src, int dst, int cap, int cost) { assert (0 <= src && src < n); assert (0 <= dst && dst < n); assert (0 <= cap); int m = edges.size(); _Edge e = new _Edge(dst, cap, cost); _Edge re = new _Edge(src, 0, -cost); e.rev = re; re.rev = e; graph.get(src).add(e); graph.get(dst).add(re); edges.add(e); return m; } public Edge getEdge(int i) { assert (0 <= i && i < edges.size()); _Edge e = edges.get(i); _Edge re = e.rev; return new Edge(re.dst, e.dst, e.cap + re.cap, re.cap, e.cost); } public List<Edge> edges() { List<Edge> result = new ArrayList<>(); for (int i = 0; i < edges.size(); i++) { result.add(getEdge(i)); } return result; } public int[] flow(int s, int t, Integer flowLimit) { List<int[]> result = slope(s, t, flowLimit); return result.get(result.size() - 1); } public List<int[]> slope(int s, int t, Integer flowLimit) { assert (0 <= s && s < n); assert (0 <= t && t < n); assert (s != t); if (flowLimit == null) { flowLimit = graph.get(s).stream().mapToInt(e -> e.cap).sum(); } int[] dual = new int[n]; Tuple[] prev = new Tuple[n]; List<int[]> result = new ArrayList<>(); result.add(new int[] {0, 0}); while (true) { if (!refineDual(s, t, dual, prev)) { break; } int f = flowLimit; int v = t; while (prev[v] != null) { Tuple tuple = prev[v]; int u = tuple.first; _Edge e = tuple.second; f = Math.min(f, e.cap); v = u; } v = t; while (prev[v] != null) { Tuple tuple = prev[v]; int u = tuple.first; _Edge e = tuple.second; e.cap -= f; e.rev.cap += f; v = u; } int c = -dual[s]; result.add(new int[] { result.get(result.size() - 1)[0] + f, result.get(result.size() - 1)[1] + f * c}); if (c == result.get(result.size() - 2)[1]) { result.remove(result.size() - 2); } } return result; } private boolean refineDual(int s, int t, int[] dual, Tuple[] prev) { PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); pq.add(new int[] {0, s}); boolean[] visited = new boolean[n]; Integer[] dist = new Integer[n]; Arrays.fill(dist, null); dist[s] = 0; while (!pq.isEmpty()) { int[] current = pq.poll(); int distV = current[0]; int v = current[1]; if (visited[v]) continue; visited[v] = true; if (v == t) break; int dualV = dual[v]; for (_Edge e : graph.get(v)) { int w = e.dst; if (visited[w] || e.cap == 0) continue; int reducedCost = e.cost - dual[w] + dualV; int newDist = distV + reducedCost; Integer distW = dist[w]; if (distW == null || newDist < distW) { dist[w] = newDist; prev[w] = new Tuple(v, e); pq.add(new int[] {newDist, w}); } } } if (!visited[t]) return false; int distT = dist[t]; for (int v = 0; v < n; v++) { if (visited[v]) { dual[v] -= distT - dist[v]; } } return true; } static class Tuple { int first; _Edge second; Tuple(int first, _Edge second) { this.first = first; this.second = second; } } } class Solution { public int findMinimumTime(int[] strength) { int n = strength.length; int s = n * 2; int t = s + 1; MCFGraph g = new MCFGraph(t + 1); for (int i = 0; i < n; i++) { g.addEdge(s, i, 1, 0); g.addEdge(i + n, t, 1, 0); for (int j = 0; j < n; j++) { g.addEdge(i, j + n, 1, (strength[i] - 1) / (j + 1) + 1); } } return g.flow(s, t, n)[1]; } } -
class MCFGraph: class Edge(NamedTuple): src: int dst: int cap: int flow: int cost: int class _Edge: def __init__(self, dst: int, cap: int, cost: int) -> None: self.dst = dst self.cap = cap self.cost = cost self.rev: Optional[MCFGraph._Edge] = None def __init__(self, n: int) -> None: self._n = n self._g: List[List[MCFGraph._Edge]] = [[] for _ in range(n)] self._edges: List[MCFGraph._Edge] = [] def add_edge(self, src: int, dst: int, cap: int, cost: int) -> int: assert 0 <= src < self._n assert 0 <= dst < self._n assert 0 <= cap m = len(self._edges) e = MCFGraph._Edge(dst, cap, cost) re = MCFGraph._Edge(src, 0, -cost) e.rev = re re.rev = e self._g[src].append(e) self._g[dst].append(re) self._edges.append(e) return m def get_edge(self, i: int) -> Edge: assert 0 <= i < len(self._edges) e = self._edges[i] re = cast(MCFGraph._Edge, e.rev) return MCFGraph.Edge(re.dst, e.dst, e.cap + re.cap, re.cap, e.cost) def edges(self) -> List[Edge]: return [self.get_edge(i) for i in range(len(self._edges))] def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> Tuple[int, int]: return self.slope(s, t, flow_limit)[-1] def slope( self, s: int, t: int, flow_limit: Optional[int] = None ) -> List[Tuple[int, int]]: assert 0 <= s < self._n assert 0 <= t < self._n assert s != t if flow_limit is None: flow_limit = cast(int, sum(e.cap for e in self._g[s])) dual = [0] * self._n prev: List[Optional[Tuple[int, MCFGraph._Edge]]] = [None] * self._n def refine_dual() -> bool: pq = [(0, s)] visited = [False] * self._n dist: List[Optional[int]] = [None] * self._n dist[s] = 0 while pq: dist_v, v = heappop(pq) if visited[v]: continue visited[v] = True if v == t: break dual_v = dual[v] for e in self._g[v]: w = e.dst if visited[w] or e.cap == 0: continue reduced_cost = e.cost - dual[w] + dual_v new_dist = dist_v + reduced_cost dist_w = dist[w] if dist_w is None or new_dist < dist_w: dist[w] = new_dist prev[w] = v, e heappush(pq, (new_dist, w)) else: return False dist_t = dist[t] for v in range(self._n): if visited[v]: dual[v] -= cast(int, dist_t) - cast(int, dist[v]) return True flow = 0 cost = 0 prev_cost_per_flow: Optional[int] = None result = [(flow, cost)] while flow < flow_limit: if not refine_dual(): break f = flow_limit - flow v = t while prev[v] is not None: u, e = cast(Tuple[int, MCFGraph._Edge], prev[v]) f = min(f, e.cap) v = u v = t while prev[v] is not None: u, e = cast(Tuple[int, MCFGraph._Edge], prev[v]) e.cap -= f assert e.rev is not None e.rev.cap += f v = u c = -dual[s] flow += f cost += f * c if c == prev_cost_per_flow: result.pop() result.append((flow, cost)) prev_cost_per_flow = c return result class Solution: def findMinimumTime(self, a: List[int]) -> int: n = len(a) s = n * 2 t = s + 1 g = MCFGraph(t + 1) for i in range(n): g.add_edge(s, i, 1, 0) g.add_edge(i + n, t, 1, 0) for j in range(n): g.add_edge(i, j + n, 1, (a[i] - 1) // (j + 1) + 1) return g.flow(s, t, n)[1]