Distributed Load Balancing

Limits: 0.5 sec., 1024 MiB

The goal of this task is to solve a load balancing problem with multiple agents in a telecommunication network for the case where agents cannot explicitly exchange information.

We consider a telecommunication network environment where agents act on the same network. The network consists of nodes and undirected links that connect them. Some of the nodes are where agents are located, and multiple agents can share the same node.

Each agent has to send data at some rate to some of the other agents and has a finite number of paths (sequence of links and nodes) to send traffic to the other agents. Each link in the network has a maximum bandwidth capacity and may be used by several paths of several agents at the same time in any direction.

Let’s consider an example of the network below.

The network consists of 7 nodes and 8 links connecting them. The numbers on links indicate the capacity of the corresponding link.

There are 3 agents: Alice (located at node 5), Bob (located at node 7), and John (located at node 6).

Alice has to send 10 MB/s of data to Bob, and can use the following two paths for this: \(5 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 7\) and \(5 \rightarrow 1 \rightarrow 4 \rightarrow 7\).

Bob has to send 10 MB/s of data to John, and can use the following two paths: \(7 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 6\) and \(7 \rightarrow 4 \rightarrow 3 \rightarrow 6\).

In this example, John does not send any data to other agents.

Link utilization

Link utilization represents the ratio of the traffic currently running through the link (regardless of the direction) to its capacity, i.e. \(\frac{\textrm{Total traffic of the link}}{\textrm{Capacity of the link}}\). The maximum link utilization (MLU) is calculated as maximum link utilization among all links and is an important notion in telecommunication networks since it permits to evaluate the network congestion. The goal is to minimize the MLU of the network.

In order to avoid a traffic loss or delay, all link capacities have to be respected as much as possible. When all link capacities are respected, the split of traffic is called feasible. However, it is called optimal if its corresponding MLU is minimum. Note that if the \(MLU \le 1\), the associated split of traffic is considered feasible.

Distributed algorithm

Each agent is aware of all existing network links, data that this agent needs to send to other agents, along with a list of paths that can be used for that.

Each agent is not aware of the data sent by other agents or what paths they use. However, periodically, each agent receives the current utilization of all links and the number of agents using each link in the network. Using the given information, each agent must decide how to split the data over his paths without exceeding the link capacities and minimizing the MLU of the network.

Each test case will be split into 30 steps. At each step, all agents will receive current link utilization and have to independently decide how to distribute the data transfer. Once all of their decisions are collected, they are applied to the new link utilization. The new total utilization is then given to all agents on the next step. Initially (before the first step) the utilization of all links is equal to zero. Note that the solution is not executed for agents that don’t send any data to other agents.

Additionally, agents have the ability to broadcast two real values to all other agents on the next step. It’s up to you to decide the meaning of those values, and how to use them when processing agents.

Note that the overall structure of the network, as well as sources, destinations, and amounts of data being sent will not change from step to step.

Your task is to implement a program that will be making the data distribution decision on behalf of agents at all given steps.

The details on the solution scoring are given in the Notes section below.

Input

The first line of the input contains three integers \(n\), \(m\), and \(k\), which describe the number of nodes, the number of links of the network, and the number of agents, respectively.

Nodes are numbered with integers from 1 to \(n\), inclusive.

The following \(k\) lines describe agents.

For each agent with index \(i\) (between 1 and \(k\), inclusive), a single line contains three space-separated numbers \(a_i\), \(b_{1i}\), \(b_{2i}\) which describe the integer index of the node the corresponding agent is in, as well as two real numbers broadcast by the corresponding agent. On the first execution step, all broadcast numbers will be equal to zero. The broadcast numbers will also be zero for all agents that don’t send any data to other agents.

The following \(m\) lines describe links of the network.

For each network link with index \(j\) (between 1 to \(m\), inclusive), a single line contains five space-separated numbers \(u_j\), \(v_j\), \(cap_j\), \(util_j\), \(count_j\) which describe the following:

• \(u_j\), \(v_j\) — the integer indicies of the nodes connected by the corresponding two-way link

• \(cap_j\) — the maximum feasible total utilization of the link (real number, in MB/s)

• \(util_j\) — the current absolute link unitialization (real number, in MB/s)

• \(count_j\) — the non-negative integer number of agents that used the corresponding link on the previous step. An agent is using a link if they send a non-zero amount of traffic over this edge to any of destination agents. This value will be equal to zero on the first step.

The next line contains three space-separated integers \(t\), \(v\), and \(c_{dest}\), which describe the following:

• \(t\) — the index of the currently processed step (between 1 and 30, inclusive)

• \(v\) — the index of the currently processed agent (betwen 1 and \(k\), inclusive)

