Kamehameha-Greedy approach

general
1

Could somebody tell me where does my solution go wrong?
Working for all the test cases in the editorial.

What I had done was to remove that column of demons which removes the maximum number of rows and vice versa
and if I’m not able to find such a row or column I remove that row or column which has the maximum number of demons.

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

Also could somebody give me the test case where my second approach fails:

1)Find the minimum(current number of rows,current number of columns).Let it be x

2)Find the row/column with maximum number of demons and remove that.(break ties arbitrarily)

Let the answer using 2) be y.

The final answer is min(x,y)

2

I employed an approach similar to the first one and it failed for the test case given in the editorial. Have you tried that one? You can also try the test cases given by @kevinsogo in the comments under the editorial. Most probably you will find some fault in these cases.

3

1 1 0 0

1 0 1 0

1 0 0 1

Answer for this is 3.
But if you apply the above greedy approach it gives 4.

4

Here’s a sample test case where your given greedy approach fails:

12
5 1
6 1
7 1
1 5
1 6
1 7
7 2
6 3
5 4
4 5
3 6
2 7

It looks like this:

XX.....
X.X....
X..X...
....X..
.....X.
......X
....XXX

Answer should be 6, but your approach gives 7.

Here’s another one:

XXX......
X.XX.....
X..XX....
X...XX...
.....XX..
......XX.
.......XX
........X
.....XXXX

Answer should be 8, but your approach gives 9.

Finally, if you want, we take it to the next level:

37
785 785
785 415
785 2
785 773
415 785
415 2
415 773
415 815
2 785
2 773
2 815
2 998
773 785
773 815
773 998
773 252
815 785
815 998
815 252
815 653
998 252
998 653
998 539
252 653
252 539
252 880
653 539
653 880
653 654
539 880
539 654
880 654
654 252
654 653
654 539
654 880
654 654

When rearranged, it looks like this:

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

The answer should be 10, but your approach gives 11. Even your original code gives 11 !

5 Likes
5

Can anyone please tell if my greedy solution is failing for any test case. I am finding out the row or the column having minimum number of demon and then i am removing the corresponding row or columns of the minimum row or column. My solution is CodeChef: Practical coding for everyone.

6

@admin I feel that all those AC solutions which were done using greedy should be re-evaluated to WA as a greedy approach is bound to fail on some method or the other as shown by @kevinsogo on this thread and on many other Kamehameha threads.

7

best way to check is take a already made solution using “bi-partite matching” from solution and
compare result from greedy algorithm using randomly generated test cases. write a simple code for that
, if after millions tests u get same ans for both then try and mathematically prove the algorithm u designed to be optimal(or not optimal).

8

Nope it isn’t failing I tested for all cases by @kevinsogo

9

Could you explain how it is 2? even i think it is 3

10

I’m not sure about your implementation but your code seems to fail in this case:

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

Answer should be 3.

1 Like
11

Thanks for the test case.Could u tell me whats wrong with the 2nd approach?

Any test case for the 2nd method?

12

I made an answer below.

13

Its giving 6.

14

Why? There are 7 rows and 7 columns so x=7, while using 2) gives y=8. Your answer is min(7,8) = 7.

15

@jaskaran_1 hilarious! How you came up with this :stuck_out_tongue:

16

@kevinsogo Is every greedy approach bound to fail???
I got AC using following greedy approach-
1.Choose a row/column to attack which eliminates maximum number of columns/rows.
2.If no column or row is eliminated (by a row/column attack respectively),then find whether number of remaining columns are less or remaining rows and choose from it the row(if rows are less) or column(if columns are less) which has the maximum demons.
3.Repeat until all rows and columns are eliminated.
Code: CodeChef: Practical coding for everyone
I checked for all mentioned cases and it gives the right answer.

17

@kevinsogo the second approach fails.Your test cases are working for my code in the link.Lets say u find another test case on which my code doesn’t work.So does this mean that this can’t be solved greedily at all.

18

My answer is 3.

19

@amntri You can think of it another way.

If you read the editorial, you’ll know that KMHAMHA can be reduced to an instance of the “maximum bipartite matching” problem. But you can also reduce an instance of the maximum bipartite matching problem into an instance of KMHAMHA!

In other words, if you solve this problem with a greedy approach, then you are also able to solve the maximum bipartite matching problem with a totally new approach. If you’re able to prove that it indeed works for all cases, then in my opinion this is a totally new algorithm that is worth publishing as a research paper.

5 Likes
20

@jaskaran_1 you should have mentioned that you changed the link in the question (e.g. “edited”) so I know that you updated it. Here’s your original link: CodeChef: Practical coding for everyone . I have a copy of your previous code and it fails for the large case.

Of course I can try to find a new test case where your new program fails, but see my comment above for a reason why greedy approaches are (almost) guaranteed to fail.

1 Like