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