KMHAMHA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Vertex cover, König’s theorem, Hopcroft–Karp algorithm

PROBLEM:

Given a set of points S in a rectangular grid, find the size of the smallest set T containing rows and columns such that for each point in S either its row or column is in the selected set T.

QUICK EXPLANATION:

The problem can be reduced to finding the size of the optimum vertex cover in a bipartite graph, which can then be computed using Hopcroft-Karp algorithm.

EXPLANATION:

We are given a set of points S, where the demons stand in the beginning. In a single attack Goku can kill all demons in a single row or in a single column.

Since Goku wants to kill all demons, for each demon he must call an attack either on its row or on its column. Hence, the problem is equivalent to find a set T of smallest size containing rows and columns, such that for each demon standing on the point (Rx, Cy) either Rx is in the set T, or Cy is in the set T.

Reduction into vertex cover:

The problem can be easily reduced to finding the optimum vertex cover in a bipartite graph. Let us create a bipartite graph G = (R, C, E), where the vertices on the left side R correspond to rows of the grid, and the vertices on the right side C correspond to the columns of the grid. For each demon standing at point (Rx, Cy) create an edge between the vertex Rx and Cy.

For example, if we have 4 demons standing at (1, 8), (5, 6), (3, 8), (5, 4), we will end with the following bipartite graph:

R = {1, 3, 5}
C = {4, 6, 8}
E = {(1, 8), (5, 6), (3, 8), (5, 4)}

Here each demon is represented by an edge, and in order to kill that demon Goku must pick at least one of its two incident vertices, and call an attack on the picked row (or column), e.g., in order to kill the demon standing at (5, 6) he must attack either Row 5, or Column 6.

In other words, we want to find a set T of smallest size of vertices in the created bipartite graph such that for each edge, one of its incident vertices is in T. Such a set is called vertex cover of the graph.

Finding the Vertex cover:

Finding the optimum vertex cover in a general graph is an NP-hard problem. However, for a bipartite graph the problem can be solved in polynomial time thanks to König’s theorem which states that the size of the vertex cover in a bipartite graph is the same as the size of the maximum matching.

Finding the maximum matching in a bipartite graph is a well known problem, and can be solved in O (E√N) time using Hopcroft–Karp algorithm, where N is the number of vertices and E is the number of edges.

In our problem the number of edges is the same as the number of demons (N). The number of vertices can be at most 2N (N rows and N columns), as each edge will create at most two new vertices.

Use of hash map to create the graph:

In the problem each of the Rx and Cy can be as large as 109. However, there are at most N such values. Hence, one can assign a unique id in [1, N] to each Rx and Cy. A hash map can be used to ensure that the same values of Rx (and Cy) are assigned the same id.

Time Complexity:

O (N1.5)

Weak test cases:

Unfortunately, the test cases for this problem were weak, and allowed greedy solutions to pass. This was pointed out by many participants during the contest. We added new test cases to avoid the false positives, but still there were many solutions which are using greedy and randomized algorithm and are being accepted.

Here is one test case which helped us removing many false positives
1
15
0 0
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 0
3 7
3 8
4 9
5 9
6 9

The correct answer is 5, however many accepted solutions were providing 6 as answer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution can be found here.

28 Likes

can’t it be solved by dp?

7 Likes

code for visualizing points on the graphs
alt text

10 Likes

hello please look into my solution and tell me at which case is my solution failing.
My solution CodeChef: Practical coding for everyone
It is getting right answer for the given case but still its failing somewhere.

2 Likes

my code is giving 5 for the give test case and i verified it for many test cases it gave correct answer, still my code was not AC during the contest
http://www.codechef.com/viewsolution/2820678
if anyone can point out the problem, that would be great

Thanks

How would it be solved if the number of demons are around 10^8 or 10^9 ??

I am not able to get the Routine by tester can someone provide me a good source to get this concept ,please!

inline bool augment(int x)
    {
        for (int i = 0; i < adj[x].size(); ++ i) {
            int y = adj[x][i];
            if (mark[y] == stamp) {
                continue;
            }
            mark[y] = stamp;
            if (match[y] == -1 || augment(match[y])) {
                match[y] = x;
                return true;
            }
        }
        return false;
    }

hi admin,
my code is working fine for all above mentioned testcases can you give me any testcase for which it is failing.
http://www.codechef.com/viewsolution/2821524

