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

×

KINGCON - Editorial

8
5

PROBLEM LINK:

Practice
Contest

Author: Jay Pandya
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

EASY

PREREQUISITES:

Biconnected components

PROBLEM:

Getting rid of the story line the problem simply asks to find the number of articulation points in the undirected graph and multiply it by K.

EXPLANATION:

Naive approach would be for each vertex delete it from the graph and check the connectivity. Such approach has complexity O(N * M) and should get TLE. So something clever should be invented.

The problem could be solved using simple DFS in O(N + M) time. For this, some magic value low(v) is calculated for each vertex v and this allows to check whether v is articulation point in O(1) time inside DFS. The root of the DFS traversal tree should be analyzed in another way. Namely it will be an articulation point if and only if it has at least two sons in this tree.

But sincerely speaking biconnected components, articulation points and bridges is one of my unfavorite topics :)
So I prefer to forward you to some existing tutorials for further details of the mentioned approach:

  • Exercise 23-2 in famous book "Introduction to Algorithms" by Cormen and others.
  • The article on e-maxx.ru. It seems to be very well written but unfortunately it is only in Russian. But code there is working - I've checked and get AC here :) But be careful with IS_CUTPOINT(v); it could say this several times for the same vertex.
  • The article at Wikipedia. Unfortunately it contains no code snippets so it could be hard to learn this topic efficiently from there.
  • Yet another tutorial. It seems to be really good introduction to DFS and its applications with code snippets.
  • Several other tutorials: click, click, click.

Also I provide a lot of related problems on biconnected components, so don't blame me much for not writing yet another tutorial on this topic :)

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be provided soon.
Tester's solution can be found here.

RELATED PROBLEMS:

UVA - 796 - Critical Links
TJU - 2840 - Apple Tree
UVA - 610 - Street Directions
UVA - 10972 - RevolC FaeLoN
PKU - 3177 - Redundant Paths
Live Archive - 4186 - Lucky cities

This question is marked "community wiki".

asked 15 Apr '13, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

edited 17 Apr '13, 13:12

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

