Problem with Chef and Bipartite Graphs ICPC16F

general
1

I’m getting wrong answer for the problem Chef and Bipartite graphs ICPC16F. Can anybody provide input for which it will fail ?

Thanks in advance.

Question Link:
https://www.codechef.com/ACMIND16/problems/ICPC16F

Code Link:

10 Likes
2

I too have same doubt.

CodeLink : http://ideone.com/hCe3oZ

6 Likes
3

I have the same doubt.

Codelink: http://ideone.com/Gs0sbu

5 Likes
4

I have serious doubt in this question.

Codelink: http://ideone.com/5lsRY7

4 Likes
5

It gives correct output for all the above codes. Please run the codes and verify.

6

@nmalviya1929 I couldn’t figure out a failing test case but your code will definitely give a TLE for large subtasks (n=100,m=10000) as it uses slow I/O operations.

7

Why are they not opening question for practice???.If anyone knows where they are,Please tell me the link…

8

@ankesh18 The time limit for the problem was 2 seconds and using 10^6 I/O operations will never give TLE verdict. Further I was getting WA Verdict not TLE.

1 Like
9

@ankesh18 It is giving WA instead of TLE.

10

@codelover_ug Your code is giving wrong answer for “1 2 1 3”.Your code gives output as -1 but that should not be instead there exists a valid bipartite matching for that case…

11

@naksh9619
d and D should be less than equal to n to make a valid bipartite graph.
1 2 1 3 is not valid input.

2 Likes
12

I have the same problem with my code.

Can anyone please help, why my code is giving WA.

Code link : http://ideone.com/Tf3P1A

Can it be the case that the checker function of codechef for this question is incorrect?? @admin

1 Like
13

@ankesh18 Both the loop runs till cnt!=m, so total number of operation will be m and hence it will not give TLE. Time complexity of @nmalviya1929 's code is O(T*m).

1 Like
14

I got a WA too, and I cannot figure out a case where it would fail,

Can we have this problem rejudged once cases are corrected ? @admin

5 Likes
15

it took 20 mins for knowing whether our solution for this problem was right or wrong , submitted at 9:30 and got to know the “wrong” verdict at 9:50 with 10 mins left, didn’t expect such carelessness from codechef for this contest.

16

your solution is wrong. u also have to take care not to assign degree more than D. i see that u haven’t taken care of that. @nmalviya

17

further m<=n*n condition is also not satisfied in your case.

18

@nmalviya Try this case 100 10000 1 10

UPD-Sorry Wrong Case…

19

answer -1 is coming from his code and that’s the correct answer

1 Like
20

@tumblehead When n=100 and m=10000,every node of bipartite graph has degree 100, which doesn’t satisfy the condition d<=deg(v)<=D (d=1 & D=10). And @nmalviya1929 's code is giving -1 answer for that, which is correct.

1 Like