Let $$$B$$$ be a constant. First, similarly to the 47-point solution, we construct a tree consisting of $$$B+1$$$ leaves and all of their ancestors.

From this point, our goal is to determine the DFS order of this tree using $$$t$$$ values. Once we can do this, we can add the remaining $$$B+1-t$$$ leaves in the same manner.

This goal can be achieved if, for every leaf, we can detect when that leaf is reached by ensuring that the sequence of values along the path from the root to that leaf is distinct from the corresponding sequence for every other vertex.

First, the following observations hold:

• For a vertex that has a non-leaf child, there is no need to visit the leaves attached directly to that vertex.
• For a vertex that has two or more leaves as children, it is sufficient to visit just one of those leaves.

After removing and reorganizing the leaves in this way, it is sufficient to make the sequences obtained by looking up to two vertices ahead distinct for every vertex. If the current number of leaves is $$$m$$$, we can achieve this with $$$t=\lceil\sqrt{m}\rceil$$$.

Taking $$$B=22$$$, we can achieve $$$C=38$$$.

Consider repeatedly placing balls of value $$$m-1$$$ on leaf $$$m-1$$$ until you reach the leaf, then place balls of value $$$m-2$$$ on leaf $$$m-2$$$, and follow this pattern all the way to leaf $$$0$$$. What information can we get from this query?

Notice that all the nodes in the tree have a ball, the subgraph consisting of balls of the same value will always be an ancestor-descendant path, and each node's value is the greater than or equal to all the values in its subtree. Combining these observations, we can reconstruct the entire tree.

We iterate through the array given by the query from left to right. At any point, we maintain the current structure of the tree (which is always a connected component containing the root), and the current node.

If the current value $$$x$$$ has never appeared before, we repeatedly move the current node to its parent until its value is greater than $$$x$$$. Then we add a new node as a child of the current node and set the current node to the new node.

Otherwise, we can simply find the last node of value $$$x$$$ that has been added, and add a new node as a child of it, then set the current node to the new node. This uses a maximum ball value of $$$m-1$$$ and $$$1$$$ query, giving $$$47$$$ points.

What if we use the same querying strategy as the previous solution, but we only choose a subset of leaves?

If we do the query in hint 2, will get the structure of the virtual tree containing this subset of leaves. How can we combine the structures of multiple virtual trees to get the full tree?

If we have the depth of each leaf, and the depth of $$$\mathrm{lca}(x,y)$$$ for all pairs of leaves $$$(x, y)$$$, we can determine the structure of the tree (we can add leaves to the tree one by one, and find the leaf who has the deepest lowest common ancestor with the new leaf before we add it. Then, we can simply add a simple path from this lowest common ancestor to the new leaf, since we also know the depth of the leaves). We can see that we can get the depth of $$$\mathrm{lca}(x,y)$$$ if both $$$x$$$ and $$$y$$$ appear in the same query, so we just need to construct a set of subsets of leaves, such that any two leaves appear in the same subset at least once.

We split the leaves into $$$8$$$ groups, each containing at most $$$25$$$ leaves. We query each pair of groups, requiring $$$\binom82 = 28$$$ queries using maximum ball value of at most $$$49$$$. This gives $$$C=77$$$, for a score of $$$71.6$$$ points.

We split the leaves into $$$21$$$ groups ($$$20$$$ should be better, but for some reason my greedy algorithm mentioned later gets a better solution for $$$21$$$), each containing at most $$$10$$$ leaves. In each query, we include $$$5$$$ of these groups. We need each pair of groups to be included in the same query at least once. Using a greedy algorithm that always picks the subset that has the maximum number of unvisited pairs of groups, we have a strategy that uses $$$21$$$ queries with maximum ball value $$$49$$$. This gives a solution with $$$C=70$$$ for $$$74$$$ points.

After the contest, I found that my solution was identical to jer033's solution, except he split the leaves into $$$25$$$ groups of $$$8$$$, also querying $$$5$$$ groups at a time. Constructing the queries by hand, a solution using $$$30$$$ queries and maximum ball value $$$39$$$ can be achieved, giving $$$75$$$ points.

Since each node has degree at most $$$K$$$, this motivates us to use cliques of size $$$K+1$$$. It can be shown that the minimum number of cliques needed is $$$2K$$$ (for $$$K \gt 1$$$). One way to achieve this is two split the types into two groups of size $$$K$$$, and to build a clique for each type containing that type and all types in the opposite group. This uses $$$2K(K+1)$$$ nodes and fully solves the subtasks for $$$K\leq 4$$$.

We first solve for even $$$K$$$. Split the types into $$$4$$$ groups.

