NODDC testcase clarification

cycle
dfs
graph
iscc2017
odd

#1

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 ?


#2

The test cases are not weak, infact it’s very weak. All the cases have 0 answer. See this
solution .


#3

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?


#4

Does anyone have an elegant solution that can be proved to be correct?


#5

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.


#6

yupp…exactly :frowning:


#7

This is ridiculous!


#8

the question was a bit unclear for me. Can you just tell me, how the cycle is defined in 2nd sample case ??


#9

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.


#10

For what cases will the answer be zero, except for M=0?


#11

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.


#12

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?


#13

Wow, now that I think about it, this N^2 = 4 imes 10^8 brute force actually does fit within bounds.


#14

Thanks a lot bro!! :slight_smile:


#15

Oh wow, I used the same approach but with DFS and got TLE.


#16

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 :confused:


#17

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.


#18

completely agree with @de_vika