I have added this year's Spain Olympiad in Informatics to the gym.
Contest facts:
- Two 5-tasks contests with OI scoring (subtasks).
- Statements in English and Spanish.
- Problems are not ordered by difficulty.
- Problem authors: FelixMP, Sadito10, BlancaHM.
- Difficulty of fully solving problems should be like a Div2 round, perhaps a bit easier in general.
- The easier problems may be a bit more based on implementation and common techniques (compared to a CF round). But the harder problems require observations and should be interesting to more advanced contestants too.
Enjoy!
Auto comment: topic has been updated by FelixMP (previous revision, new revision, compare).
Thank you!
How to solve estatuas?
Here are some hints for one solution (there are multiple possible approaches)
If there exists a solution, then there exists one in which the lengths of the blocks of consecutive statues in the same side form a strictly increasing sequence.
Assuming that the lengths of blocks (consecutive statues at the same side) make an increasing sequence, if you make some greedy choices like "don't go into the next block of statues until you strictly need to" and "once you've entered a new block don't go back to previous ones", then the statues and the path are uniquely determined. But you actually need to go back to previous blocks because you need to go back to the entrance, so this doesn't directly work yet.
You can start from the end simulating the path "backwards" by inverting the characters of the string. So you can trace the path from the beginning and from the end making the same greedy choices, and try to meet in the middle.
What about factorial? Is the following solution intended or an overkill? (I think it uses no more than $$$59$$$ queries, but it's too slow to test it on all the inputs, and the checker gives $$$100$$$ points even if the solution uses too many queries).
Again there are multiple approaches, here is the idea from the official solution:
The main idea is that you can consider not only primes in the binary search, but also small multiples of primes $$$k \cdot p$$$ with $$$k < p$$$ and $$$p^k < 10^9$$$.
But this is not enough to get under 60 queries. The other idea is that the number of candidates you get for each result after binary search is different, but using binary search you always do the same number of queries independently of which result you get. You want to do something so that, if the results turns out to be one with lots of candidates, you spend less queries on finding it. In practice, you just notice that there is one gap between consecutive "searchable" elements much larger than the others, so you check that one at first and do the binary search for the others after that. With this you can just discard candidates one by one by using modulo an arbitrary large prime. You can shave off an additional couple of queries by also considering another big gap, or eliminating elements that are too close together to reduce the number of iterations in the binary search.
Where can we find an editorial for this olympiad?