There are $$$3$$$ ways to cyclically permute these groups up to reflection and rotation. For each of these $$$3$$$ permutations, add a subgraph of $$$2K$$$ nodes of different types where each node is connected to all nodes in both adjacent groups adjacent to its own group. This covers all triplets of types from three different groups. Additionally, for each of the $$$6$$$ pairs of groups, build a clique of size $$$K$$$ containing all nodes in both groups. This covers all triplets of types that span either one or two groups.

For odd $$$K$$$, we can build a the graph for $$$K-1$$$ and then add nodes of types $$$2K-1$$$ and $$$2K-2$$$ to each of the $$$6$$$ cliques.

This solution uses $$$12K$$$ nodes and fully solves all subtasks where $$$K\geq 6$$$.

Combining the two solutions above fully solves all subtasks except $$$K=5$$$. For this subtask, a specialized construction is needed. One possible construction is this:

Create $$$5$$$ groups of $$$10$$$ nodes of types $$$0\ldots9$$$. In group $$$1$$$, connect each node $$$i$$$ to nodes $$$i+2,i+3,i+5\pmod{10}$$$. In group $$$2$$$, connect each node $$$i$$$ to nodes $$$i+1,i+4,i+5\pmod{10}$$$. In group $$$3$$$, connect each node $$$i$$$ to nodes $$$i+2,i+4\pmod{10}$$$ and also $$$i+1$$$ if $$$i$$$ is even. In group $$$4$$$, connect each node $$$i$$$ to nodes $$$i+2,i+3\pmod{10}$$$ and also $$$i+1$$$ if $$$i$$$ is odd. In group $$$2$$$, connect each node $$$i$$$ to nodes $$$i+3,i+4\pmod{10}$$$ and also $$$i+1$$$ if $$$i$$$ is even.

• It doesn't require the permutation to be the same between steps.
• It doesn't require the teachers to know the number of steps (but they need to know the number of their own step, and the headmaster needs to know the number of steps).

It's rather messy in the implementation and took a while to get right, but the concepts are not too difficult. Each student holds one of the following records in their array (where r is a round number and j is a student number):

• HAND(r, j)
• INVERT(r)
• SHORT_NOHAND(j)
• SHORT_ROUND(r)
• EMPTY

These can be encoded as [r, j], [63, r], [j], [r, 63] and [] respectively. It doesn't matter which student holds which records; the records are just a set of information.

The information about which hands were raised in round r can be encoded in one of several ways: 1. HAND(r, j) for every j that raised their hand (must be at least one) 2. HAND(r, j) for every j that did not raise their hand and had not previously raised their hand (must be at least one), together with an INVERT(r) record. 3. SHORT_NOHAND(j) for every j that did not raise their hand and had not previously raised their hand (must be at least one), together with a SHORT_ROUND(r) record (there can be at most one such record). 4. As for (3), but the SHORT_ROUND(r) record is absent if r was the most recent round. 5. If no student raised their hand but there are still students have never raised their hands, (a) an INVERT(r) record with no HAND(r, j) records; or (b) no records at all. 6. No records at all for the round where all remaining students raised their hand, or where no students raised their hand.

Some care is needed to distinguish 5(b) from 6. If there are still hands to raise, case 6 applies only if there are no records for any later rounds.

Now we can consider how to pick one of these schemes for a given round. Let U be the set of students whose hand has not yet been raised (and are not raised in the current round). The invariant we'll maintain is that the number of records, excluding those for case 5a, is less than or equal to the number of hands previously raised. If we need to add any records for the current round, then we can overwrite a previous case 5a INVERT. Thus, there are always at least |U| slots we can write to. A further invariant is that if there are SHORT_NOHAND records but no SHORT_ROUND record, there are at least |U|+1 slots we can write to.

• If all hands have been raised in previous rounds, do nothing.
• Add a SHORT_ROUND record if there isn't one but there are SHORT_NOHAND records.
• If |U| = 0, do nothing further.
• Otherwise, if |T| = 0, then |U| > 0 so there is a slot to add an INVERT (5a).
• Otherwise, if |T| <= |U|, we can just add HAND(r, j) records for j in T.
• Otherwise, if there is space we can add HAND(r, j) records for j in U plus an INVERT(r) record.
• Otherwise, if there is insufficient space, add SHORT_HAND(j) records for all j in U. But we cannot do this if there is a SHORT_ROUND record for a previous round. In such a case, we can replace it with an INVERT record for that round, and the old SHORT_HAND records with HAND records. This works because the only way the space can be this tight is if all the interesting (i.e. not EMPTY or INVERT (5a)) records are held by students who did't raise their hand, and hence they can be rewritten. Because |T| > |U|, there will definitely be space next round to add the SHORT_ROUND record.