You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem with Chef and Bipartite Graphs ICPC16F

20
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: http://ideone.com/XJloUh

asked 23 Oct '16, 00:39

nmalviya1929's gravatar image

6★nmalviya1929
16114
accept rate: 0%

edited 23 Oct '16, 00:43

4

Solutions are rejudged...

(23 Oct '16, 16:20) lordshiva19965★

12

I too have same doubt.

CodeLink : http://ideone.com/hCe3oZ

link

answered 23 Oct '16, 01:00

manjunath1996's gravatar image

4★manjunath1996
1287
accept rate: 8%

10

I have the same doubt.

Codelink: http://ideone.com/Gs0sbu

link

answered 23 Oct '16, 01:20

codelover_ug's gravatar image

6★codelover_ug
964
accept rate: 33%

10

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

link

answered 23 Oct '16, 12:47

s4shyam95's gravatar image

5★s4shyam95
2086
accept rate: 20%

2

Solutions have been rejudged

(23 Oct '16, 17:17) s4shyam955★

I have serious doubt in this question.

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

link

answered 23 Oct '16, 01:32

praby's gravatar image

5★praby
511
accept rate: 0%

Yes, I have the same doubt.

Rejudging solutions still doesn't give us the time we would have got "during" the contest.

Not to mention those 10 minutes of "running" for each supposedly wrong submission.

So many faults while hosting such an important contest is simply not justified.

link

answered 23 Oct '16, 16:46

manu4rhyme's gravatar image

5★manu4rhyme
411
accept rate: 0%

True, My team and I made 5 submissions for this questions, and each returned WA after 10 minutes, and upon rejudging, all got Accepted. This not only wasted a lot of time and energy spent on this question, but also prevented us from moving on to the next question.

We understand server capacity couldn't have been estimated, but having weak test cases is just not cool.

(23 Oct '16, 23:52) s4shyam955★

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

link

answered 23 Oct '16, 10:40

praby's gravatar image

5★praby
511
accept rate: 0%

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

link

answered 23 Oct '16, 12:34

mohitbindal644's gravatar image

5★mohitbindal644
213
accept rate: 0%

edited 23 Oct '16, 14:42

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

link

answered 23 Oct '16, 12:42

vinod10's gravatar image

6★vinod10
513
accept rate: 0%

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

link

answered 23 Oct '16, 09:44

praby's gravatar image

5★praby
511
accept rate: 0%

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

link

answered 23 Oct '16, 09:45

ankesh18's gravatar image

6★ankesh18
627111
accept rate: 7%

@ankesh18 It is giving WA instead of TLE.

(23 Oct '16, 11:32) nmalviya19296★

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

link

answered 23 Oct '16, 10:31

stillhungry's gravatar image

4★stillhungry
0
accept rate: 0%

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

link

answered 23 Oct '16, 11:43

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

4

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

(23 Oct '16, 11:53) nmalviya19296★

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

(23 Oct '16, 14:23) agrocks232★

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.

link

answered 23 Oct '16, 13:17

saisumit's gravatar image

5★saisumit
112
accept rate: 0%

2

They have just made a joke of acm-icpc. 5 adhoc questions , 20 mins long queue, login suspension , unverified data of "F" question. Its one of the worst contest i have ever given :( and the excuse they are giving is that it happened with everyone else. Cant find anything wrong with this solution http://ideone.com/QMnxGN

(23 Oct '16, 18:22) saisumit5★

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

link

answered 23 Oct '16, 14:04

piyush9620's gravatar image

4★piyush9620
1
accept rate: 0%

edited 23 Oct '16, 14:05

2

Approach used here is greedy and degree of n nodes is increased one by one. To increase degree of all nodes by one, we need n edges. And condition m<=((2nD)/2) is already checked.

(23 Oct '16, 14:57) vinod106★

@nmalviya Try this case 100 10000 1 10

UPD-Sorry Wrong Case..

link

answered 23 Oct '16, 14:34

tumblehead's gravatar image

2★tumblehead
11
accept rate: 0%

edited 23 Oct '16, 18:09

2

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

(23 Oct '16, 14:45) agrocks232★
2

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

(23 Oct '16, 14:54) vinod106★

guys,most of you have made same mistake.you all are printing edges and then checking the condition. @nmalviya Try this: 1 0 0 1 your output is 1 1.but no. of edges to be printed is 0. hope this helps.

link

answered 23 Oct '16, 15:11

adityacoder's gravatar image

4★adityacoder
1
accept rate: 0%

There is a constraint mentioning d>=1

(23 Oct '16, 15:17) s4shyam955★

Did u guys handle the case when m=0 and n=0?? Even I couldn't figure it out until the contest finished. :(

link

answered 23 Oct '16, 18:38

jainy6's gravatar image

2★jainy6
11
accept rate: 0%

edited 23 Oct '16, 18:39

@jainy6 According to the constraints given in the question n >= 1

link

answered 23 Oct '16, 18:50

mohitbindal644's gravatar image

5★mohitbindal644
213
accept rate: 0%

link

answered 23 Oct '16, 21:34

deepansh_946's gravatar image

2★deepansh_946
466
accept rate: 0%

Oh ya @mohitbindal644. Didn't see that... And I'm again badly curious for the reason y I got WA.

link

answered 23 Oct '16, 21:35

jainy6's gravatar image

2★jainy6
11
accept rate: 0%

I just don't know what people at Codechef office are happy about. Reference: https://www.facebook.com/CodeChef/photos/a.10150302285647799.346300.53227312798/10154057722962799/?type=3&theater

There servers weren't ready to take the load of the high submission rate but still they went for the Common Online Test. My team was logged out 9-10 times due to session limit and the submission's were in Queue for more than 20 minutes. It's just frustating.

link

answered 24 Oct '16, 08:44

dusht0814's gravatar image

4★dusht0814
1945
accept rate: 14%

edited 24 Oct '16, 08:46

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,101

question asked: 23 Oct '16, 00:39

question was seen: 4,615 times

last updated: 24 Oct '16, 08:46