KMHAMHA - Editorial

editorial
, , , , ,
34

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.

35

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

9 Likes
36

http://www.codechef.com/viewsolution/2828457
@kevinsogo- take a look at this solution it has passed the given test case but gives WA.

37

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

2 Likes
38

@kevinsogo can you provide me the test case where this code fails. CodeChef: Practical coding for everyone

39

@sobhagya

6
1 3
1 4
2 1
2 2
3 2
4 1
1 Like
40

@kevinsogo Thanks man. I got it.

41

@kevinsogo thanks.

42

@kevinsogo Thanks for the failing case.

43

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

44

@Kevinsogo, Can u please give a case where this solution fails CodeChef: Practical coding for everyone

45

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

46

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

@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

48

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

49

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

50

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

51

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…

52

Nice editorial.

53

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