Please note: the language of this site will now be ENGLISH. Please do not use another language since visitors from different countries will participate in training.

Week 6 - Graphs (2)

The tasks for week 6 are as follows:

Week problem: 00315 Network
Weekend problem: 11080 Place the Guards
Suggested bonus: 11838 Come and Go

Read up on articulation points, bipartite graphs and strongly connected components.

You must submit your solutions on http://uva.onlinejudge.org/

You can browse to these problems from the online judge website by clicking on Browse Problems, Contest Volumes, and then selecting the contest volume as indicated above.

asked Jul 11, 2012 in Tasks by eljakimit

Please post below which of the questions you have been able to finish.

For each task, please let us know how much time you have spent on understanding / coding / debugging.

For each task let us know what the hardest part was. (This can be anything, ranging from not having read the problem to forgetting about a border case, to a semicolon in the wrong spot that screwed up an if-statement...)

1 Answer

0 votes

I had some trouble with Network as the input does not give how many of each there are, it depends on lines instead, which I am not used to.

I also just switched to VIM

I did the other two easily, the third one in literally 5 minutes

answered Jul 18, 2012 by bvdbijl
edited Jul 19, 2012 by bvdbijl

Did you use Tarjan Algorithm for the third problem? Because you can also solve it using a simple O(V^2) DFS, but you should have used Tarjan: O(E+V) :). Unfortunately the test cases are bad....

I also had the most problems with Network, first I misunderstood the algorithm for articulation points.

Yeah, DFS on every point did the job fine, N was never more than 2000

I am learning Tarjan's tomorrow, the network problem of the CEOI also needed this algorithm

Yes I know that Network subtask A also needed Tarjan, that was for me the reason to use Tarjan here, so that I really understand it :) (it's not difficult).

NL: NIO UK: BIO Int: IOI
...