Can please anyone tell for which test case my AC greedy solution for KAMEHAMEHA might fail. It works on all test cases in editorial as well as those provided in by kevinsogo. In my solution I am first finding the row or column with the minimum number of demons. Suppose a row i contains the minimum number of demons, then I am attacking the columns of those demons which are present in the row i. Same operation is done if column contains the minimum number of demons, in the case of column I am attacking the rows of demons present in the column. Iterate this way until no demon remains. This is how I am calculating the result.
My solution is http://www.codechef.com/viewsolution/2809364
Try this one:
17
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
It looks like this:
XX...
XXXXX
XXXXX
XXXXX
The answer is 4. Another one is:
32
6 1
7 1
8 1
6 2
7 2
8 2
6 3
7 3
8 3
6 4
7 4
8 4
6 5
7 5
8 5
1 5
2 5
3 5
4 5
5 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
1 8
2 8
The answer is 7. It looks like this:
XX......
XXXXX...
XXXXX...
XXXXXXXX
.....XXX
.....XXX
.....XXX
.....XXX
2 Likes
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!
Have you tried the test cases given in the editorial and in the comments given below it ?