(15 Apr '13, 15:42) bugkiller3★

Is this problem the same as the "minimum vertex cover" problem?

(16 Apr '13, 12:13) tyrant2★

@tyrant No. Serf Wikipedia.

(17 Apr '13, 13:03) anton_lunyov ♦6★

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

(16 May '13, 19:55) banarun4★

Thanks for the new algorithm I can learn, never met that before.

link

answered 15 Apr '13, 15:11

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

2

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

(15 Apr '13, 15:17) junior944★

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.

(16 Apr '13, 21:06) kunaal4★

@avinrox: It is not just DFS. You have to do some more stuff which is explained in all the links in the editorial. Even i found it difficult to understand the extra magic that went in after we DF traversal, but later made sense after i read it multiple times. Here is my simplified understanding of it.

Assume you have a graph (for simplicity assume it is a fully connected graph, so no matter from which node we start, we end up with only 1 forest). Now imagine you take off a node from DF tree. Now by removing the node (yellow node in below image) , we have literally divided the tree in to ,many forests, one with all nodes above the deleted node and others at the children's of the deleted node.(see image again). alt text Now after deleting the node, we need to find if there is any way for children nodes to find a path back to the forest#1. That is when we start adding back edges and check if there is way up to forest#1. If we see node "C" and node "D", have a way back to forest#1 (through dotted back edge), but no such back edge exists for any of the nodes in forest#2. Hence deleting the node, will eventually lead to breaking up of a connected tree in to multiple forest and hence it (yellow node) is a articulation point.

Hope it helps :) Please correct if i've misunderstood something.

link

answered 15 Apr '13, 18:03

prakash1529's gravatar image

3★prakash1529
16625
accept rate: 0%

@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

(15 Apr '13, 18:05) prakash15293★

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

http://ideone.com/nhNVCe

(15 Apr '13, 18:19) betlista ♦♦3★

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

(15 Apr '13, 19:04) prakash15293★

Okay articulation points concept was a new thing to me. But I tried another approach:

That for each vertex(V) having more than one vertices, we apply DFS on any of its adjacent vertex and see if all other adjacent vertices can be reached through some other path except V or not. That led to TLE. Can you please tell why? It seems really time consuming, but can't I just put some trick to run within TL? http://www.codechef.com/viewsolution/2019855

link

answered 15 Apr '13, 16:10

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

2

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.

(15 Apr '13, 16:14) anton_lunyov ♦6★
1

@bugkiller I tried the same, but it was only "are test cases weak?" test...

(15 Apr '13, 16:16) betlista ♦♦3★

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

(15 Apr '13, 16:24) bugkiller3★

I have used the following approach :

 1. get the degree of each node in the graph.
 2. while(all nodes are not visited)
    {
        a. consider node N with maximum degree.if degree of two nodes are equal, then the one which is visited gets preference.
        b. for each of its neighbor
           {
               i.  mark the neighbor as visited.
               ii. reduce the degree of neighbor by 1.
           }
        c. mark the node N as visited.
        d. reduce the degree of N to 0.
    }
3. the number of times the above loop executes, is the required count.

Following is my attempt for this problem :

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

Hence or otherwise, could you explain why DFS should give the solution?

link

answered 15 Apr '13, 16:56

avinrox's gravatar image

2★avinrox
2075
accept rate: 10%

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.

(17 Apr '13, 13:19) anton_lunyov ♦6★

Can anyone explain me whats wrong in my code which I have written in python..... Since similar submission of mine got accepted in C++

link

answered 15 Apr '13, 18:31

devanshug's gravatar image

4★devanshug
2.7k111927
accept rate: 13%

Here I encountered the wierdest error of all times. For one sequence of input i got correct answer for other sequence of same input i got runtime error in C++ finally i submitted in c with same idea and got AC. Articulation points was definitely new concept and worth learning thanks to codechef :)

link

answered 15 Apr '13, 18:39

amitupadhyay's gravatar image

2★amitupadhyay
1.4k92241
accept rate: 14%

can anyone please look at http://www.codechef.com/viewplaintext/2037379. I used the same dfs approach mentioned but still I am getting a TLE. Where I am going wrong?

link

answered 15 Apr '13, 23:39

vagrawal13's gravatar image

2★vagrawal13
152
accept rate: 0%

Hello, this was my first participation in a Codechef contest. When I saw this problem, I immediately recalled my Discrete Mathematics lessons and implemented an algorithm searching articulations. I believe it runs in O(n), but still I got TLE. Coud anyone please have a look at it and tell me what's wrong? Thanks a lot. For clarification: I colored nodes that have not been opened yet as WHITE, nodes whose descendants are being searched are GREY and nodes whose all descendants have been searched are BLACK.

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

link

answered 16 Apr '13, 07:15

milhaus's gravatar image

2★milhaus
464
accept rate: 0%

@vagrawal13: I had a look at your code, I think instead of this:

FOR(i,0,n)
    if(pre[i] == -1)
        dfs(i,i);

You can just call dfs(0,0), since in the beginning there is "unity" so the dfs(0, 0) will go through all nodes. Otherwise I didn't notice any problem with your code. My Java code is similar and also TLE, so I hope somebody can explain this to us :-)

link

answered 16 Apr '13, 09:18

milhaus's gravatar image

2★milhaus
464
accept rate: 0%

edited 16 Apr '13, 10:23

I've just checked a successful Java solution. I noticed the programmer used a custom fast I/O, so I modified my own solution with this fast I/O and got AC. So even using Java buffered streams is not fast enough and it is neccessary to use custom I/O. I think this should be included in the FAQ. Don't you use Scanner, don't you use BufferedReader, use custom I/O. It is a huge difference !!! I measured execution of 100 test cases (all of them being the example test case). When using BufferedReader + Scanner it took 0.646 seconds, when using custom I/O it just took 0.026 seconds.

@vagrawal13: I guess your problem is the same as mine, you can use eg. getInt() from @bhambya 's code, I think you will get an AC: http://www.codechef.com/viewsolution/2018093

link

answered 16 Apr '13, 10:21

milhaus's gravatar image

2★milhaus
464
accept rate: 0%

edited 16 Apr '13, 10:24

I used the same dfs approach, but was getting the TLE. And I even tried using fast IO, but it did not work. Finally is modified my code to if(m == n*(n-1)/2) return 0 ,as for complete graph there are no cut nodes and it got AC. My code was in java. I still don't understand how many milliseconds did it save!

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

link

answered 16 Apr '13, 10:40

anunay_arunav's gravatar image

3★anunay_arunav
1963613
accept rate: 0%

edited 16 Apr '13, 11:23

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.

(16 Apr '13, 11:09) bugkiller3★

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

(16 Apr '13, 11:11) bugkiller3★

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

link

answered 16 Apr '13, 12:50

vagrawal13's gravatar image

2★vagrawal13
152
accept rate: 0%

@Tester: It is my attempt for this problem - http://www.codechef.com/viewsolution/2056304 . can anyone please look at it and tell me why it getting WA (can I know the test cases for which it getting WA)

link

answered 17 Apr '13, 12:07

sushilkumar's gravatar image

4★sushilkumar
463
accept rate: 0%

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

link

answered 02 Aug '14, 12:17

vicky2135's gravatar image

4★vicky2135
112
accept rate: 0%

This article explains the algorithm for finding articulation points very well. It has got code too. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

link

answered 31 Dec '14, 16:30

codester94's gravatar image

4★codester94
11
accept rate: 0%

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

link

answered 09 Jan '18, 16:44

jasmeet101's gravatar image

3★jasmeet101
11
accept rate: 0%

edited 09 Jan '18, 17:11

I tried to solve the prob using Articulation Point concept but , am getting TLE. https://www.codechef.com/viewsolution/22527020 :->Here is my solution. Please debug my code

link

answered 18 Jan, 20:21

alpha_better's gravatar image

4★alpha_better
31
accept rate: 0%

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

link

answered 27 Jan, 14:42

skyap79's gravatar image

4★skyap79
1
accept rate: 0%

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:

×15,631
×3,741
×1,217
×725
×15
×3

question asked: 15 Apr '13, 15:00

question was seen: 10,643 times

last updated: 27 Jan, 14:42