<center>↵
<table class="tex-tabular bordertable"↵
style="border-left: none; border-right: none; border-top: 1px solid; border-bottom: 1px solid; border-collapse: collapse;">↵
<tbody>↵
<tr>↵
<td class="tex-tabular-text-align-center"↵
style="border-left: none; border-right: none; border-top: none; border-bottom: none;">↵
<span class="tex-font-size-small">↵
<span class="tex-font-style-it">↵
<a href="https://www.youtube.com/watch?v=HCYKLnT0UNU">Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii</a>↵
</span>↵
</span>↵
</td>↵
</tr>↵
</tbody>↵
</table>↵
</center>↵
↵
[problem:2207A]**UPD 1:** added hints, problem credits, more specific acknowledgements and some remarks. Implementations are on the way, sorry for making y'all wait!↵
↵
[problem:2207A]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
If there are two consecutive zeroes, can you ever change either of them?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207A]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!↵
">↵
[likes:1,option1] Awesome!↵
↵
[likes:1,option2] Okay...↵
↵
[likes:1,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207B]↵
↵
<spoiler summary="Solution">↵
We credit [user:awesomeguy856,2026-03-08] for the analysis of this problem.↵
[tutorial:2207B]↵
</spoiler>↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
(Cool) analysis: [user:awesomeguy856,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Which animatronic should you choose with your flashlight?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How many animatronics are worth incrementing when there are $k$ flashes remaining?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Write an expression for the ending danger level in terms of the night length and the danger levels of the animatronics that get flashed.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207B]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:2,option1] Awesome!↵
↵
[likes:2,option2] Okay...↵
↵
[likes:2,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207C]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Solve the case of one drain first! You should aim for $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you pick two drains, what's the shape of their overlap?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Brute force.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207C]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:3,option1] Awesome!↵
↵
[likes:3,option2] Okay...↵
↵
[likes:3,option3] I would have rather watched cricket world cup↵
↵
↵
[problem:2207D]</spoiler>↵
↵
<spoiler summary="Remark 1">↵
There are tons of ways to do this problem, and chances are you found a different one than most other contestants! This problem is solvable in subquadratic time however, can you do it?↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
Also, the diagrams in the problem, as well as the ones in all editorials and other problems, are completely drawn natively in tikzpictures. Did you know you can cram 3-D plots onto 2-D to make textured filling?↵
</spoiler>↵
↵
[problem:2207D]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Let's first think about path graphs. For some $k$, what are the $n$ for which an $n$-path wins for Cyndaquil?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Between every pair of Cyndaquil-winning nodes a distance of $k$ apart, all the nodes on the path between them also win. How can we find these efficiently?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Why did we ask for only vertex $v$, and not for all nodes?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Tree DP.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207D]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:4,option1] Awesome!↵
↵
[likes:4,option2] Okay...↵
↵
[likes:4,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207E1]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Write some bounds for the $a_i$. What's the biggest/smallest each one can be?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to pick only numbers that aren't in the $a_i$, and $+\infty$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207E1]↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:5,option1] Awesome!↵
↵
[likes:5,option2] Okay...↵
↵
[likes:5,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207E2]↵
↵
Same credits as E1.↵
↵
<spoiler summary="Hint 1">↵
Read E1's hints first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
There are actually a very well-constrained set of working solutions. How many times do we pick each number not present in the $a_i$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207E2]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:6,option1] Awesome!↵
↵
[likes:6,option2] Okay...↵
↵
[likes:6,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207F]↵
↵
Author: [user:IceSerpent,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Think about how you'd play in the case of only one color. Once you have that, how would you do two colors?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Each color has some sequence of clues that will get them to be played correctly. How do we coalesce them into one string of clues?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Some rank clues must be given for all cards to be played. If two consecutive forced rank clues are for ranks $a, b$, is it ever optimal to only rank clue some of the ones between $a, b$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
There is an $O(n^2)$ dp. How can we speed it up?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207F]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:7,option1] Awesome!↵
↵
[likes:7,option2] Okay...↵
↵
[likes:7,option3] I would have rather watched cricket world cup↵
↵
↵
[problem:2207G]</spoiler>↵
↵
<spoiler summary="Remark 1">↵
As suggested by the editorial, this problem was originally about Squid Game! Until we made the round about the 2010s, that is.↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
There's actually a way to do this in $O(nm \sqrt{nm})$ or faster with flows! Can you represent the problem as a flow or matching instance?↵
</spoiler>↵
↵
[problem:2207G]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:awang11,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Use Pigeonhole to first solve for the case of no needy cells.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How can you adjust your solution when there are needy cells?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The graph is planar. Recall the Euler characteristic formula.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207G]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:8,option1] Awesome!↵
↵
[likes:8,option2] Okay...↵
↵
[likes:8,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
↵
<spoiler summary="Remark / Conjecture">↵
It is open to us whether the following cheese is actually provably correct:↵
↵
- First attempt to fill in the cells (blind to whether they are special or not) in reading order, adding if it doesn't form a cycle.↵
↵
- Second attempt to fill in the cells, but with special cells first, in reading order, adding if it doesn't form a cycle.↵
↵
We conjecture that one of the two always passes.↵
</spoiler>↵
↵
[problem:2207H1]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Use 0-1 sorting to make the structure a little simpler. What's a concise way to visualize a min max function?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The min max function is a tree that alternates min/max across depths. Can you determine the type of the top operation?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
You will need to try a good number of schemes, but try to find a point where you can split $f = \min(g, h)$ or similar. Then, divide and conquer will win.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H1]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:9,option1] Awesome!↵
↵
[likes:9,option2] Okay...↵
↵
[likes:9,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207H2]↵
↵
Same credits as H1, main solution due to [user:244mhq,2026-03-09].↵
↵
<spoiler summary="Hint 1">↵
Read the H1 hints.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Go for $O(n \log n)$; how can we optimize the previous approach?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Determine the top node in $O(\log n)$ time.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Scan for your split point from both ends simultaneously.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H2]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:10,option1] Awesome!↵
↵
[likes:10,option2] Okay...↵
↵
[likes:10,option3] I would have rather watched cricket world cup↵
↵
↵
[problem:2207H3]</spoiler>↵
↵
<spoiler summary="Remark">↵
The music choice across H1, H2, H3 actually follows the level of the final castle in World 8 of New Super Mario Bros Wii.↵
</spoiler>↵
↵
[problem:2207H3]↵
↵
Same credits as H1, main solution inspired by [user:IceSerpent,2026-03-09] and [user:awesomeguy856,2026-03-09].↵
↵
<spoiler summary="Hint 1">↵
Read H1 and H2 first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What is $f(1, \dots, n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $t = f(1, \dots, n)$, then $x_t$ is the leaf at an alternating path from root (max goes right, min goes left.)↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
What is $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$? How does it relate to the tree structure of $f(x_1, \dots, x_n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
You know the number of variables in each child of $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$ and $f(-\infty, \dots, -\infty, x_t, \dots, x_n)$. Can you use these children to assemble $f(x_1, \dots, x_n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
Work from the inside (two nearest pieces to $x_t$) to the outside with two pointers. How many queries do we use? The recurrence may look quite terrifying, but...↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H3]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:11,option1] Awesome!↵
↵
[likes:11,option2] Okay...↵
↵
[likes:11,option3] I would have rather watched cricket world cup↵
↵
↵
We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless!</spoiler>↵
↵
<spoiler summary="Remark 1">↵
The solution due to [user:awesomeguy856,2026-03-09] and incidentally the one in contest found by [user:ecnerwala,2026-03-09] actually uses only $2n$ queries!↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
A naive entropy bound gives a lower bound of $n / \log n$ queries; can we push this to linear so our upper bound of $O(n)$ queries becomes asymptotically tight?↵
</spoiler>↵
↵
We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless! ↵
↵
Special thanks to [user:Hori,2026-03-09], [user:nik_exists,2026-03-09], [user:awesomeguy856,2026-03-09], [user:shcal,2026-03-09] for their assistance with problems F through H3. We also acknowledge [user:Amazed,2026-03-09], [user:chromate00,2026-03-09], [user:defnotmee,2026-03-09], [user:Noobish_Monk,2026-03-09], [user:awoo,2026-03-09], [user:misteg168,2026-03-09], [user:cduckling,2026-03-09] for sticking with us in copy-editing and improving statements up until the contest. Once again, a huge thanks to [user:flummoxedfeline,2026-03-09] for making our round look beautiful. ↵
Without them this round wouldn't be complete.↵
↵
Implementations will be added soon.↵
↵
<center>↵
<img width="25%" src="/predownloaded/94/6e/946e024636b88c0e9c5da0b5cba4286bd405add7.jpg">↵
</center>
<table class="tex-tabular bordertable"↵
style="border-left: none; border-right: none; border-top: 1px solid; border-bottom: 1px solid; border-collapse: collapse;">↵
<tbody>↵
<tr>↵
<td class="tex-tabular-text-align-center"↵
style="border-left: none; border-right: none; border-top: none; border-bottom: none;">↵
<span class="tex-font-size-small">↵
<span class="tex-font-style-it">↵
<a href="https://www.youtube.com/watch?v=HCYKLnT0UNU">Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii</a>↵
</span>↵
</span>↵
</td>↵
</tr>↵
</tbody>↵
</table>↵
</center>↵
↵
↵
[problem:2207A]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
If there are two consecutive zeroes, can you ever change either of them?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207A]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!
[likes:1,option1] Awesome!↵
↵
[likes:1,option2] Okay...↵
↵
[likes:1,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207B]↵
↵
We credit [user:awesomeguy856,2026-03-08] for the analysis of this problem.↵
[tutorial:2207B]↵
</spoiler>↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
(Cool) analysis: [user:awesomeguy856,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Which animatronic should you choose with your flashlight?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How many animatronics are worth incrementing when there are $k$ flashes remaining?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Write an expression for the ending danger level in terms of the night length and the danger levels of the animatronics that get flashed.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207B]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:2,option1] Awesome!↵
↵
[likes:2,option2] Okay...↵
↵
[likes:2,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207C]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Solve the case of one drain first! You should aim for $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you pick two drains, what's the shape of their overlap?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Brute force.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207C]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:3,option1] Awesome!↵
↵
[likes:3,option2] Okay...↵
↵
[likes:3,option3] I would have rather watched cricket world cup↵
↵
[problem:2207D]
↵
<spoiler summary="Remark 1">↵
There are tons of ways to do this problem, and chances are you found a different one than most other contestants! This problem is solvable in subquadratic time however, can you do it?↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
Also, the diagrams in the problem, as well as the ones in all editorials and other problems, are completely drawn natively in tikzpictures. Did you know you can cram 3-D plots onto 2-D to make textured filling?↵
</spoiler>↵
↵
[problem:2207D]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Let's first think about path graphs. For some $k$, what are the $n$ for which an $n$-path wins for Cyndaquil?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Between every pair of Cyndaquil-winning nodes a distance of $k$ apart, all the nodes on the path between them also win. How can we find these efficiently?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Why did we ask for only vertex $v$, and not for all nodes?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Tree DP.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207D]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:4,option1] Awesome!↵
↵
[likes:4,option2] Okay...↵
↵
[likes:4,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207E1]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Write some bounds for the $a_i$. What's the biggest/smallest each one can be?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to pick only numbers that aren't in the $a_i$, and $+\infty$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207E1]↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:5,option1] Awesome!↵
↵
[likes:5,option2] Okay...↵
↵
[likes:5,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207E2]↵
↵
Same credits as E1.↵
↵
<spoiler summary="Hint 1">↵
Read E1's hints first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
There are actually a very well-constrained set of working solutions. How many times do we pick each number not present in the $a_i$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207E2]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:6,option1] Awesome!↵
↵
[likes:6,option2] Okay...↵
↵
[likes:6,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207F]↵
↵
Author: [user:IceSerpent,2026-03-09]↵
↵
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Think about how you'd play in the case of only one color. Once you have that, how would you do two colors?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Each color has some sequence of clues that will get them to be played correctly. How do we coalesce them into one string of clues?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Some rank clues must be given for all cards to be played. If two consecutive forced rank clues are for ranks $a, b$, is it ever optimal to only rank clue some of the ones between $a, b$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
There is an $O(n^2)$ dp. How can we speed it up?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207F]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:7,option1] Awesome!↵
↵
[likes:7,option2] Okay...↵
↵
[likes:7,option3] I would have rather watched cricket world cup↵
↵
[problem:2207G]
↵
<spoiler summary="Remark 1">↵
As suggested by the editorial, this problem was originally about Squid Game! Until we made the round about the 2010s, that is.↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
There's actually a way to do this in $O(nm \sqrt{nm})$ or faster with flows! Can you represent the problem as a flow or matching instance?↵
</spoiler>↵
↵
[problem:2207G]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:awang11,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Use Pigeonhole to first solve for the case of no needy cells.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How can you adjust your solution when there are needy cells?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The graph is planar. Recall the Euler characteristic formula.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207G]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:8,option1] Awesome!↵
↵
[likes:8,option2] Okay...↵
↵
[likes:8,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
↵
<spoiler summary="Remark / Conjecture">↵
It is open to us whether the following cheese is actually provably correct:↵
↵
- First attempt to fill in the cells (blind to whether they are special or not) in reading order, adding if it doesn't form a cycle.↵
↵
- Second attempt to fill in the cells, but with special cells first, in reading order, adding if it doesn't form a cycle.↵
↵
We conjecture that one of the two always passes.↵
</spoiler>↵
↵
[problem:2207H1]↵
↵
Author: [user:awang11,2026-03-09]↵
↵
Preparer: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
Analysis: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]↵
↵
<spoiler summary="Hint 1">↵
Use 0-1 sorting to make the structure a little simpler. What's a concise way to visualize a min max function?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The min max function is a tree that alternates min/max across depths. Can you determine the type of the top operation?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
You will need to try a good number of schemes, but try to find a point where you can split $f = \min(g, h)$ or similar. Then, divide and conquer will win.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H1]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:9,option1] Awesome!↵
↵
[likes:9,option2] Okay...↵
↵
[likes:9,option3] I would have rather watched cricket world cup↵
</spoiler>↵
↵
[problem:2207H2]↵
↵
Same credits as H1, main solution due to [user:244mhq,2026-03-09].↵
↵
<spoiler summary="Hint 1">↵
Read the H1 hints.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Go for $O(n \log n)$; how can we optimize the previous approach?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Determine the top node in $O(\log n)$ time.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Scan for your split point from both ends simultaneously.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H2]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:10,option1] Awesome!↵
↵
[likes:10,option2] Okay...↵
↵
[likes:10,option3] I would have rather watched cricket world cup↵
↵
[problem:2207H3]
↵
<spoiler summary="Remark">↵
The music choice across H1, H2, H3 actually follows the level of the final castle in World 8 of New Super Mario Bros Wii.↵
</spoiler>↵
↵
[problem:2207H3]↵
↵
Same credits as H1, main solution inspired by [user:IceSerpent,2026-03-09] and [user:awesomeguy856,2026-03-09].↵
↵
<spoiler summary="Hint 1">↵
Read H1 and H2 first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What is $f(1, \dots, n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $t = f(1, \dots, n)$, then $x_t$ is the leaf at an alternating path from root (max goes right, min goes left.)↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
What is $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$? How does it relate to the tree structure of $f(x_1, \dots, x_n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
You know the number of variables in each child of $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$ and $f(-\infty, \dots, -\infty, x_t, \dots, x_n)$. Can you use these children to assemble $f(x_1, \dots, x_n)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
Work from the inside (two nearest pieces to $x_t$) to the outside with two pointers. How many queries do we use? The recurrence may look quite terrifying, but...↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2207H3]↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
[likes:11,option1] Awesome!↵
↵
[likes:11,option2] Okay...↵
↵
[likes:11,option3] I would have rather watched cricket world cup↵
↵
We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless!
↵
<spoiler summary="Remark 1">↵
The solution due to [user:awesomeguy856,2026-03-09] and incidentally the one in contest found by [user:ecnerwala,2026-03-09] actually uses only $2n$ queries!↵
</spoiler>↵
↵
<spoiler summary="Remark 2">↵
A naive entropy bound gives a lower bound of $n / \log n$ queries; can we push this to linear so our upper bound of $O(n)$ queries becomes asymptotically tight?↵
</spoiler>↵
↵
We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless! ↵
↵
Special thanks to [user:Hori,2026-03-09], [user:nik_exists,2026-03-09], [user:awesomeguy856,2026-03-09], [user:shcal,2026-03-09] for their assistance with problems F through H3. We also acknowledge [user:Amazed,2026-03-09], [user:chromate00,2026-03-09], [user:defnotmee,2026-03-09], [user:Noobish_Monk,2026-03-09], [user:awoo,2026-03-09], [user:misteg168,2026-03-09], [user:cduckling,2026-03-09] for sticking with us in copy-editing and improving statements up until the contest. Once again, a huge thanks to [user:flummoxedfeline,2026-03-09] for making our round look beautiful. ↵
Without them this round wouldn't be complete.↵
↵
Implementations will be added soon.↵
↵
<center>↵
<img width="25%" src="/predownloaded/94/6e/946e024636b88c0e9c5da0b5cba4286bd405add7.jpg">↵
</center>
