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

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

5

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

6

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
7

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 !

4 Likes
8

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

Any test case for the 2nd method?

9

I made an answer below.

10

Its giving 6.

11

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

12

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

13

@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: http://www.codechef.com/viewsolution/2819215
I checked for all mentioned cases and it gives the right answer.

14

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

15

My answer is 3.

16

@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
17

@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: http://www.codechef.com/viewsolution/2803224 . 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
18

@jaskaran_1 you deleted your previous comments and also change the solution link. And, greedy approach never get passed in this problem.

2 Likes
19

@amntri Here’s a test case where your solution fails.

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........
1 Like
20

@kevinsogo Thanks a lot for your time :slight_smile:

1 Like