I did not know about any of the algorithms mentioned in the prerequisites but was able to arrive at a pretty simple logical solution. Thought I’d share it.

For killing any demon either its row has to be destroyed or its column. Now if a demon is alone in its row ie. there is only one demon in that row, then destroying that row would be useless as one attack will kill only one demon. So in that case the column will be destroyed for that particular demon. It does not matter how many demons are there in that column because this attack will kill one or more demons instead of only one if we used the attack on the row. Similarly for a column having only one demon, the optimal way will be to destroy the corresponding row for that demon instead of the column.
So the basic form of the program will be :

  • keep a count of demons for all rows and columns.
  • do this until every row has more than one demon : if a row has a single demon(say ith row and jth column) then all the demons in the jth column will be destroyed. Count for that column will become 0 and update the count for all the rows. The answer will be incremented by 1.
  • repeat step 2 for the columns so that all columns have more than one demon now.
  • Now every column and every row has more than one demon. All we need to do now is find the minimum of ( no. of rows with atleast one demon , no.of columns with atleast one demon) and add this to the answer calculated before.

Implementation was a little tricky but fortunately got AC on first try. Here is the solution
http://www.codechef.com/viewsolution/2795618

6 Likes

Sir,There is no link for editorials in Contest page.please post it :slight_smile:

1 Like

Even I didn’t know any particular algorithm for this problem and tried an approach of mine own and would like to share it with you guys.

Since we are asked to minimize the maximum number of attacks.initially I was maintaining a count of total number of cells containing demons.suppose the value is N.
Now while N > 0, I was repeatedly doing the following

  • find the count of the distinct rows and columns containing demons and determing the minimum value,Determining the minimum count(row or column) is useful because thats the maximum possible number of attacks.
    Now there might be three cases 1)Count of unique rows is minimum 2)Count of unique column is minimum 3)both are equal

  • Let us consider that count of unique row is minimum.So,Now I search if any column exist such that if I remove that column then more than 1 such unique rows are removed(i.e some rows might exist which only contains a single demon in the same column).Now this will further decrease the minimum count of unique rows.
    However if no such column exist then i search if such a row exist whose removal also removes more than one column.This will decrease the minimum count of unique columns.
    However if still no such rows exist then I only remove the row containing maximum number of demons.

  • The same approach is followed if column count is minimum.

  • However if both unique column and unique row count are same then first search for columns whose removal removes more than one row or any row whose removal removes more than one column**(whichever removes the higher number of rows/columns is selected)**.or Else find the row/column with maximum number of demons and delete it…

This is a greedy approach which worked for me after I got WA after first resubmissions.

I applied a solution similar to @sikander_nsit but this one actually goes through all possible configurations. For each row there are only two possible ways to kill all demons: either all the columns of that row are covered or the all row is covered. Using recursion, for each row first cover all remaining columns and proceed to the next row and store the value, after that try to cover the all row and proceed to the next row and store the value. Return the minimum of those two values. And like @sikander_nsit said if a demon is alone in its row cover its column. If any of the demons in the current row is last in its columns then cover the all row.

if the x-coordinate and y coordinate of a point is same how can it be a bipartite

http://www.codechef.com/viewsolution/2847127
plz tell me where my code fails.

I cannot find a single test case where my solution fails! take a look at it: http://www.codechef.com/viewsolution/2813956
I know my approach is not the best one, but still can any one give me a test case where my solution fails! I have tried all the test cases - those given in the comments above, those given in problem’s comment section, the one in the editorial, and many more of my own! My code works for all of them!
Please Please ! It’s becoming increasingly difficult for me to sleep peacefully without knowing what’s wrong in this code!

How do i start learning Hopcroft - Karp algorithm ? Should i know max flow - min cut problem prior to it ? I am new to this topic. Somebody please help…

I think time complexity is O(N2.5) as:
O(E) = O(N2)
O(V0.5) = O(N0.5)

1 Like

Hi Ajay, Can you please give the test case failed by my code CodeChef: Practical coding for everyone . It passes the above test case.

Here is a case where ur code goes wrong: http://pastie.org/8401415

Answer should be 3

ur ouput is 4

1 Like

http://www.codechef.com/viewsolution/2823452

it would be nice if anyone could give me a test case where my code fails. It’s giving correct results for above test case and all the others in comment section of the problem