PROBLEM LINK:Author: Kaushik Iska DIFFICULTY:EASYMEDIUM 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 HopcroftKarp 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} 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 NPhard 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 10^{9}. 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 (N^{1.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 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.
This question is marked "community wiki".
asked 14 Oct '13, 16:18
showing 5 of 7
show all

answered 14 Oct '13, 16:50

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 :
Implementation was a little tricky but fortunately got AC on first try. Here is the solution http://www.codechef.com/viewsolution/2795618 answered 15 Oct '13, 06:03
1
This is what you would call as a Greedy Solution.
(15 Oct '13, 08:42)
2
You're lucky to have got an AC. The official test cases were too weak to defeat your greedy algorithm.
(15 Oct '13, 11:39)
SAme logic i have applied but still it gives WA. Actually my answer code is giving correct answers for all of the cases given. kevinsogo The question was open for these kind of solutions because time limit was 2sec and n<=1000. So a solution with complexity O(n^2) will easily pass.
(15 Oct '13, 15:06)
@abhisht7 The problem is not speed, but correctness. No doubt this solution will pass the time limit, but it may not be correct in certain test cases. It's hard to come up with a really strong test case, though.
(15 Oct '13, 16:12)
This algorithm may be greedy but not in the sense that there are some missing test cases on which this will give wrong answer. It will show correct ans for any possible test case within the given limits.
(15 Oct '13, 16:19)
9
@sikander_nsit Here's a case where your answer fails:
The answer is 4, but your code gives 5.
(15 Oct '13, 16:36)
http://www.codechef.com/viewsolution/2828457 @kevinsogo take a look at this solution it has passed the given test case but gives WA.
(15 Oct '13, 17:44)
2
(15 Oct '13, 21:08)
@kevinsogo can you provide me the test case where this code fails. http://www.codechef.com/viewsolution/2827617
(15 Oct '13, 21:56)
@kevinsogo Thanks man. I got it.
(15 Oct '13, 22:20)
@kevinsogo thanks.
(15 Oct '13, 22:21)
@kevinsogo Thanks for the failing case.
(15 Oct '13, 23:26)
@Kevinsogo, Can u please give a case where this solution fails http://www.codechef.com/viewsolution/2826193
(18 Oct '13, 17:13)
showing 5 of 14
show all

hello please look into my solution and tell me at which case is my solution failing. My solution http://www.codechef.com/viewsolution/2828457 It is getting right answer for the given case but still its failing somewhere. answered 14 Oct '13, 18:31

Sir,There is no link for editorials in Contest page.please post it :) answered 15 Oct '13, 08:41

I think time complexity is O(N^{2.5}) as: answered 05 Jan '14, 12:52
1
Sorry, misunderstood the problem statement (input format). I thought you are given NxN matrix. :)
(05 Jan '14, 13:15)
@sylap nahilow sylap aga, gowumy yagdaylar :)
(06 Jan '14, 04:59)
@garakchy shukur gowy siz nahili? :D
(20 Jun '15, 15:27)

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 answered 14 Oct '13, 19:11
1
(14 Oct '13, 19:47)
1
Yash I ran your code for test case given in editorial it outputs 6.
(14 Oct '13, 21:43)
hey vikrant1433. plz suggest a testcase for my solution. Its giving correct answer http://www.codechef.com/viewsolution/2828457. I dont know what is wrong.
(14 Oct '13, 22:10)
thank you Ahmed and Vikrant for pointing that out...now i know what my method missed... i am still very new to coding and unaware of many of the algorithm that are used and explained in editorials i just guessed the method and implemented it..maybe my approach is what they are calling "GREEDY" algorithm and that's why it failed... Thanks again
(15 Oct '13, 23:52)

I am not able to get the Routine by tester can someone provide me a good source to get this concept ,please!
answered 14 Oct '13, 21:36
@anu1234 The notion of augmenting path is explained here http://en.wikipedia.org/wiki/Matching_(graph_theory)
(14 Oct '13, 22:07)
@tibip i am getting augmenting path an alternating path having start and end point free. But i am not getting it's implementation ,I need explanation.At wikipedia it is quit confusing to me get the implementation .Please help me!
(14 Oct '13, 22:22)
i got !! thanx :)
(14 Oct '13, 23:00)

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 answered 14 Oct '13, 23:59

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
This is a greedy approach which worked for me after I got WA after first resubmissions. answered 15 Oct '13, 14:17
This is a greedy approach and I would really like to know any test case that it would fail?? I tried all the test cases till now even for the one given in the editorial its giving 5.. http://www.codechef.com/viewsolution/2802744 Here is the link of my solution..
(15 Oct '13, 14:22)
Here's a test case I posted in one of the other kmhamha threads
The answer should be 9. It looks like this:
(19 Oct '13, 07:23)
@kevinsogo do you have a file of test cases or could you generate a file of some challenging test cases? It will be really helpful as a lot of people are having doubts in this question
(19 Oct '13, 11:46)
@kcahdog I compiled all the test cases so far into this link, plus a few programs that generate test cases. You might want to look at it (suggestions welcome).
(21 Oct '13, 01:57)
@kevinsogo Thanks a lot. Could you post it as a separate post from this as it will be better for people to access.Also could you post some short notes on how to generate such test cases for future reference?.I already found the test case for which my code failed but it will be better for others who want to debug theirs.
(21 Oct '13, 02:18)
showing 5 of 6
show all

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. answered 15 Oct '13, 16:30

if the xcoordinate and y coordinate of a point is same how can it be a bipartite answered 17 Oct '13, 22:47

http://www.codechef.com/viewsolution/2847127 plz tell me where my code fails. answered 18 Oct '13, 21:23

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! answered 19 Oct '13, 00:19

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..... answered 09 Nov '13, 09:23

Hi Ajay, Can you please give the test case failed by my code http://www.codechef.com/viewsolution/2826193 . It passes the above test case.
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
http://www.codechef.com/viewsolution/2828457 please tell me where my solution goes wrong.
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
hi admin ,plz tell me where my code fails. http://www.codechef.com/viewsolution/2847127
int newid = hashX.size(); adj[newid].clear();
I am not getting the above part in the tester solution. Why we need to clear the adj[newid]? Plz. someone explain it..
Nice editorial.