## 11248 - Frequency Hopping

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 11248 - Frequency Hopping

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``````
I code, therefore I am.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
possible option:(1,4),(3,2)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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).
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Adrian Kuegel wrote:... 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". I code, therefore I am.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
There is another way which needs only O(n) network flows. In fact it is similar to step 2 of mf's algorithm.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.