Hi everyone!
As the Universal Cup stage 7 which mirrored my contest from the Osijek Competitive Programming Camp 2023 just concluded, I decided to also upload the contest to gym as OCPC 2023, Oleksandr Kulkov Contest 3, and post the tutorial here. I hope you enjoyed the contest!
My previous ICPC-style contests:
Compiled PDF Tutorial for all problems: link.
To make it worth a separate blog post, I will also add some brief meta comments :)
P.S. Congratulations to the team USA1 (ecnerwala, ksun48, scott_wu) for solving all the problems in-contest!
104234A - Square Sum
Author: adamant
In number theory, it is a semi well-known fact that the number of solutions to $$$x^2 + y^2 \equiv z \pmod p$$$ only depends on whether $$$z$$$ is divisible by $$$p$$$. In particular, for $$$z=1$$$ the number of solutions is found as
where $$$\left(\frac{-1}{p}\right)$$$ is the Legendre symbol.
This fact is quite interesting on its own and it got me curious on how to count the solutions for generic modulo $$$m$$$. While it is considered standard fact that modulo $$$m$$$ is equivalent to modulo $$$p^k$$$ if you factorize it, I rarely ever saw problems that actually rely on it explicitly, so I felt like there should be one.
Besides that, while the solution expects transition from $$$p^{k-1}$$$ to $$$p^k$$$, I believe one could as well transition from $$$p^k$$$ to $$$p^{2k}$$$, making for a much more efficient solution of the factorization of $$$m$$$ is known and much larger. Of course, this idea would be very similar to Hensel lifting, also known in polynomial context as Newton's method.
104234B - Super Meat Bros
Author: adamant
See also: Hadamard product and binomial convolution of linear recurrences.
I saw several problems which required one to compute characteristic polynomial for the Hadamard product of two linear recurrences, but not for binomial convolution, despite the latter being based on the same ideas. Well, this problem is aimed to make binomial convolution of linear recurrences represented among competitive programming problems too :)
104234C - Testing Subjects Usually Die
Author: adamant
A version of this problem with $$$c=0$$$ and $$$c=1$$$ was proposed to me by a colleague when I was working at think-cell. It got me curious, how the transition from $$$c=0$$$ to $$$c=1$$$ would look like if we make it continuous, hence it inspired me to make this problem.
104234D - Triterminant
Author: adamant
See also: What are the properties of this polynomial sequence?
I actually came up with this polynomial sequence quite a long time ago, and there was even a reply by Terry Tao himself on the mathoverflow question about it that I asked. Since then, with the help of gamegame, I was able to develop much more intuitive and simple explanation for its major properties. There was another problem partially relying on this sequence: 901B - НОД многочленов.
One could use this sequence to get Accepted on that problem (though there were much simpler constructions too).
104234E - Garbage Disposal
Author: adamant
There were several harder ideas revolving around this problem. You may try to solve them if you feel bored:
- For each garbage type, you know its amount and for each garbage bin you know its capacity. Is it possible to dispose of all garbage?
- Same question as above, but the criterion is $$$\gcd(x, y) > 1$$$ instead of $$$\gcd(x, y) = 1$$$.
104234F - Palindromic Polynomial
Author: fedimser
The problem turned out much harder than I anticipated, and requiring some decent amount of casework. Nevertheless, I find the fact that $$$P(x) = x^n P(x^{-1})$$$ for such polynomials, and how it is used in the solution, very beautiful (even though a bit well-known).
104234G - Palindromic Differences
Author: fedimser
The initial version of the problem also guaranteed that the input array is a permutation, but we had to change this, as in this way the solution might've been too OEISable.
104234H - Graph Isomorphism
Author: adamant
While the intended solution relies on some advanced group theoretic facts (see e.g. here), I still felt like the solution itself is cute and could justify the problem. I also hope that there is a simpler explanation for the solution specifically in the graph case (by looking on the degrees, perhaps). Have you found a simpler solution?
104234I - DAG Generation
Author: adamant
Initially, I wanted the problem about generating rooted trees, rather than DAGs. In this case, one would have to solve the equation
or similar to check if $$$k$$$ generated trees are same. Then, one would use generalized CDQ convolution to solve it, and the equation itself follows from the number of topological orderings of a tree. But, ultimately, I decided that it would be more interesting to explore the connection between DAGs and their topological orderings, as I thought that the change in summation ordering here (to sum up DAGs for given topsort instead of topsorts for given DAG) is neat. One downside is that in this way the solution is formulaic and OEISable, perhaps?
104234J - Persian Casino
Author: adamant
Well, not much to comment here. I like Prince of Persia games, esp. the sands of time trilogy, and I would imagine that this would happen if Prince was using his time unwind abilities in a more casual manner. After all, I did a lot of save-load cheating with in-game casinos in Yakuza games :)
104234K - Determinant, or...?
Author: adamant
While most people probably solved it using the identity for the determinant of block matrices, my original inspiration was the formula for the determinant of circulant matrices. While circulant matrices correspond to cyclic convolutions, the matrix in question here corresponds (to some extent) to the or-convolution of two arrays, which provides some additional context as to why the solution is so similar to inverse sum over subsets, which is also used to compute such convolutions.
104234L - Directed Vertex Cacti
Author: adamant
As probably majority of participants who solved it during the contest, I found the fact accidentally and couldn't believe my eyes. Only much later, Endagorion and Electric-tric helped me make sense of it and find an actual meaningful bijective proof for the answer.
104234M - Siteswap
Author: adamant
I actually like juggling (though I can only do so with 3 balls), and the siteswap concept is quite nice, so I just wanted to make more people aware of it.
