http://www.codechef.com/viewsolution/2847127
plz tell me where my code fails.
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!
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........
@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
@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).
@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.
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…
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…
Nice editorial.
Yes, you need to study max-flow min-cut algorithms. 
I think time complexity is O(N2.5) as:
O(E) = O(N2)
O(V0.5) = O(N0.5)
1 Like
Sorry, misunderstood the problem statement (input format). I thought you are given NxN matrix.
1 Like
