×

NODDC testcase clarification

 4 Please refer to this question. What would be your answer for N=5 M=6 1 2 2 3 3 4 4 5 5 1 1 4 My answer is 2. But according to this submission that passed all test cases, the answer is 0. Am I going wrong somewhere ? Or are the test cases weak ? asked 27 Jul '17, 18:36 2★de_vika 43●3 accept rate: 0%

 6 The test cases are not weak, infact it's very weak. All the cases have 0 answer. See this solution . answered 27 Jul '17, 21:02 304●9 accept rate: 10% 2 This is ridiculous! (27 Jul '17, 22:02) 1 I guess there should be a test for setting test cases ! Because its really disheartening to see this after putting a lot of effort into the question :/ (29 Jul '17, 12:31) de_vika2★ completely agree with @de_vika (29 Jul '17, 21:31)
 4 To answer @liaojh If you use c++ or java (idk about other languages), testing all 2*10^4 edges actually works. Basically just remove every edge and do a bfs to see if the graph will be 2-colorable. Original author: https://www.codechef.com/viewsolution/14667767 which passes in 0.03s My java solution: https://www.codechef.com/viewsolution/14687222 which passes in 0.15s It may not be "elegant", but it is definitely simple. Or most likely, the test cases are weak. answered 28 Jul '17, 05:25 71●3 accept rate: 0% 2 Wow, now that I think about it, this $N^2 = 4 \times 10^8$ brute force actually does fit within bounds. (28 Jul '17, 06:12) liaojh5★ Oh wow, I used the same approach but with DFS and got TLE. (28 Jul '17, 14:26) It may be because dfs requires a lot of function calling, but in the solutions above an array was used as a queue for bfs which could be faster. (29 Jul '17, 12:39)
 2 I wont call it weak, i will call that broken to be honest. In sample input, he is removing edges from trees (trees have no cycle in first place), and here the answer of ALL the test cases is 0? WTF? answered 27 Jul '17, 21:24 15.5k●1●20●66 accept rate: 18% yupp...exactly :( (27 Jul '17, 21:53)
 2 Does anyone have an elegant solution that can be proved to be correct? answered 27 Jul '17, 23:28 5★liaojh 182●5 accept rate: 7% the question was a bit unclear for me. Can you just tell me, how the cycle is defined in 2nd sample case ?? (28 Jul '17, 00:48) There is no odd cycle in the second case, and removing any edge will not give you an odd cycle, thus, you can remove all edges. This just tells us in a case where no odd cycle exists, all edges are removable. (28 Jul '17, 01:12) liaojh5★ For what cases will the answer be zero, except for M=0? (28 Jul '17, 02:24) 2 Here's what I got: If there exists a segment such that it connects with all odd cycles and such that removing this segment will result in all cycles become even, then the answer will not be zero. For me, the problem reduces down to finding this one segment if it exists, but I'm sure I'm overdoing it. (28 Jul '17, 04:08) liaojh5★ 1 If you want the cases where the answer will be zero: Odd cycles that are not circuited together on one segment (difficult part) Odd cycle circuited with even cycle (simply test with bipartite) The first case can be reduced to searching for the common edges in which all odd cycles have, and those edges are basically the answer to the problem. Searching for common edges feels like an intense algorithm. Is there an elegant solution for it? (28 Jul '17, 04:21) liaojh5★ Thanks a lot bro!! :) (28 Jul '17, 12:17) showing 5 of 6 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,236
×733
×46
×19
×13

question asked: 27 Jul '17, 18:36

question was seen: 723 times

last updated: 29 Jul '17, 12:39