I was solving the problem Finding Routers in the practice session of APIO 2025. I intuited (guessed) the following solution.
code
It gives the full 100 points but I have no proof of its correctness. It has an obvious $$$n\log_2{l}$$$ upper bound on the number of use_detector calls. This accounts for the first 3 subtasks. I think this bound can be further improved to $$$2n\log_2(\frac{l}{2n})$$$. However, none of these bounds explain why it can solve subtask 4 within $$$7500$$$ queries.
I found this blog post but the commentor also had no proof of his solution. I also found this solution which caches the queries. I think (not sure) it asks the same queries as my solution. It might be easier to reason about.
Imagine the D&C as a binary tree with some good leaves. In each level, you will either have less than $$$n$$$ nodes. In this case, all nodes can have good children, so you will query all of them. Or you will have more than $$$n$$$ nodes, and obviously, at most $$$n$$$ of them can have good children, so you will query only $$$n$$$ of them.
We also know that a level $$$i$$$ has exactly $$$2^i$$$ nodes. So if we let $$$l = 2^k$$$, the total number of queries is
By letting $l = 2^{16}$, we get $$$Q = 7023$$$ and letting $$$l = 2^{17}$$$, we get $$$Q = 8023$$$, so we know that for $$$l = 10^5$$$, $$$7023 \le Q \le 8023$$$. I don't think finding a closed formula for a non power of two value of $$$l$$$ is trivial, so in these cases it's better to code and see.
Some IOI problems like IOI17 — Prize and IOI15 — Scales are similar in that you need to code your solution to know for sure the number of queries you need.
Thanks! Also, shouldn't $$$l = 2^k - 1$$$ since $$$\sum_{i=0}^{k - 1}{2^i} = 2^k - 1$$$?
Nope, there are $$$l = 2^k$$$ leaves, but we don't query any leaves, that's why the sum is only till $$$k - 1$$$.
I remained skeptical even after seeing MinaRagy06's bounds. Because, a binary tree with $$$10^5$$$ nodes would need $$$17$$$ layers. Make the first $$$16$$$ layers into a complete binary tree. Then, the last layer would have $$$34465$$$ nodes. Since $$$34465 \ge n$$$, the bound on the number of queries when $$$l=10^5$$$ should be similar to the bound when $$$l = 2^{17}$$$.
Finally, I prepared a countercase.
My code used $$$7993$$$ queries on the countercase!
The cache solution used $$$7596$$$ queries.
I am pretty confident that I can hack any solution that is a variation of mine (uses
firstinstead oflast, uses inclusive range, does not usestd::max, etc). So, does someone have a deterministic solution for solving subtask 4 using $$$7500$$$ queries?Ohh.. my bad.
I've checked the model solution from the official IOI 2020 website. After adjusting your generator, it took more than $$$8200$$$ queries, and after reading it, I found that it queries the leaves, taking $$$n$$$ extra queries. So apparently there are no correct solutions to the problem :clown:
Okay, so I've tried to combine the queries caching optimization with my old 96.64 points solution, which uses binary search + square root decomposition, and it got $$$100$$$ points, and I wasn't able to hack it. However, I couldn't find any upper bounds better than $$$8500$$$ (the upper bound before caching queries), but I believe it would be really hard to hack because its behavior is very messy.
Mine used $$$7666$$$ queries.
I used memoization with binary search
My code:
I was also shocked that it passed all tests
can ternary search improve it?
No, because binary search takes $$$\lceil\log_2(l + 1)\rceil = 17$$$ queries but ternary search would take $$$2\lceil\log_3(l + 1)\rceil = 22$$$ queries.
I have found a proof for your solution.
Let's create a binary search tree representing the search on the range $$$[0, l]$$$. Starting from root node, we can observe how many points will not use any query on this level. So, the root node — midpoint of the range will be asked once, for the next points, we have its value in memory, that's why we lose $$$n-1$$$ queries. Then in the second level of the tree, there are two nodes and they both will be asked once, again we lose $$$n-2$$$ queries. And this continues. In total, we use $$$n*log2(l)-(n-1)-(n-2)-(n-4)-...$$$ queries.
I hope, I explained it correctly.))
Can you elaborate? If that is true, I think the problem would be solvable in $$$\approx 4000$$$ queries with the solution from my previous comment.
The function
use_detectorgives the values \begin{equation}0, \ldots, 0, 1, \ldots, 1, \ldots \ldots, (n — 1), \ldots, (n — 1)\end{equation} in the range $$$[0, L]$$$.The binary search code repeatedly divides ranges in half until it knows that the entire range has the same element. Let us construct the final partitions.
Start with all the segments with size 1. \begin{equation}[0], [0], [0], [1], [1], [1], [1], [2], [3], [3], [3], [3], [3]\end{equation} Merge the elements with indexes $$$2k$$$ and $$$2k + 1$$$ if they are the same. \begin{equation}[0, 0], [0], [1], [1, 1], [1], [2], [3, 3], [3, 3], [3]\end{equation} Merge the elements with indexes $$$4k$$$, $$$4k + 1$$$, $$$4k + 2$$$, and $$$4k + 3$$$ if they are the same. \begin{equation}[0, 0], [0], [1], [1, 1], [1], [2], [3, 3, 3, 3], [3]\end{equation} And so on until no more segments can be merged.
Consider the range in the output of
use_detectorwith all its elements equal to $$$v$$$. What is the maximum number of segments it can be split into?If two segments of size $$$s$$$ are next to each other, they will be merged unless they are misalligned (i.e., the first one is offset exactly by $$$s$$$). We greedily set the first element into its own segment of size 1. For it not to be immediately merged with its right neighbour, it must be offset by 1.
For the next element to be in a segment of size 1, it must be the last element in the range. Otherwise, it can be merged with its right neighbour since it is now guaranteed to not be offset by 1 (since the first element was offset by 1). So, it will be in a segment of size 2 and we now assume that it is offset by size 2.
We then repeat this process. As an example, this is the maximal splitting when $$$s = 22$$$. \begin{equation} v], [v, v], [v, v, v, v], [v, v, v, v, v, v, v, v], [v, v, v, v], [v, v], [v \end{equation}
When $$$s = 3 \times 2^k - 2$$$, the maximum number of segments would be $$$2k + 1$$$. So, the upper bound on the number of segments for a range of size $$$s$$$ is $$$2\lceil\log_2(\frac{s + 2}{3})\rceil + 1$$$.
The upper bound on the total number of segments is $$$\sum_{i = 0}^{n - 1}(2\lceil\log_2(\frac{s[i] + 2}{3})\rceil + 1)$$$ where $$$\sum_{i = 0}^{n - 1}{s[i]} = l + 1$$$. This is equal to \begin{equation}2\sum_{i = 0}^{n — 1}(\lceil\log_2(\frac{s[i] + 2}{3})\rceil) + n\end{equation} \begin{equation}\le 2n\log_2(\frac{\sqrt{8}(l + 1)}{3n} + \frac{2\sqrt{8}}{3})\end{equation}
Trivially, the number of queries $$$=$$$ number of segments $$$- 1$$$.
So, the number of queries $$$ \lt 2n\log_2(\frac{\sqrt{8}(l + 1)}{3n} + \frac{2\sqrt{8}}{3})$$$.
Initially, I had only analyzed it roughly and made crude assumptions about $$$l$$$, $$$s$$$ (so no need for ceil in equation), etc. This is a more correct bound. I hope it is strong enough for your algorithm.
Edit: \begin{equation}\lfloor 2n\log_2(\frac{\sqrt{8}(l + 1)}{3n} + \frac{2\sqrt{8}}{3})\rfloor = 13174\end{equation}