Algorithms : martix traversal variation
algorithm, data-structures
Solution
Construct complete grid of wires. Then destroy first M/2 wires. Check connectivity with depth-first search. If still connected, destroy M/4 more wires. If not, restore M/4 most recently destroyed wires. Continue this binary search until proper T is found.
Time complexity is determined by number of depth-first searches: O(log M) <= O(log N) and complexity of each depth-first search: O(N2).
Previous result may be improved with Disjoint-set data structure.
Construct complete grid of wires. Then destroy M wires as directed by arrays A, B, and C. Add the remaining connected components of the grid to disjoint-set data structure.
Then sequentially restore wires, starting from the last elements of these arrays and coming to their first elements. While doing this, find union of the sets remaining in disjoint-set structure. Stop when sets containing nodes (0, 0) and (N−1, N−1) are joined together.
If disjoint-set data structure uses union by rank and path compression approaches, time complexity of the whole algorithm is O(N2 α(N)), where α is the inverse Ackermann function. This is practically as good as O(N2).
Previous result may be improved if we use a graph, dual to the original grid of wires: node of the dual graph corresponds to face of the original graph, each edge of the dual graph intersects corresponding edge of the original graph. Two additional nodes will be needed: node L connected to every top and left node of the dual graph and node R connected to every bottom and right node.
If this dual graph contains a path from L to R, nodes (0, 0) and (N−1, N−1) cannot be connected to each other. If there is no path from L to R, nodes (0, 0) and (N−1, N−1) are connected.
Initially dual graph is completely disconnected. While removing edges from the original graph, we add corresponding edges to dual graph. At the same time we update disjoint-set data structure. Stop as soon as the sets containing nodes L and R are joined together.
This algorithm needs to visit elements of its input arrays A, B, and C only once, which makes it an Online algorithm.
The most limiting factor for time complexity is now the initialization time for the array of dual graph's nodes: O(N2). If there is a way to avoid this initialization, we get asymptotically more efficient O(M α(M)) algorithm. There are several approaches to initialization problem:
- Use this trick to initialize array in O(1) time. This gives O(M α(M)) worst case time algorithm. But in practice it is rarely possible to allocate memory without initializing it (for security reasons).
- Initialize array once and then use this algorithm many times. This gives O(M α(M)) amortized time algorithm.
- Use hash table to store dual graph's nodes. This gives O(M α(M)) expected time algorithm. Also this improves space complexity to O(M).
Problem
There is an N × N square mesh-shaped grid of wires, as shown in a figure below. Nodes of the grid are at points (X, Y), where X and Y are integers from 0 to N−1. An electric current flows through the grid, between the nodes at (0, 0) and (N−1, N−1). Initially, all the wires conduct the current, but the wires burn out at a rate of one per second. The burnouts are described by three zero-indexed arrays of integers, A, B and C, each of size M. For each moment T (0 ≤ T < M), in the T-th second the wire between nodes (A[T], B[T]) and: ``` (A[T], B[T] + 1), if C[T] = 0 or (A[T] + 1, B[T]), if C[T] = 1 ``` burns out. You can assume that the arrays describe existing wires, and that no wire burns out more than once. Your task is to determine when the current stops flowing between the nodes at (0,0) and (N−1,N−1). Write a function: ``` int wire_burnouts(int N, int A[], int M, int B[], int M2, int C[], int M3); ``` that, given integer N and arrays A, B and C, returns the number of seconds after which the current stops flowing between the nodes at (0, 0) and (N−1, N−1). If the current keeps flowing even after all M wires burn out, the function should return −1. For example, given N = 4, M = 9 and the following arrays: A[0] = 0 B [0] = 0 C[0] = 0 A1 = 1 B 1 = 1 C1 = 1 A2 = 1 B 2 = 1 C2 = 0 A[3] = 2 B [3] = 1 C[3] = 0 A[4] = 3 B [4] = 2 C[4] = 0 A[5] = 2 B [5] = 2 C[5] = 1 A[6] = 1 B [6] = 3 C[6] = 1 A[7] = 0 B [7] = 1 C[7] = 0 A[8] = 0 B [8] = 0 C[8] = 1 your function should return 8, because just after the eighth wire burns out, there is no connection between the nodes at (0, 0) and (N−1, N−1). This situation is shown in the following figure: Given N = 4, M = 1 and the following arrays: A[0] = 0 B [0] = 0 C[0] = 0 your function should return −1, because burning out a single wire cannot break the connection between the nodes at (0, 0) and (N−1, N−1). Assume that: ``` N is an integer within the range [1..400]; M is an integer within the range [0..2*N*(N−1)]; each element of array A is an integer within the range [0..N−1]; each element of array B is an integer within the range [0..N−1]; each element of array C is an integer within the range [0..1]. ``` Complexity: ``` expected worst-case time complexity is O(N2*log(N)); expected worst-case space complexity is O(N2), beyond input storage (not counting the storage required for input arguments). ```