Information Theory #6 - Amusement Park

I am writing a series of posts about Information Theory problems. You may find the previous one here.

The problem we will analyze is Amusement Park from the Japanese Olympiad in Informatics Open Contest (JOI Open 2017). You may find the problem statement and a place to submit here.

A synthesis of the problem statement is : You are given a connected graph of N vertices and M edges (60 <= N <= 10000, M <= 20000) . JOI-kun must tell the integer X ( 0 <= X <= 2^60 - 1) to IOI-chan, but he cannot do that directly. Instead, he will write either 0 or 1 in each vertex.  IOI-chan can read the integer written on the vertex currently at and move to any adjacent vertex. Help IOI-chan discover X by using the smallest possible number of movements. You must submit two files:

• One that given the structure of the graph and the integer X, writes 0 or 1 on each vertex. Note that JOI-kun does not know the starting vertex of IOI-chan.
• One that given a starting vertex and the graph structure, uses the least number of moves such that with the integers written on the visited vertices it can recover the integer X.

The scoring of the subtasks is based on the maximum number of moves IOI-chan does. In order to score 100 points, you must find a solution that uses at most 120 moves.

I will not discuss the first subtasks because I found a solution that in my opinion is conceptually simple (it is basically a DFS) and already scores 78 points going up to subtask 4. Thus, we will discuss the DFS idea and the final solution.

A DFS approach : 78 points

There are some initial steps that are common to almost all approaches to this problem. They are necessary in order to solve the problem because they take care of the basic : how to send X with 0's and 1's

The idea is : we will have to use the binary encoding of X to send it with 0's and 1's. The strategy will be as follows : we will assign for each vertex which of the 60 bits it represents; we must find a procedure that produces the same result for IOI-chan and JOI-kun, because we need to be sure that we are correctly receiving the message.

The next step of this idea is : we need to find an efficient way of moving between the vertices such that we can recover the 60 bits quickly. When we get all the bits, we stop moving and report X. In order to achieve this, we have to also think about the way we assign the bit for each vertex, because this assignment heavily impacts in the number of movements.

The final step is : it is easier to solve this problem on a tree. Because of the tree properties, it is simple to find a correct way to assign the bits to the vertices and it is less complicated to decide where to move compared to a general graph. Due to the fact that our graph is connected, we can always find a spanning tree of the graph and transform the general graph into a tree.

An algorithm that finds a spanning tree and also finds an efficient way of choosing the bits is the Depth-First Search. Let's take a look :

We start the algorithm by doing the DFS from any vertex of the graph. There are two key ideas that make the algorithm efficient:

• If a vertex was the (i)-th vertex to be discovered by the DFS, we define its discovery time as (i - 1). The bit that we will assign for this vertex will be (i - 1) modulo 60.
• We keep the edges used to discover of a new vertex as the edges of our spanning tree. Thus, we build the tree as we assign the bits

By doing that, the only remaining step is to find an efficient way to move in order to quickly discover all the 60 bits.

However, the way we move will also be heavily inspired by the DFS. Suppose that we are currently at a vertex v and let T be the subtree of v considering that the tree is rooted at the starting vertex of the DFS. There are two cases:

• The size of T is bigger than or equal to 60. We just follow the DFS order and stop when all the 60 bits are found.
• The size of T is smaller than 60. We follow the DFS order and then return to the parent vertex of v, p. In p we do something similar but in a different order : instead of following the DFS from the first discovered child, we follow the DFS order from v and consider the array of children to be circular. Let's exemplify : if [1,2,3,4] was the ordering and you came from 3, them the order will be [3,4,2,1].

This algorithm uses at most 160 movements and scores 78 points. It was harder to think and explain the algorithm then to implement it. You may find the partial solution here.

A smart subtree approach : 100 points

In the final solution, we will also stick to the idea of solving the problem on a tree and reducing a general graph to its spanning tree. However, we will tweak the moving part of our algorithm to be more efficient.

From now on, when we talk about subtrees , think of them as a connected acyclic subgraph rather than a subtree of a rooted tree. Suppose that we have a subtree of exactly 60 vertices . If we run the DFS algorithm on this subtree, we will be able to find X with 120 moves or less for all the vertices of the subtree.

If we could assign for each vertex a subtree of size 60 such that all the bits of X are represented in the subtree, then our problem is solved. Let's focus on finding a way of doing that.

Suppose we have already found the spanning tree and found an arbitrary subtree T of size 60. For all vertices of the subtree, we assign T as its subtree. Then, we will try to assign a subtree to the neighbors of the vertices of the subtree that have not yet been assigned a subtree.

The idea is as follows. Let u be the vertex without an assigned subtree and v its neighbor that has been assigned the subtree T. To find subtree for u, we copy T and remove an arbitrary leaf of the tree that is not v. Then, we connect u to v in the new subtree T* and assign the bit of the removed leaf to u. The image above shows this idea for a smaller subtree : we pick any of the leaves (in this it was the one numbered 6, but it could be 5) and remove it. Then, we connect the new vertex to its neighbor in the subtree an assign the 6th bit to the new vertex.

We must run the routine above until all vertices are assigned a subtree. Because the graph is connected, it will always be possible to assign a subtree to each vertex.

In the decoding part as IOI-chan , we run the DFS idea from our previous algorithm in the subtree of the starting vertex. IOI-chan will make at most 120 moves.

In my final implementation, I opted to use a BFS to generate a spanning tree instead of the DFS. Despite that, the algorithm is exactly the same as the one described above.