You are not logged in. Please login at www.codechef.com to post your questions!

×

KMHAMHA - Editorial

28
12

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.

This question is marked "community wiki".

asked 14 Oct '13, 16:18

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 17 Oct '13, 12:13

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138

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.

(14 Oct '13, 17:25) ajit_a2★

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

(14 Oct '13, 21:34) sahil1401943★

http://www.codechef.com/viewsolution/2828457 please tell me where my solution goes wrong.

(14 Oct '13, 23:30) abhisht73★

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

(15 Oct '13, 00:00) jnash_073★

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

(18 Oct '13, 21:25) irshsay3215★

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..

(20 Dec '13, 22:21) sanjeev17793★

Nice editorial.

(21 Dec '13, 16:19) sananth124★
showing 5 of 7 show all

link

answered 14 Oct '13, 16:50

vikrant1433's gravatar image

3★vikrant1433
227369
accept rate: 0%

edited 14 Oct '13, 16:55

can't it be solved by dp?

link

answered 14 Oct '13, 16:49

amitbaranwal53's gravatar image

3★amitbaranwal53
10114
accept rate: 0%

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

link

answered 15 Oct '13, 06:03

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 15 Oct '13, 06:10

1

This is what you would call as a Greedy Solution.

(15 Oct '13, 08:42) bugkiller3★
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) kevinsogo7★

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) abhisht73★

@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) kevinsogo7★

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) sikander_nsit5★
9

@sikander_nsit Here's a case where your answer fails:

16 1 1 1 2 1 3 1 4 1 5 2 1 2 5 3 1 3 5 4 1 4 5 5 1 5 2 5 3 5 4 5 5

The answer is 4, but your code gives 5.

(15 Oct '13, 16:36) kevinsogo7★

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) abhisht73★
2

@abhisht7 Here's one:

7 1 1 1 2 1 3 2 2 2 3 3 1 3 2

The answer is 3 but you gave 4.

(15 Oct '13, 21:08) kevinsogo7★

@kevinsogo can you provide me the test case where this code fails. http://www.codechef.com/viewsolution/2827617

(15 Oct '13, 21:56) sobhagya3★
1

@sobhagya

6 1 3 1 4 2 1 2 2 3 2 4 1

(15 Oct '13, 22:10) kevinsogo7★

@kevinsogo Thanks man. I got it.

(15 Oct '13, 22:20) abhisht73★

@kevinsogo thanks.

(15 Oct '13, 22:21) sobhagya3★

@kevinsogo Thanks for the failing case.

(15 Oct '13, 23:26) sikander_nsit5★

@Kevinsogo, Can u please give a case where this solution fails http://www.codechef.com/viewsolution/2826193

(18 Oct '13, 17:13) ajit_a2★
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.

link

answered 14 Oct '13, 18:31

abhisht7's gravatar image

3★abhisht7
303
accept rate: 0%

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

link

answered 15 Oct '13, 08:41

sainath_b's gravatar image

3★sainath_b
3842613
accept rate: 11%

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

link

answered 05 Jan '14, 12:52

sylap's gravatar image

3★sylap
172
accept rate: 0%

edited 05 Jan '14, 12:54

1

Sorry, misunderstood the problem statement (input format). I thought you are given NxN matrix. :)

(05 Jan '14, 13:15) sylap3★

@sylap nahilow sylap aga, gowumy yagdaylar :)

(06 Jan '14, 04:59) garakchy1★

@garakchy shukur gowy siz nahili? :D

(20 Jun '15, 15:27) sylap3★

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

link

answered 14 Oct '13, 19:11

yashkumar18's gravatar image

5★yashkumar18
82661224
accept rate: 18%

1

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

Answer should be 3

ur ouput is 4

(14 Oct '13, 19:47) ahmed1ossama134★
1

Yash I ran your code for test case given in editorial it outputs 6.

(14 Oct '13, 21:43) vikrant14333★

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) abhisht73★

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) yashkumar185★

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

link

answered 14 Oct '13, 19:20

jaigulraj's gravatar image

3★jaigulraj
1
accept rate: 0%

hashing is the only solution i guess.you need to map the higher values to lower values as the input of demons is maximum 1000.

(14 Oct '13, 21:42) saimadan2★

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;
    }
link

answered 14 Oct '13, 21:36

anu1234's gravatar image

1★anu1234
11431018
accept rate: 0%

@anu1234 The notion of augmenting path is explained here http://en.wikipedia.org/wiki/Matching_(graph_theory)

(14 Oct '13, 22:07) tibip6★

@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) anu12341★

i got !! thanx :)

(14 Oct '13, 23:00) anu12341★

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

link

answered 14 Oct '13, 23:59

jnash_07's gravatar image

3★jnash_07
1
accept rate: 0%

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.

link

answered 15 Oct '13, 14:17

deepai_dutta's gravatar image

2★deepai_dutta
180129
accept rate: 0%

edited 15 Oct '13, 14:19

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) deepai_dutta2★

Here's a test case I posted in one of the other kmhamha threads

33 1 1 2 1 3 1 1 2 2 2 3 2 1 3 2 3 3 3 1 4 2 4 3 4 4 4 5 4 4 5 5 5 4 6 5 6 5 7 6 7 7 7 8 7 6 8 7 8 8 8 8 9 9 9 10 9 11 9 8 10 9 10 10 10 11 10

The answer should be 9. It looks like this:

.......XXXX .......XXXX .....XXX... ....XXXX... ...XX...... ...XX...... XXXXX...... XXX........ XXX........ XXX........

(19 Oct '13, 07:23) kevinsogo7★

@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) kcahdog3★

@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) kevinsogo7★

@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) kcahdog3★

@kcahdog Thanks for the suggestion. I made a separate post here.

(21 Oct '13, 02:56) kevinsogo7★
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.

link

answered 15 Oct '13, 16:30

junior94's gravatar image

4★junior94
3.2k143058
accept rate: 15%

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

link

answered 17 Oct '13, 22:47

monel1994's gravatar image

2★monel1994
1111
accept rate: 0%

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

link

answered 18 Oct '13, 21:23

irshsay321's gravatar image

5★irshsay321
11113
accept rate: 30%

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!

link

answered 19 Oct '13, 00:19

ashish1294's gravatar image

2★ashish1294
19615
accept rate: 7%

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.....

link

answered 09 Nov '13, 09:23

krishnan1159's gravatar image

3★krishnan1159
16122
accept rate: 0%

Yes, you need to study max-flow min-cut algorithms. :)

(05 Jan '14, 12:49) sylap3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,723
×101
×86
×28
×12

question asked: 14 Oct '13, 16:18

question was seen: 9,353 times

last updated: 24 Jun '15, 15:29