Editorials for ANCOIMP please !!

explanation for the solution is required. Can anyone help ??

2 Likes

Hint : Graph (edge from i to j when Aij = 1) , DP on Connected Components

4 Likes

Here is my idea…
The new matrix X must have as many 1’s as possible along with those positions in which A has 1.
I thought of this as a 2 coloring problem with the two colors being numbered ‘1’ or ‘0’.
For checking whether a solution exists or not , just do a simple bipartite checking with the given A matrix as the adjacency matrix. If possible, answer is YES (and we need to find an optimal coloring) else NO .
If YES, as I told we need to find an optimal coloring . By Optimal Coloring I mean that there will be maximum number of edges in the graph . (becoz maximum number of edges -> maximum 1’s in the adjacency matrix).
And this can be achieved if the vertices are evenly distributed between the partites…This is becoz there can be many components in the graph corresponding to the matrix and so an optimal partitioning is required .
SO for each component keep track of the number of vertices in the two partites and combine(or merge) them in such a way that vertices are equally distributed between the partites . I have just provided an overall idea !!!

1 Like

Graph + greedy (used wittily) will also work. :stuck_out_tongue:

1 Like

Here’s a detailed write-up of my solution, which follows the solution sketch mentioned by @sudharsansai. Solution code here: http://www.codechef.com/viewsolution/7107968

In any case where Aij == 0, then Aij -> Xij will always be 1, regardless of choice of X. Thus the choice of Xij is free when Aij is 0.

For Aij == 1, then Aij -> Xij will be 1 iff Xij == 1. Thus Xij is constrained exactly when Aij is 1.

We are not looking for Xij, but yi and yj. We can rewrite our contraints above in terms of y:

  1. If Aij == 1, then yi ^ yj == 1 (using the shorthand for XOR). In other words yi != yj.
  2. If Aij == 0, then there is no constraint between yi and yj. To maximize 0s in X -> A, we want Xij == 1 in as many of these cases as possible. Thus we prefer yi != yj in unconstrained pairings.

We can represent these “!=” constraints as a 2-coloring problem on a graph with N nodes for each yi where each “!=” corresponds to an edge. We can construct this graph and try to color it. For each connected component, if we choose an initial color (let’s say black or white) for one of the nodes, the coloring for all of the others nodes can be determined greedily in linear time. It’s possible that here we find a coloring conflict due to the graph topology, in which case we return “-1”.

For every connected component, if it is possible to color, we have two choices of coloring, one for an initial choice of white and one for an initial choice of black. To choose the best colorings across connected components, we want to minimize the difference across the whole graph of the black and white node colorings. To do so, we can use a dynamic programming solution: we list out the pairs of counts of black/white colorings for each connected component, then we find an optimal choice of coloring for every pair.

The dynamic programming function can be written as bool f(prefix, sum) = whether we can make choices for the first prefix connected components to equal sum black (or alternatively white) colored nodes. If there are C connected components, we can build the C x N dp boolean array and build it up incrementing one prefix at a time. For each cell (c,n) we do this by looking at the cell entries from (c-1, n-) and (c-1, n-), if either are true, then this cell is true. As we do this, we also augment with an array of the choices of black/white for each of these cells that are true.

Once we fill this dp array, we find the true cell with prefix == N with sum closest to N/2. From this cell, we can backtrack all of the choices from the augmentation array and store in the output array the choice of color, component by component. Finally, we output this final colored y array (it doesn’t matter whether white or black corresponds to 1 in the final y array, but a consistent choice must be made).

4 Likes

This is what i was searching for thank you so much !!!

thank you !!

Here is what I did ->

First of all, wherever you have 1 in A, you must have 1 in X as well because A->X is 1. So if the positions i,j have 1 in A then Yi xor Yj must be 1 or in other words Yi and Yj need to be complements of each other.

Now we want to maximize the 0s in X->A. In order to maximize the number of 0s in X->A, we need to maximize the number of 1s in X because X->A = !X || (X && A).

To maximize the number of 1s in X, we need to minimize the difference D where
D = abs (Y0 - Y1)
where Y0 = number of 0s in Y and Y1 = number of 1s in Y.

You can use various techniques to achieve this - I used sum of subsets.
Here is a brief idea of how Sum of subsets approach works : -

So connect all the positions which are dependent on each other together, thereby forming components. In a component if a vertex v1 is connected to v2 by an edge then v1 and v2 should have complimentary values.

Assign each component a value V which is the maximum difference that can be provided by this component. For example if we have a component 1-2-3 then here V = 1 because the nodes 1 and 3 will be given same values while 2 will be given a complementary value. So the difference is number of nodes having one type of value - number of nodes having complementary value = 1.
Now let total_sum = sum of all Vs of such components.

Once this is done, just find the subset which can give sum closest to (total_sum/2) and that will be the best way to split the components in order to achieve closest number of 1s and 0s.

EDIT : Seems like @Looterguf has explained a similar soln. Should ve read before typing :stuck_out_tongue:

2 Likes

A one-line summary of this problem would be:

Given the adjacency matrix of an undirected graph, determine the maximum number of edges you can add to turn it into a complete bipartite graph (iff it is possible) and output the neighbor list of vertex 0.

So DFS to ensure none of the connected components have odd cycles, and then performing a knapsack DP to build up the largest possible complete bipartite graph suffices.

2 Likes

“In any case where Aij == 0, then Aij -> Xij will always be 1, and Xij -> Aij will always be 1”. I m getting the first part right, but I am not getting the second part from my truth table. Is that maybe a typo or my truth table is wrong? Here is what I am getting: when p=0, p->q=1 for both values of q, when p=0, p->q=value of q.

@eisenhover, you’re right, I mistyped. I meant to say only Aij -> Xij will always be 1 (which satisfies the hard constraint). We want Xij -> Aij to be 0 in as many locations as possible, so this is the pairing we are optimizing over as we choose colorings.