In my opinion, all of the problems have a very simple solution and actually require no special data structure at all. To demonstrate the point, I will also use EvErYoNe'S fAvOrItE lAnGuAgE: Pascal.
I will also include some notes, which are not related to the solution at all, but I find them interesting, so I will also include them in.
Obviously, the problem is solvable using simulation. But it is solvable in $$$O(1)$$$ time as well, and I will discuss it.
- Yes, I purposely make the constraint small. Firstly, the simulation solution is straightforward to think of, and I think everyone should be able to do it. But secondly, I wanted to see high-rated people suffering from going too fast :).
- I hope that you like the animation! If you didn't know it yet, I use the library called Manim, created by 3Blue1Brown. He has a lot of great content about math with excellent animation. So if you wanted to see the illustrations in higher quality, or see the illustration of the other input, here is my Jupyter Notebook on Google Colab, that you can run directly and see it. The first example is already rendered but seems like the file is too big, and Google asks for a login first to see it.
- Making the animation is one process, but uploading it is another. Polygon only supported a PNG file with the maximum size of 1 MB, so I need to first compress the GIF, and then convert it to APNG (animated PNG). The process is a little painful tho. Not only do I need the external tool for compression, but I need to reduce the playtime of the animation as well (so the other example besides the first one is faster).
There are a lot of solutions to this problem. The solution I described below might be the simplest in my opinion.
- The game process is actually inspired by Quick sort: the range, picked by Alice, is the sorting range, and the number, picked by Bob, is the pivot.
- Testers really like sorting. Some of the testers demand order for the input, so they need to do the sorting. But Nah, that is totally not required :)
There is not much to note about this problem.
- This is the not planned problem in the problem set.
- All of the solutions that I saw, including the solution by testers and in the comments, use some sort of formulas, which I actually don't understand yet :).
- The colors for the illustration are friendly to color-blind :).
- If you are using a dark theme you will see a small hidden message in the illustration :). You can also see it by just changing the background to black (using F12 in the browser and changing the CSS).