KINGCON - Editorial

@anton_lunyov >> thanks for related problems, really. I used to get nightmares not practicing much in Graph Algorithms, but now I will work harder.

Such solution has complexity O(N * M). In this problem N could be up to 3000 and M could be up to 4500000. So N * M is very large number. It depends on test data whether such solution could be fit into TL using some tricks.

2 Likes

@bugkiller I tried the same, but it was only “are test cases weak?” test…

1 Like

@betlista >> Because before went to depth I wanted to first try out from things that I already know but … :frowning: rather I am thankful that I learned new things.

@admin: Can you please tell me which test case gave WA for my submission (below). I am sure i missed some case.

http://www.codechef.com/viewsolution/2040555

If I did it correctly, than here it returns 2 and expected result is 1

@betlista: Thanks a lot. Figured out my mistake. :slight_smile:

In java, you cant really say anything. The TL is set basically using C/C++ because tester and setter both use these most of the times. You did well, congratulations and all the best for future contests.

or maybe in the test cases, there were few complete graphs with huge number of nodes, and those cases were eating up the time.

Is this problem the same as the “minimum vertex cover” problem?

exactly same here.
Thats the essence of CodeChef long challenge.
It gives you time to explore new concepts and implement them.
I started with checking the graph by removing each node and marking the critical nodes and as expected was getting TLE.
Articulation points : got to learn a new application of DFS.
Kudos to the problem setter and CodeChef team.

@tyrant No. Serf Wikipedia.

Your solution is completely wrong and seems to produce wrong output for almost all official test cases.
The simplest test where it fails is:
2 1 1
0 1
You return 1 while the correct answer is 0.

@anton_lunyov How to check whether root is an articulation point or not?

Pls help Why my code is giving WA
https://www.codechef.com/viewsolution/34476945

I have used the articulation point concept with low but still getting TLE can any one suggest me my mistake. Here is my submission link -
https://www.codechef.com/viewsolution/38505329