11248 - Frequency Hopping

[Cho]

Two clarifications requested:

Would there be more than one edge connecting the same pair of stations?
i.e. Are the following valid test cases?

Code: Select all

2 2 2
1 2 1
1 2 1

2 2 3
1 2 1
1 2 2

0 0 0

... print all pairs of stations (in ascending order) ...

This is somehow ambiguous to me.
Ascending order of the edges's appearance in the input data?
Or ascending order of the stations connected by the edges?
i.e. What is the correct output of the following test case?

Code: Select all

4 4 3
3 2 1
1 3 2
2 4 2
4 1 1
0 0 0

[Adrian Kuegel]

I can't answer your question, but something I have found out about the input: it seems there are channels from one station to itself. Not sure if there are also duplicate channels between two stations, I would handle that as one channel with added frequency values (which should be the correct way to handle this, but then it is not clear if we should print the solution pair also multiple times).
Anyway, my algorithm (or my network flow implementation) is not good enough to avoid TLE. I have something which runs in O(n^4).
Edit: got Accepted by improving my implementation of the preflow push algorithm; I use now the gap heuristic mentioned in CLRS.
To answer some of your questions: for your input the output is "not possible"; note that channels are unidirectional (this is also written in the problem statement). The order in the output should be according to the stations, so sort the solution edges by start station, then by end station.
If you use the test case:
4 4 3
3 2 1
1 3 2
2 4 2
1 4 1
the answer would be:
possible option:(1,4),(3,2)

[mf]

To answer some of your questions: for your input the output is "not possible"

not possible, are you sure?

I use Edmonds-Karp for maximum flow, and get WA after 2 seconds with this algorithm:
1. Compute value F of maximum flow between nodes 1 and N. If F>=C, output "yes".
2. Find with a Dijkstra-like algorithm for each node u, maximum capacities p1 and p2 of paths in the residual graph from 1 to u, and from u to N, respectively.
3. Output all pairs (u,v) in lexicographical order such that (u,v) is an edge of the original graph, and F + min(p1, p2[v]) >= C.
Does anyone see any problem with it?

[Adrian Kuegel]

Yes, I am sure the output for that test case must be "not possible" (of course with Case number is shown in problem statement).
Because edge 4 1 1 can be ignored completely, a channel from 4 to 1 is not useful, because it can not be used in other direction.
So there is exactly one path from 1 to 4:
1 -> 3 -> 2 -> 4
And capacities on the edges are 2, 1, 2
so to get a flow of 3, we would need to increase capacities on all 3 edges (which is not allowed).
About your algorithm:
I also got this idea first, but I think this part is wrong:

2. Find with a Dijkstra-like algorithm for each node u, maximum capacities p1 and p2 of paths in the residual graph from 1 to u, and from u to N, respectively.

This will only determine the maximum capacity on one path, but it is allowed to use several paths.
I think I have a counter example:
4 4 3
1 2 2
2 3 2
1 3 2
3 4 1
output should be: possible option:(3,4)
but I think you would print not possible.

[mf]

Ok, sorry. I thought you said not possible for the first Cho's case. I didn't notice that the other two were different.

Thanks for the test case!

[Cho]

... note that channels are unidirectional (this is also written in the problem statement). ...

Yes, I noticed that, but my sucking mind somehow translated it to "undirected".

[sclo]

Well, the only method that I can think of that actually produces the correct answer is to find the maxflow for each edge in the minimum cut with capacity modified to be infinity. Of course, that would tle.

[rio]

I'm thinking near idea. Using two min-cuts, from s and from t.

Actually, I'm not good at network flow, I have one question:
Let (S, T) be the sets of nodes divided by min-cut. I know there is various way of dividing.
Is there a min-cut (S', T') such that S' is included in S for all min-cut (S, T) ?

If the answer is "Yes", let S' be the "minimum" for S and T'' be the "minimum" for T, we should just consider the edges which S' -> T''.


Anyway, I have to improve my maxflow algorithm. Reading book "Combinatorial Optimization"..
I hope you understand my English.
----
Rio

[Adrian Kuegel]

There is another way which needs only O(n) network flows. In fact it is similar to step 2 of mf's algorithm.

[sclo]

Suppose the set S and T are the two sides of the boundary of the mincut. I would try running maxflow in the residual network from 1 to each vertex u in S, and from each vertex v in T to n.
Then we have a solution if there exists edge u->v and min(f(u),f(v))+F>=C.

That's basically similar to mf's.

[Adrian Kuegel]

Yes, that is what I meant, only that I don't run it in the residual graph, but instead each time I add an additional edge, so if I run it for node u, I add an edge from source to u with capacity C, and the condition in the end becomes min(f(u),f(v)) >= C.

[jah]

Reading Rio's post many doubts came to my mind.
I don't know if this method is incorrect:

1) Find the maxflow F and it's corresponding mincut.
2) For each node in S which shares and edge with an edge in T find the additional flow which can be sent from the source.
3) For each node in T sharing and edge with S, considering the edges from (S,T) as blocked (so it doesn't cancel existant flow), find the maxflow to the sink.

( 3 and 4 O(n) maxflows in total)

4) Finally for each node in s' in S and t' in T such that (s',t') is an edge find if F + min(additional flow up to s', additional flow from t') >= C.

I don't know if i'm doing something wrong in 3) in order to consider all the max-flows. I should review some theory, . Perhaps in step 3) i shouldn't block (s,t) edges.

[sclo]

I think all of our methods are equivalent. The problem is how to get it to pass the 10 sec time limit. Either wait for the new servers to start working, or implement the CLRS stuff.

Still getting TLE, even after I implemented the relabel-to-front algorithm.

[Adrian Kuegel]

Did you also implement the gap heuristic? It is posed as a problem at the end of the chapter. I implemented it in such a way that the complexity of the algorithm remains the same (for each relabel operation, I have amortized O(1) for the gap heuristic). For only calculating the minimum cut, my program needs about 0.25 seconds for all test cases.

[sclo]

Thanks, when I have time, I'll try to speed up my gap heuristic, mine is too slow.