### FelixMP's blog

By FelixMP, history, 2 months ago,

I have added this year's Spain Olympiad in Informatics to the gym.

Contest facts:

• 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!

• +136

 » 2 months ago, # |   0 Auto comment: topic has been updated by FelixMP (previous revision, new revision, compare).
 » 2 months ago, # |   +66 Thank you!
 » 7 weeks ago, # |   +9 How to solve estatuas?
•  » » 7 weeks ago, # ^ |   +10 Here are some hints for one solution (there are multiple possible approaches) Hint 1If 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. Hint 2Assuming 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. Hint 3You 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.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 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). Solution Precompute all the primes until $4 \cdot 10^6$. Find the largest prime $\leq n$ with binary search. There can be at most $72$ possible remaining values of $n$. For each pair $(x, x+2)$ of candidates, find a prime $x+2 < p < 4 \cdot 10^6$ such that $x! \equiv (x+2)!\ (\textrm{mod}\ p)$ (it can be found about $2/3$ of the times). For example, you can factorize $(x+1)(x+2)-1$ to find it. Then, check if $n! \equiv x!\ (\textrm{mod}\ p)$. In this way, you can exclude at least two candidates. Calculate the factorials of the remaining candidates modulo a random prime, so that you can exclude $1$ candidate for each remaining query.
•  » » » » 7 weeks ago, # ^ |   +20 Again there are multiple approaches, here is the idea from the official solution: SpoilerThe 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.
 » 7 weeks ago, # |   +4 Where can we find an editorial for this olympiad?