PUSHFLOW - Editorial

PROBLEM LINK:

Practice
Contest

Author: Constantine Sokol
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

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:

  • 0 S T: find the maximum flow in G in case the source is S and the sink is T;
  • 1 X NEW_CAPACITY: make the capacity of X'th edge equal to NEW_CAPACITY.

SOLUTION OUTLINES:

Link1: Heavy Light Decomposition
Link2: Heavy Light Decomposition
If you don’t know about HLD you can read about it on the previous editorials etc. :).

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 Heavy-Light 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 Approach

We consider a cycle as a node, then graph will be a tree. After this we do HL-decomposition, 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.
If the edge is in cycle, we modify this cycle, and then modify HLD.
Otherwise, we just modify HLD.
It will be done in O(log N).

Author’s Approach

Firsly, 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:

  1. We need to raise both vertices A and B to the same cycle.
  2. Then, just simply solve the problem of a cycle(described before).

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.
But the problem is that we have modification queries. :slight_smile:
If we modify the capacity of an edge, that doesn’t belong to any cycle(let’s call it a tree edge), then we can simply maintain such edges with HLDOT.
If we modify the capacity of an edge, that does belong to a cycle(let’s call it a cycle edge), then we should:
A) Update the corresponding segment tree with the new capacity.
B) Update the capacity of all (K - 1) edges, that we built for the cycle of this cycle edge.

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 flow-query, we can simply loop through all the big cycles and calculate the size of the flow.

So, total complexity:

Preprocessing: O( N log N )
Change-query: O( log N ) for an tree edge, O( K * log N ) for an cycle edge of a small cycle, O( log N ) for an cycle edge of a big cycle.
Flow-query: O( ( log N ) ** 2 + T * log N ), where T equals to the number of big cycles.
The complexity of change-query won’t exceed sqrt( N ) * log N.
The complexity of flow-query won’t exceed sqrt( N ) * log N as well.

So, the solution runs in O( N log N + Q * sqrt( N ) * log( N ) )

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution

3 Likes

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

1 Like

To clarify:

Author’s solution doesn’t get AC. It was meant to, but now it doesn’t. The reason is that Hiroto(the Tester) has came up with a better one, so we decided to use his solution as the model one.

Nevertheless, Author’s approach is rather interesting, so we decided to share it with you.

3 Likes

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 :frowning: :frowning:

1 Like

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?

  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 cook-off 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?

1 Like

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…

1 Like

Peace :slight_smile: :slight_smile:

1 Like

His solution had a small bug, it’s been fixed and updated solution has been put up.

1 Like

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:

  • Preprocessing:
  • dfs to detect cycles/bridges, each cycle is a node
  • dfs to root the tree and immediately add LCA
  • dfs to find heavy paths (heavy paths are also modeled with segment trees)
  • Queries:
  • Query: Min(flow(x,LCA(x,y),flow(y,LCA(x,y)) where flow(A,B) is letting A climbing up to B tracking the minimum, using heavy paths if any + if LCA(a,b) is a cycle then the min flow in that cycle is checked as well
  • Update: update node + it’s heavy path if node is on heavy path

My 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)?

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

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

1 Like

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.