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.
A proof for Graph Isomorphism, which doesn't use anything complicated.
First, consider the case when $$$n \leq 3$$$. There are no graphs on $$$1$$$, $$$2$$$ or $$$3$$$ vertices with more isomorphic graphs than $$$n$$$. For $$$n = 1$$$ and $$$2$$$, there is only one isomorphic graph. For $$$n = 3$$$, the graph is either complete or empty, or it has $$$3$$$ isomorphic graphs. Therefore, if $$$n$$$ is less than or equal to $$$3$$$, the answer is "YES"
Now, consider the case when $$$n = 4$$$. If there are 3 nodes with the same degree, it turns out the answer is always less than or equal to n isomorphic graphs. Specifically, there are three cases:
And the for the $$$3-1$$$ split, the only two graphs that have this are the star graph and the complement of that. If the degrees of the nodes do not fall into any of these categories, then the graphs that are left have either a $$$2-2$$$ split of degrees or worse. This means their isomorphic graphs are greater than or equal to $$${4 \choose 2} = 6>4$$$. Therefore, if $$$n = 4$$$ and the degrees of the nodes do not fall into any of the special categories, the answer is NO.
Next, consider the case when $$$n \geq 5$$$. Let's again look at the degree sequence of the graph.
If the graph contains contains more than two distinct degrees, there are at least three distinguishable groups of nodes. This gives a lowerbound equal to a multinomial for the number of distinct isomorphic graphs. It's not hard to see this multinomial is too big, so the answer is NO.
If the graph has two distinct degrees, then the graph can be split into two groups of distinguishable vertices, with group A containing nodes of one degree and group B containing nodes of the other degree. If both groups contain at least $$$2$$$ nodes, then there are $$${n \choose A} \geq {n \choose 2} > n$$$, for $$$n \geq 5$$$.
Now, suppose without loss of generality that group A contains only one node. If this node has a degree other than $$$0$$$ or $$$n-1$$$, then some nodes in group B can be distinguished by whether they are connected to the node in group A. Additionally, the node in group A can be positioned on any node, giving $$$\geq 2*n$$$ isomorphic graphs . Therefore, the node in group A must have either degree 0 or n-1, for the answer to be YES.
Similarly, if nodes in group B have a degree other than $$$0$$$ or $$$n-1$$$, then some nodes in group B can be distinguished by whether they are connected to a fixed node in group B. Additionally, the a vertex can be moved again. Therefore, the answer is always NO in this case.
For regular graphs (with only 1 distinct degree), if the degree is not $$$0$$$ or $$$n-1$$$, again a similar argument with binomials shows that there are way too many isomorphic graphs. There's one special case, if the degree is $$$1$$$ or $$$n-2$$$, but then the graph is a perfect matching (or the complement), and the number of perfect matchings is $$$(n-1)\times (n-3) \times (n-5) \dots$$$, which is also bigger than $$$n$$$.
And for the graphs that are left, stars, complete graphs and their complement, they have $$$\leq n$$$ isomorphic graphs.
J can be solved without the $$$\Sigma m$$$ constraint using sqrt decomposition or Mo's algorithm.
Reference: https://yukicoder.me/problems/no/2206