Since people are looking for editorials for the May Long Competition and I really enjoyed this problem I decided to describe my solution.
The most obvious part of the problem is that the final matrix A needs to be symmetric. That is clear from the first two test cases. After that it helped me to consider the first subtask.
First Subtask:
For the first subtask we have A_{ij}\in\{0,1\}. In this case we only need to consider connectivity. Here we will say that two nodes are connected if there exists a path between them. We then have a very important transitive property: If node i is connected to node j and node j is connected to node k then node i is connected to node k. In terms of minimum cuts that statement can be reformulated as:
If the i-j mincut cost is 1 and the j-k mincut cost is 1 then the i-k mincut cost is at least 1.
As a result the final A_{ij} will be at least equal to 1 if there is a path P=\{p_1=i,p_2,\dots,p_q=j\} such that A_{p_\ell p_{\ell+1}}=1 or A_{p_{\ell+1}p_\ell}=1 in the original matrix A for all 1\leq\ell< q. If we update only those components A_{ij} and set them to 1 then we get a matrix A that is associated with a forest (an acyclic graph that may or may not be connected). Given any such forest, the matrix A is given by
We note that the matrix A depends only on how the nodes are grouped into connected components (trees) and not on the structure of those components. Since this matrix satisfies our requirements and we only made changes that are necessary, it must be optimal.
The problem can now be solved using a disjoint-set data structure. We start with a set of nodes that are all in different sets. We then iterate over the elements of A. If the element A_{ij}=1 and the associated nodes i and j are in disjoint sets, we join those two sets. In the end we have a collection of disjoint sets, each of which represents a tree in the forest. Based on the sizes of the disjoint sets it is then easy to compute the total number of 1 s in the final matrix A.
Implementing this method is extremely easy if you have a disjoint-set data structure available. Here is a solution in Python:
https://www.codechef.com/viewsolution/18589852
Original Constraints:
To solve the problem with the original constraints we can use many of the same ideas but we iterate over the different values of the mincut. As an example let us assume that A contains values from \{0,1,2\}. In the optimal A no element will need to be larger than 2. To determine where 2 s will be located in the optimal A we can build a forest as before but only connecting nodes if the associated A_{ij}=2. After taking care of all of the stronger connections, we can then continue working with the weaker connections (A_{ij}=1).
To generalise this idea we can use a max-heap priority queue. We will loop over all elements of A and add them to the priority queue if they have a value that is greater than 0. We also need to keep track of the nodes associated with each value in the priority queue. To solve the problem then remove elements from the queue and process them in the order that they come out. Each new element is always one of the largest remaining values. If the associated nodes are not currently in the same set, we need to join those sets and account for the associated values in the final matrix A.
Here is my Python code to solve the full problem:
https://www.codechef.com/viewsolution/18590032
Third Test Case:
I will now give a quick description of how my method solves the third test case.
We start by considering the largest element of the matrix A. That is A_{42}=4. We thus connect nodes 2 and 4 with an edge of weight 4. We then move onto either A_{23}=3 or A_{34}=3. In both cases we will connect node three to either node 2 or 4 with an edge of weight 3. We then have a graph with nodes 2, 3, and 4 in a single connected component. We can thus skip any components of A that do not involve node 1. When we get to A_{13}, A_{14}, or A_{41}, we will then add an edge with weight 2 between node 1 and any other node. At that point our graph is fully connected and we can stop.
The final matrix is given by
and one possible graph is given by
