KINGCON - Editorial

editorial
, , , , ,
13

@milhaus : Thanks for your help but @anunay_arunav is right. Removing those test cases do save a TLE even without using fast I/O.
This is sometimes really dissapointing on part of Codechef that the time limit they set is too much strict, even after getting the algorithm correct, one has to waste time on over-optimizing.The dfs approach was already optimized.

14

@Tester: It is my attempt for this problem - CodeChef: Practical coding for everyone .
can anyone please look at it and tell me why it getting WA (can I know the test cases for which it getting WA)

15

Can anyone please tell me why my submission (below) gives WA.
http://www.codechef.com/viewsolution/4438627

16

This article explains the algorithm for finding articulation points very well. It has got code too.

17

Can anyone have a look at my code ? pastebin
its giving me TLE and i m not able to figure out why.Thanks in advance:)

18

I tried to solve the prob using Articulation Point concept but , am getting TLE.
CodeChef: Practical coding for everyone :->Here is my solution.
Please debug my code

19

https://www.codechef.com/viewsolution/22661232

Trick to solve this question in python:

  1. use python(cpython 2.7.13)

  2. increase the recursion limit

20

me 2… Took a lot of time to find it, at first I thought it was mostly a had hoc problem because a lot of people were solving it and good tutorials on this were hard to find…

2 Likes
21

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

22

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
23

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

1 Like
24

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

25

@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

26

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

27

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

28

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.

29

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

30

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

31

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.

32

@tyrant No. Serf Wikipedia.