• \(c_{dest}\) — the number of destination agents that the current agent needs to send traffic to

The following \(c_{dest}\) lines describe destination agents.

For each destination agent with index \(q\) (between 1 and \(c_{dest}\), inclusive), the first line contains two integers \(dest_q\), \(path\_count_q\), and a real number \(amount_q\) (space-separated) — the index of the destination agent, the number of paths that can be used to send data, and the traffic rate sent (in MB/s), respectively. The following \(path\_count_q\) lines describe paths that can be used to send data to the destination. For each path with index \(p\) (between 1 and \(path\_count_q\), inclusive), a single line containts an integer \(len_{qp}\) — the number of nodes in the corresponding path, followed by \(len_{qp}\) integers \(path_{qpl}\) which describe the corresponding path edges in order.

Each agent can choose multiple paths to send traffic to a single destination agent, but the total data rate sent should be equal to \(amount_q\). All paths will be valid simple graph paths that begin and end at the corresponding source and destination agent nodes. Note that the same agent can appear multiple times as a destination agent.

For each test case, it’s guaranteed that a feasible data distribution exists.

All real numbers in the input will be given in double-precision floating-point format with maximum precision available.

Output

For each of the \(c_{dest}\) destination nodes print \(path\_count_q\) space-separated non-negative real values \(transmit_{qp}\), which describe the rate (in MB/s) of data trasmitted over the \(p\)-th path to the \(q\)-th destination agent.

The total rate transferred to the \(q\)-th destination agent must be equal to the rate requested, i.e. \(\sum_{p=1}^{path\_count_q} transmit_{qp} = amount_q\) for each destination agent \(q\) from 1 to \(c_{dest}\). The total rate will be considered correct if the absolute or relative error does not exceed \(10^{-11}\).

After that, print a line with exactly two real values \(b_1\) and \(b_2\) — the values that will be broadcast to all agents on the next step.

All real numbers in the output must be given in double-precision floating-point format.

Constraints

\(1 \le n \le 800\), \(1 \le m \le 20000\), \(1 \le k \le 50\),

\(1 \le a_i \le n\),

\(1 \le u_j, v_j \le n, u_j \ne v_j\),

\(0 \le cap_j, amount_q \le 10^5\),

\(1 \le c_{dest} \le 7\),

\(1 \le path\_count_q \le 5\),

\(1 \le len_{qp} \le 200\),

\(1 \le path_{qpl} \le m\).

Notes

Submissions

• Your solution will be executed for each step from 1 to 30 and for each agent independently. It’s guaranteed that the input values provided to agents are valid and based on outputs of all agents from the previous step.

• The time limit is 0.5 seconds and the memory limit is 1024 mibibytes for each independent execution.

• Since your solution is executed for each step and agent independently, the total evaluation time will be higher than usual. Please be patient.

• If the solution exceeds given limits or produces an invalid output, the score will be equal to zero.

• The code size limit is 64 kibibytes.

• The compilation time limit is 1 minute.

• There are 15 provisional test cases. Your submissions will be evaluated on provisional set during the submission phase.

• You can submit your code once per 60 minutes and you will get a feedback with your score for each of the provisional tests.

• There will be 50 test cases in the final testing after the submission phase is over.

Scoring

The following two parameters are used to evaluate and count the final score:

• \(A\) — The gap from the optimal solution after all 30 iterations. The gap is calculated in the following way: \(\frac{MLU_{current}-MLU_{optimal}}{MLU_{optimal}}\), where \(MLU_{optimal}\) is the optimal solution to the network traffic distribution, and \(MLU_{current}\) is the MLU after 30 steps of the solution.

• \(B\) — The feasible solution factor defined as the number of feasible solutions among all 30 steps executed divided by 30. A solution is feasible if every agent splits all its data flow over his paths and all link capacities are satisfied.

The score for a single test is calculated in the following way: \(\left\lfloor 1000000 \cdot \max{(0, 1 - A)} + 500000 \cdot B \right\rfloor,\) where \(A\) and \(B\) are the parameters described above. Note that the maximum score for a single test case is \(1000000 + 500000 = 1500000\).

The total score is calculated as the sum of scores among all test cases.

Quick start

Below we provide a sample solution which distributes data evenly among all paths available. The source code is available for all contest programming languages:

• C++

• Python

• Java

• C#

• Pascal

• F#

Sample

Let’s consider an example based on the previously described network.

On the first step, your solution will be executed twice. The first execution corresponds to Alice’s point of view, and the second for Bob’s.

The Alice’s input and sample output might look like this:

7 8 3
5 0 0
6 0 0
7 0 0
5 1 500 0 0
1 2 10 0 0
1 4 10 0 0
4 2 10 0 0
4 7 500 0 0
2 3 10 0 0
4 3 10 0 0
3 6 500 0 0
1 1 1
3 2 10
4 1 2 4 5
3 1 3 5

