Problem LinkAuthor: Tianyi Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyHARD PrerequisitesFlows, Minimum Cut ProblemYou are given a grid consisting of $0$(white), $1$(black) and $?$(unknown). You are required to convert $?$ to $0$ or $1$ such that the following cost is maximised: $$\sum_{i=1}^{\mathrm{min}(N, M)} C_{B, i} \cdot B_i + C_{W, i} \cdot W_i\,.$$ where $B_i$ denotes the number of ways to select a black square of size $i$, $W_i$ denotes the number of ways to select a white square of size $i$ and $C_{B, i}$ and $C_{W, i}$ arrays is provided in input. ExplanationSubtask 1: N * M ≤ 10A simple brute force which converts each $?$ to $0$ or $1$ and calculates the cost of the board is sufficient to pass this subtask. The time complexity of the above approach is $O(2^{NM})$. Subtask 2, 3: N * M ≤ 500The constraints are small and since the problem is related with maximisation, it hints towards either dynamic programming or flows based solution generally. We will use minimum cut to solve this problem. In case you are not familiar with the topic or its usage in the problem, please you through this awesome video tutorial by Anudeep Nekkanti. Now, using the ideas similar in the video, we design the below algorithm.
To understand why the above algorithm works, we will reason cutting of each edge in terms of minimum cuts and the rewards/penalties it provides. It is sure that edges of weight INFINITY will never be considered in the minimum cut of the graph. So we consider the remaining 2 scenarios. This image shows the scenario where the edge containing white node (source) and the node representing an optimistic white square of length $L$ is cut. This implies one of the $?$ in the square chose to convert to $1$ instead of $0$. This can happen for whatever reason, for example  It might to costlier to cut the corresponding black edges to which the $?$ node also connects (such a node will exist otherwise there will be no path from white i.e. source to black i.e. sink). This case is similar to above case, just that instead one of the $?$ in the optimistic black square of length $L$ chose to convert to $0$ instead of $1$. Thus the minimum cut in the above graph will contain edges which tell that the optimistic square which we considered for being white or black will not be actually white or black in the optimal selection because one of $?$ chose to convert to opposite colour. We must thus remove this minimum optimistic answer we added to "initial ans" to obtain the solution to the problem. Let us now finally analyse the complexity of the above solution. For the worst case, the grid will only consist of $?$ as there are no edges coming out of $0$ or $1$ in the grid. Let $K = min(N, M)$. So there will be $N * M + (N  1) * (M  1) + \cdots + (N  K) * (M  K) = O(K^3)$ intermediate white and black nodes i.e. the ones connecting grid cells and also to the corresponding source or sink. For details of the proof, refer to this. The number of edges in the graph will be $O(K^4)$ as there can be maximum $O(L^2)$ edges from an intermediate node representing the square of length $L$. Using Dinic Algorithm which has the worst complexity of $O(V^2 * E)$, the overall complexity of the solution will be $O(K^{10})$ ~ $O({(N * M)}^3)$. The hidden constant factor is very low and Dinic's algorithm suffices to solve the problem. Extra ObservationNote that above solution using minimum cut also enables us to print one grid with required cost as well. The construction of such grid is simple. Just consider the edges from white (source) and black (sink) node to the intermediate nodes which are not part of the minimum cut. This means all the cells in the grid connected to it actually retained their preference to colour which was optimistically assigned before to them. Once, you are clear with the above idea, you can see the editorialist implementation below for help. It also contains the part for printing a possible grid with the conversion of $?$ to $0$ or $1$. Author's Editorial for the problemFeel free to share your approach, if it was somewhat different. Time Complexity$O({(N * M)}^3)$ Space Complexity$O({(N * M)}^3)$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 11 Jun, 02:30
