Hi, everyone!

2014 World Cup Brasil has started, and I was looking for interesting problems. I found a nice IOI-style problem from Japanese Olympiad In Informatics 2014 (this is not the online contest!). If you know how to read Japanese, you can find the problem "Kanji Shiritori" from the statement file. Here is the translation of the problem, powered by Google Translation and me :D

You are given a weighted directed graph. The graph consists of N (2 ≤ N ≤ 300) vertices and M (1 ≤ M ≤ N × (N - 1)) edges, and there are no loops or multiple edges in this graph. The vertices are numbered by integers from 0 to N - 1, and the edges are numbered by integers from 0 to M - 1. The i-th edge goes from vertex A_i to vertex B_i, and the weight of this edge is C_i. (0 ≤ A_i < N, 0 ≤ B_i < N, A_i ≠ B_i, 1 ≤ C_i ≤ 10¹⁶)

Anna and Bruno have to solve Q (1 ≤ Q ≤ 60) queries during a exam. Each query is given by two integers S_i and T_i (0 < S_i, T_i < N, S_i ≠ T_i), which means that they have to find the shortest "path" from vertex S_i to vertex T_i. It is guaranteed that such path always exists. If there are many possible answers, they can write any of them.

Both Anna and Bruno are given the whole graph and the description of the queries. (Of course, those are the same) Unfortunately, Bruno has forgotten the weight of K (1 ≤ K ≤ 5) distinct edges. (He just forgot the 'weight', not the 'whole edge') Fortunately(?), the start vertex of each queries are all the same.

(Formally, Bruno has forgotten the weight of the U₀-th, U₁-th, ..., U_K - 1-th edge. So Bruno doesn't know the values of C_U0, C_U1, ..., C_UK - 1. It is guaranteed that A_U0 = A_U1 = ... = A_UK - 1.)

Bruno told Anna that he had forgotten the weight of some edges and gave Anna U₀, U₁, ..., U_K - 1. Anna wanted to tell Bruno the weights, but the exam was going to start, so Anna decided to give information during the test by tapping the desk. By one tap, Anna can send a single bit to Bruno.

If Anna taps the desk too much, the supervisor will know that they were cheating. So Anna has to give Bruno as least bits as possible. Let the number of such bits L. Can you make a strategy for Anna and Bruno? If L ≤ 64 you can get full score.

At first I read this problem, I couldn't find any solution near 64 bits. But after I introduced this problem to my friends, unbelievably (at least for me), gs12117 found an algorithm that just requires 22 bits!

His solution is quite simple: For each weight-unknown edge, Anna sends the number of queries whose shortest path passes that edge. With this information, Bruno can find which shortest path(answer for the queries) passes each weight-unknown edge and restore the answer.

Here is the proof below. Because of my poor English skill, I think it is hard to understand. I'm sorry about that.

For all u, v (0 < u, v < N, u ≠ v), the shortest path from vertex u to vertex v passes at most one unknown edge. This is because the start vertex of the weight-unknown edges are all the same. If the path passes more than one weight-unknown edge, there must be an positive cycle in that path, and it is obviously not optimal.

For each query(shortest path) that passes an weight-unknown edge, we define an "benefit" for this (query, weight-unknown edge) pair.

• Let the weight-unknown edge goes from vertex p to vertex q.
• Let the query (s, t).
• Let dist(a, b) the length of the shortest path from vertex a to vertex b. If undefined, it is inf.
• (benefit) = dist(a, b) - dist(a, p) - dist(q, b)

If the shortest path passes (p, q), the length of the shortest path decreases by "(the benefit achieved by passing (p, q)) — (the length of edge (p, q))".

Let's fix the query. (i.e. the source and the sink of the shortest path) If this value is negative for all weight-unknown edges, it is better for the shortest path not to pass any weight-unknown edge. Otherwise, the shortest path must pass the weight-unknown edge which has the maximum benefit.

Bruno can calculate the benefit for all (query, weight-unknown edge) pairs, and find the shortest path. For this, Bruno has to maximize the total benefit following the restriction that Anna has given to her. This can be done by solving the assignment problem. There are many ways to make such matrix. We can use Hungarian method, but because of the low constraints, DP is enough. Now, let's prove that the result we have found is correct.

Take a look the sum of the total weight of all shortest paths that Bruno calculated for all queries. Let's denote this sum as S₁. This equals to the sum of,

• (the sum of the total weight of all shortest paths except the weight of the weight-unknown edges)
• for each weight-unknown edge, (the number of queries that passes the edge)  ×  (the length of that edge)

Let's calculate the sum described above with no weight-unknown edges, and say this S₂

If we decrease S₁ by (the total benefit achieved by passing the weight-unknown edges) minus the sum of (the number of queries that passes the edge)  ×  (the length of that edge) for each weight-unknown edge, the value becomes S₂.

The increased value is a constant for Bruno because it is a restriction given by Anna. Thus, maximizing the total benefit obeying Anna's restriction equals to minimizing the sum of the total weight of the shortest paths.

What if Bruno's result is not optimal? It means that S₁ > S₂. And it also means that (the total benefit calculated by Anna) is bigger than (the total benefit calculated by Bruno), and this is false because Bruno followed the restriction given by Anna.

Therefore we can conclude that Bruno's result is optimal.

There are ₆H₆₀ = 8259888 ≤ 2²³ - 1 different states, so we can use only 22 bits. If you don't want to code this part, you can just send the number of queries passing each weight-unknown edge. This costs 30 bits.

This is the implemention of the solution: Anna, Bruno Most part is coded by ainta.

How do you think about this solution? I think it's brilliant and optimal for this problem, but it is quite hard to implement. I saw the official implementation, and it seemed quite simple, but I can't get the idea.

• Sorry for the confusing title :| If you have a great title, please write in the comments