J. Just So You Know

**Definitions** Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers. Let $ \mathcal{B} $ be the set of all contiguous subsequences (intervals) of $ A $, i.e., $$ \mathcal{B} = \{ A[i:j] \mid 1 \leq i \leq j \leq n \}, \quad \text{where } A[i:j] = (a_i, a_{i+1}, \dots, a_j). $$ Let $ |\mathcal{B}| = \binom{n+1}{2} = \frac{n(n+1)}{2} $. Each element of $ \mathcal{B} $ is selected uniformly at random as the hidden subsequence $ B $. A *conjecture* is a claim of the form "Is $ B = A[i:j] $?" for some $ i \leq j $. Matthew uses an optimal adaptive strategy to identify $ B $ with minimal expected number of conjectures. **Constraints** 1. $ 1 \leq T \leq 1000 $ 2. $ 1 \leq n \leq 10^6 $ 3. $ 0 \leq a_i < 100 $ for all $ i $ 4. Total sum of $ n $ across test cases $ \leq 10^7 $ **Objective** Compute the minimal expected number of conjectures required to identify $ B $, under an optimal strategy, over the uniform distribution over $ \mathcal{B} $. Output the result as an irreducible fraction $ \frac{p}{q} $, or $ p $ if $ q = 1 $. **Key Insight** The problem reduces to computing the **expected depth of a leaf in the optimal binary identification tree** for the set $ \mathcal{B} $, where each leaf corresponds to a unique contiguous subsequence, and internal nodes correspond to queries that partition the set of candidates. By information theory and optimality of Huffman coding for uniform distributions over distinct items, the minimal expected number of queries equals the **average depth** of a leaf in a **complete binary tree** with $ |\mathcal{B}| $ leaves — **only if all subsequences are distinct**. But: **Subsequences may not be distinct**. Two different intervals $ A[i:j] $ and $ A[k:\ell] $ may be identical as sequences. Thus, we must group identical subsequences: let $ \mathcal{S} $ be the set of *distinct* contiguous subsequences of $ A $, and for each $ s \in \mathcal{S} $, let $ f(s) $ be the number of intervals in $ A $ that equal $ s $. Then the probability of selecting a subsequence equal to $ s $ is $ \frac{f(s)}{\binom{n+1}{2}} $. The minimal expected number of conjectures is the **entropy of the distribution** over distinct subsequences, **only if** we can design a decision tree that exploits the structure — but in the worst case, without structure, the optimal strategy is to treat each *occurrence* as a distinct outcome? No. Actually, since Matthew must identify the *exact interval* (not just the content), even if two intervals have the same content, they are different outcomes. So the sample space has $ \binom{n+1}{2} $ equally likely outcomes (each interval is a distinct candidate), regardless of content. Thus: **Each contiguous subsequence is a distinct hypothesis**, even if content repeats. Matthew must identify *which interval* was chosen, not just its content. Therefore, there are $ N = \frac{n(n+1)}{2} $ equally likely hypotheses. The minimal expected number of yes/no queries to identify one out of $ N $ equally likely items is the **expected depth of a leaf in a balanced binary decision tree**, which is minimized by a Huffman tree — but for uniform distribution, the optimal is a complete binary tree. The minimal expected number of queries is: $$ \mathbb{E} = \frac{ \sum_{k=1}^{N} \lceil \log_2 k \rceil }{N} $$ No — that’s incorrect. Actually: for $ N $ equally likely items, the minimal expected number of yes/no queries is the **average depth** of the leaves in a **complete binary tree** with $ N $ leaves. This is a classic problem: the minimal expected number of comparisons to identify one of $ N $ items is: $$ \mathbb{E} = \frac{ \sum_{i=1}^{N} d_i }{N} $$ where $ d_i $ is the depth of leaf $ i $ in a **minimum-height binary tree** with $ N $ leaves — which is the same as the **average depth of a leaf in a complete binary tree**. This value is known to be: Let $ h = \lfloor \log_2 N \rfloor $, and let $ r = N - 2^h $. Then: - $ 2^h - r $ leaves are at depth $ h $ - $ r $ leaves are at depth $ h+1 $ So total sum of depths = $ (2^h - r) \cdot h + r \cdot (h+1) = 2^h h + r $ Thus: $$ \mathbb{E} = \frac{2^h h + r}{N}, \quad \text{where } h = \lfloor \log_2 N \rfloor, \; r = N - 2^h $$ **Therefore, the answer for a test case is:** Let $ N = \frac{n(n+1)}{2} $ Let $ h = \lfloor \log_2 N \rfloor $ Let $ r = N - 2^h $ Let $ \text{sum\_depth} = h \cdot 2^h + r $ Then expected value = $ \frac{\text{sum\_depth}}{N} $ Reduce the fraction $ \frac{\text{sum\_depth}}{N} $ to lowest terms. **Note**: The values of $ A $ are irrelevant! Because Matthew must identify the *interval*, not the content. Even if two intervals have the same content, they are different outcomes. So the problem reduces to: > Uniformly random interval among $ \binom{n+1}{2} $, find minimal expected number of yes/no queries to identify it. Thus, **the sequence $ A $ does not affect the answer**. **Final Formal Statement** **Definitions** Let $ n \in \mathbb{Z}^+ $. Let $ N = \binom{n+1}{2} = \frac{n(n+1)}{2} $. Let $ h = \lfloor \log_2 N \rfloor $, $ r = N - 2^h $. Let $ D = h \cdot 2^h + r $. **Objective** Compute the irreducible fraction $ \frac{D}{N} $. **Constraints** As given. **Note**: The sequence $ A $ is irrelevant to the computation.