Solution Sketches for M(IT)^2

M(IT)^2 2024 Spring Invitational - Finals

Two Tokens

Consider the set $V'$ of all vertices in $G = (V, E)$ that can be printed. Then for any $u \in {V \setminus V'}$, either edges $(u, v)$ exist for all $v \in V'$, or edges $(u, v)$ do not exist for all $v \in V'$.

This is similar to the problem of counting labeled undirected connected graphs.

Let $f(n)$ be the number of artistic graphs on $n$ vertices. The formula is

$$f(n) = 2 ^ {n(n - 1) / 2 - 1} - \sum_{i = 2}^{n - 1} \binom{n - 2}{i - 2} f(i) 2 ^ {(n - i + 1)(n - i) / 2}.$$

M(IT)^2 2025 Spring Invitational - Finals

M(IT)^2 2026 Spring Invitational - Finals

Sell in Pairs

A solution different from the official one.

Since each query can be answered in $\mathcal{O}(n)$, we may write the answer in the form

$$a x_i + b y_i,$$

where $a$ and $b$ are coefficients determined by the query.

Define the following pairs $(x, y)$ as key pairs:

$$\operatorname{KP} \coloneqq \{(1, 1)\} \cup \{(k, k + 2) : k \in [0, n] \cap \mathbb{Z}\} \cup \{(k + 1, k) : k \in [0, n] \cap \mathbb{Z}\}.$$

It can be shown that every pair is dominated by one of these key pairs, and the number of distinct pairs $(a, b)$ seems to be only $\mathcal{O}(\sqrt n)$.

I don’t have a clean proof of this observation yet, but it matches the behavior of the accepted submission, and the problem author also believes it is correct.

79brue: I actually believe that approach is correct. We have some insights in why that’s correct but did not fully formalize the proof so didn’t write it in the editorial.