KMHAMHA - Editorial

editorial
, , , , ,
21

hashing is the only solution i guess.you need to map the higher values to lower values as the input of demons is maximum 1000.

22

Yash I ran your code for test case given in editorial it outputs 6.

1 Like
23

@anu1234 The notion of augmenting path is explained here Matching (graph theory) - Wikipedia

24

hey vikrant1433. plz suggest a testcase for my solution. Its giving correct answer CodeChef: Practical coding for everyone. I dont know what is wrong.

25

@tibip i am getting augmenting path an alternating path having start and end point free. But i am not getting it’s implementation ,I need explanation.At wikipedia it is quit confusing to me get the implementation .Please help me!

26

i got !! thanx :slight_smile:

27

CodeChef: Practical coding for everyone please tell me where my solution goes wrong.

28

hi admin, my code is working fine for all above mentioned testcases can you give me any testcase for which it is failing. CodeChef: Practical coding for everyone

29

This is what you would call as a Greedy Solution.

1 Like
30

You’re lucky to have got an AC. The official test cases were too weak to defeat your greedy algorithm.

2 Likes
31

This is a greedy approach and I would really like to know any test case that it would fail?? I tried all the test cases till now even for the one given in the editorial its giving 5…

CodeChef: Practical coding for everyone Here is the link of my solution…

32

SAme logic i have applied but still it gives WA. Actually my answer code is giving correct answers for all of the cases given.
kevinsogo- The question was open for these kind of solutions because time limit was 2sec and n<=1000. So a solution with complexity O(n^2) will easily pass.

33

@abhisht7 The problem is not speed, but correctness. No doubt this solution will pass the time limit, but it may not be correct in certain test cases. It’s hard to come up with a really strong test case, though.

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.