PROBLEM LINK:Author: Constantine Sokol DIFFICULTY:Hard PREREQUISITES:Segment Tree, Heavy Light Decomposition, Flow PROBLEM:Given a graph G, consisting of N vertices and M edges, each edge has a positive capacity and each vertex of G belongs to at most one simple cycle. You task is to implement a data structure, which can process the following queries efficiently:
SOLUTION OUTLINES:Link1: Heavy Light Decomposition Firstly, let's assume that the graph given to us consists of a single cycle. Than the solution is obvious: there are only two path between every two distinct vertices. We can simply maintain a segment tree of edges and that's it. Secondly, let's assume that the graph given to us is a tree. That the solution is obvious as well: there's a single path between every two distinct vertices. We can use HeavyLight Decomposition of tree in order to process all the queries and that's it. OK, now let's go back to the problem as it is. Tester's ApproachWe consider a cycle as a node, then graph will be a tree. After this we do HLdecomposition, then each component will be like a (upper component)  cycle  cycle  cycle  cycle. (here cycle = a cycle or an ordinary node). We use a segment tree for each component of HLD, and we also use a segment tree for each cycle. Then we can calculate the maximum flow from some node to the nearest node of upper component of HLD in O(log N). And of course, we can calculate the maximum flow from some node to some node, if both nodes are in the same component in O(log N). The depth of HLD is O(log N), so we can calculate the maximum flow in O( (log N)^2 ). The modification query is not difficult in this approach. Author's ApproachFirsly, let's make our graph rooted(let's assume that the first vertex is the root). Now the processing of the queries is splited into two parts: So, the problem is to raise a single vertex to a cycle. Let's do this for each cycle: we have a cycle 1  2  3  4  ...  K, which consists of K vertices. Then, let's transform it into K  1 edges 1  2, 1  3, 1  4, ..., 1  K, where the capacity of edges 1  L(for 1 < L <= K) is equal to the size of the flow, that can stream through the cycle from vertex L to the vertex 1. If we have no modification queries, than the problem is easy: we simply transform our graph into a tree and then process all the queries the way described above. The problem is with B). If we update the capacity of a cycle edge, that belongs to a big cycle, then we should update a lot of edges and can lead to the TLE verdict. But there are not so many big cycles. Let's call a cycle BIG if it contains at least sqrt( N ) vertices and SMALL otherwise. Then, for each small cycle we can simply update all the (K  1) edges. For big cycle we won't maintain the edges in our HLDOT. We will store them separately. When we need to process a flowquery, we can simply loop through all the big cycles and calculate the size of the flow. So, total complexity: Preprocessing: O( N log N ) So, the solution runs in O( N log N + Q * sqrt( N ) * log( N ) ) AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 11 Aug '14, 15:13

I am sorry to say that even the tester's solution is not upto the mark. Even for a simple test case such as a binary tree with 100000 vertices,99999 edges and 200000 queries each of them of type 0, first of all it shows assertion failed. Even if I remove the assertion it runs in 1.98 seconds whereas my own submission which got TLE runs in 1.43 seconds on my machine. I don't want to sound harsh but the time limit is way too strict and even the tester's solution won't pass under time limit for certain testcases (See this testcase generator http://pastebin.com/73CyaTZa ). Here's my submission http://www.codechef.com/viewsolution/4544977. I am really heartbroken :( :( answered 11 Aug '14, 17:14
I don't know about assertion failing. But results vary from machine to machine if you are talking about execution time. (tester's soln ran within 1s on my machine, even though your solution was faster). And, If your solution is faster on one type of file, does it really mean that it will be fast on all files?
(11 Aug '14, 17:29)
1
1) It's a long contest and it's the hardest problem of the contest. You had a lot of time to speed up your solution. If it was a cookoff or a lunchtime contest, then the time limit would be more friendly, but since it's a long one, you should show your ability to optimize code. 2) Tester's solution works in less than 1s on my laptop. We had a test with a binary tree in our data and Tester's solution passes it as well. By the way, I've passed your solution throught all the testdata. Your solution gives RTE on 20 tests and TLE on 2 tests. Is it acceptable to give AC verdict to such a solution?
(11 Aug '14, 17:55)
1
About assert error, indeed, my (=tester) solution has a small stupid mistake. Now I have fixed it, and CodeChef admin will replace. (This error will not change the running time at all) On your test case, your solution is faster than mine. But my solution also run within 1 sec on judge server. And your solution are slow for other some tests...
(11 Aug '14, 18:17)
1
Peace :) :)
(11 Aug '14, 19:05)

Really liked this problem, although didn't correctly solve it. I was wondering how I should start with these kind of problems. I immediately came up with the following and coded it in that sequence, very likely to tester solution:
I also made up some examples by hand which all passed. I still haven't found my bug(s). Is there a good general approach to start with these kind of problems? Or some ideas how I would be able to quickly find my bug(s)? answered 12 Aug '14, 04:27

Hi, I used the testers approach and got TLE. Despite attempting a lot of optimization I still failed to get and AC. Can you please tell me on which kind of test case I was failing? My Submission answered 13 Aug '14, 10:41

There is a easier algorithm using LCT. It runs in $O((n + q)\log n)$. I learnt it from wangyisong1996. For each cycle, we cut down the edge with the min flow and add its flow to all other edges on the cycle. Then this graph becomes a tree and we can use LCT to calculate the min edge on the path from x to y, which is the answer of query(x, y). As for modifies, we can maintain a heap for each cycle and maintain the LCT. The LCT should support two operations : query the min edge on a path, and add a number on all edges on a path. It's more intuitive than using segment trees on HLD and more easy to implement. Though its complexity is better, it runs slower than HLD, because of the large constant number of LCT. answered 19 Dec '15, 15:18

How can a O( N log N + Q * sqrt( N ) * log( N ) ) algo run under 1 sec!! o.O