The problem difficulty of JOI Open Contests are similar to IOI, because one of the objectives of this contest should be to practice for IOI 2025.

For this year, judging from the standings, Bubble Sort Machine was the easiest problem with difficulty like upper silver medalists in IOI (CF 2500-level?), and Lottery have difficulty like average gold medalists in IOI (CF 3000-level?). Telepathy turned out to be very difficult, and only two legendary participants fully solved it.

However, getting some partial points can be much easier than getting 100 points, so I expect that there's something to do with enjoyable difficulty zone for wide range of ratings :)

My solution: first find the centroid of the tree to use as a shared reference point, and from now on, the two people should move towards the centroid(s) when possible. Now we can get some points by using the following strategy: A moves up the tree a distance of 1 (stopping at the centroid), B moves up 2, A moves up 4, and with any geometric increase in the distances moved we will get within a constant factor of the initial distance of the two people, though not the $$$6d$$$ required for full points.

To get full points we need to leverage the fact that both people can move together in opposite directions, though we should be careful to not have them miss each other. We can revise the strategy a bit to the following: pick a sequence $$$a_0, a_1, a_2, \dots$$$ of numbers increasing geometrically.

We cycle the turns:

• A up $$$(a_i - a_{i-1})$$$ times

• A down and B up $$$a_i$$$ times

• B up $$$(a_{i+1} - a_{i})$$$ times

• A up and B down $$$a_{i+1}$$$ times, and so on

Also we should be careful that they don't pass each other on an edge, this can be resolved by using the first move to move them both to even depth when rooted at the centroid(s) and picking all $$$a_i$$$ to be even so that they are always at the same parity distance centroid.

The worst case is when the two people start directly above each other at a distance of $$$a_{i} + 1$$$ for some $$$i$$$. If we pick $$$a_i$$$ to increase with a ratio of $$$1 + \sqrt{\frac{2}{3}}$$$ this allows us to get within a factor of $$$3 + \sqrt{6}$$$ of $$$d$$$ asymptotically.

The official editorial is now published :)

I believe that any solution which uses $$$O(d)$$$ turns uses some exponential zig-zag movements. It should be the easiest to consider the path graph case; let $$$x = (\text{Bruno's position}) - (\text{Aitana's position})$$$. Then, moving $$$x$$$ like (below is the change of $$$x$$$):

will reach $x = 0$ in less than $$$9d$$$ turns (which is possible when Aitana stays and only Bruno moves). We can improve this by noticing that $$$x$$$ can be increased/decreased by $$$2$$$ in one turn. However, to avoid "jumping" the $$$x = 0$$$, we let increase/decrease by $$$1$$$ for the first visit. The movement will be like ($$$\Rightarrow$$$ means increase/decrease $$$x$$$ by $$$2$$$ per turn):

and it will reach $x = 0$ in less than $$$6d$$$ turns, giving the full score in Subtask 2.

The editorial solution for general case have some similar points to ksun48's solution, which set the meeting points to centers of the tree. The tree case is actually harder than path graph case, so to make things work, we ensure to pass even numbers when going in positive direction, and to pass odd numbers when going in negative direction (when changing $$$x$$$ by $$$2$$$). However, when the exponent is set to $$$2$$$ as above, this requires $$$7.5d$$$ turns unlike the path graph case. Instead we set the exponent to $$$1.685$$$ and achieves $$$5.99d$$$ turns.