5.0 5.0
1 0

In the example above, Alice decided to split data equally over the two paths available, sending 5 MB/s over each path. Additionally, Alice broadcasts two real numbers 1 and 0 to other agents.

On the next execution, your program will be given input on behalf of Bob. Note that the solution is not executed on behalf of agent John as he is not sending any data to other agents.

The input and sample output might look like this:

7 8 3
5 0 0
6 0 0
7 0 0
5 1 500 0 0
1 2 10 0 0
1 4 10 0 0
4 2 10 0 0
4 7 500 0 0
2 3 10 0 0
4 3 10 0 0
3 6 500 0 0
1 3 1
2 2 10
4 5 4 6 8
3 5 7 8

5.0 5.0
0 1

This concludes the first step of the solution execution, and the total link utilization looks like this:

It’s easy to see that \(MLU = 1\) in this case, as the link between nodes 2 and 4 is fully utilized, while the others are not. Since \(MLU \le 1\), this data distribution in considered feasible.

It can also be proven that the \(MLU_{optimal} = \frac{2}{3}\), which means the MLU gap is equal to \[\frac{MLU_{current}-MLU_{optimal}}{MLU_{optimal}} = \frac{1-\frac{2}{3}}{\frac{2}{3}} = \frac{1}{2}.\]

Let’s consider the second step.

This time, the solution will be given the updated link utilization, as well as real values broadcast by the agents.

The Alice’s input and output on the second step could look like this:

7 8 3
5 1 0
6 0 0
7 0 1
5 1 500 10 1
1 2 10 5 1
1 4 10 5 1
4 2 10 10 2
4 7 500 20 2
2 3 10 5 1
4 3 10 5 1
3 6 500 10 1
2 1 1
3 2 10
4 1 2 4 5
3 1 3 5

6.666666666666666 3.333333333333333
0 1

In this case, Alice decided to split \(\frac{2}{3}\) of the traffic over the first path, and the remaining \(\frac{1}{3}\) over the second.

Similarly, let’s consider Bob’s input and output on the second step:

7 8 3
5 1 0
6 0 0
7 0 1
5 1 500 10 1
1 2 10 5 1
1 4 10 5 1
4 2 10 10 2
4 7 500 20 2
2 3 10 5 1
4 3 10 5 1
3 6 500 10 1
2 3 1
2 2 10
4 5 4 6 8
3 5 7 8

6.666666666666666 3.333333333333333
1 0

Just like Alice, Bob decided to split \(\frac{2}{3}\) of the traffic over the first path, and the remaining \(\frac{1}{3}\) over the second.

This concludes the second step with the following network links utilization:

In this case, both Alice and Bob are sending \(10 \cdot \frac{2}{3}\) of traffic over the link between nodes 2 and 4. This means that the distribution is not feasible, as \(MLU = \frac{40/3}{10} > 1\).

Let’s also consider the third step.

The Alice’s input and output on the third step could look like this:

7 8 3
5 0 1
6 0 0
7 1 0
5 1 500 10 1
1 2 10 6.666666666666666 1
1 4 10 3.333333333333333 1
4 2 10 13.333333333333333 2
4 7 500 20 2
2 3 10 6.666666666666666 1
4 3 10 3.333333333333333 1
3 6 500 10 1
3 1 1
3 2 10
4 1 2 4 5
3 1 3 5

3.333333333333333 6.666666666666666
1 0

In this case, Alice decided to split \(\frac{1}{3}\) of the traffic over the first path, and the remaining \(\frac{2}{3}\) over the second.

Similarly, let’s consider Bob’s input and output on the third step:

7 8 3
5 0 1
6 0 0
7 1 0
5 1 500 10 1
1 2 10 6.666666666666666 1
1 4 10 3.333333333333333 1
4 2 10 13.333333333333333 2
4 7 500 20 2
2 3 10 6.666666666666666 1
4 3 10 3.333333333333333 1
3 6 500 10 1
3 3 1
2 2 10
4 5 4 6 8
3 5 7 8

3.333333333333333 6.666666666666666
0 1

Just like Alice, Bob decided to split \(\frac{1}{3}\) of the traffic over the first path, and the remaining \(\frac{2}{3}\) over the second.

This concludes the third step, with the following links utilizations:

In this case, both Alice and Bob are sending \(10 \cdot \frac{1}{3}\) of traffic over the link between nodes 2 and 4. This means that the distribution is feasible, as \(MLU = \frac{20/3}{10} < 1\). It can also be proven that this distribution is optimal for the given network, which means that the MLU gap will be equal to 0.