Oleksandr Kulkov Contest 3 in gym + tutorial and comments

Правка en4, от adamant, 2023-03-12 02:21:52

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

$$$ p-\left(\frac{-1}{p}\right), $$$

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.

Tutorial

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 :)

Tutorial

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.

Tutorial

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).

Tutorial

104234E - Garbage Disposal

Author: adamant

There were several harder ideas revolving around this problem. You may try to solve them if you feel bored:

  1. 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?
  2. Same question as above, but the criterion is $$$\gcd(x, y) > 1$$$ instead of $$$\gcd(x, y) = 1$$$.
Tutorial

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).

Tutorial

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.

Tutorial

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?

Tutorial

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

$$$ \left(x\frac{\partial }{\partial x}\right)^k T(x) = x e^{T(x)}, $$$

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?

Tutorial

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 :)

Tutorial

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.

Tutorial

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.

Tutorial

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.

Tutorial
Теги okc, ocpc, universal cup, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский adamant 2023-03-12 02:21:52 170
en3 Английский adamant 2023-03-12 02:17:57 0 (published)
en2 Английский adamant 2023-03-12 02:09:09 0 (saved to drafts)
en1 Английский adamant 2023-03-12 02:08:15 8344 Initial revision (published)