Hi everyone!
Today I saw a discussion in AC Discord server about how many problems some people made for different competitions. It was sparkled by this CF entry. I haven't keep track of this before, so it made me curious to go through everything that I made and publish in a comprehensive list. I'm doing it mostly out of curiosity, but maybe it might be interesting for someone else too :)
| # | Date | Problem | Contest | Comment |
|---|---|---|---|---|
| 1 | Jan 2016 | Sasha and Swaps | Ad Infinitum 14 | Find a $$$T$$$-th root of a given permutation, while minimizing the number of swaps in which the root may be decomposed. |
| 2 | Aug 2015 | Sasha and swag strings | Ptz Summer 2015. MIPT Contest | Compute the total number of distinct substrings on all edges of a given string's suffix tree. |
| 3 | Sep 2015 | Alice and Bob (and string) | Hackerrank World Cup Finals | A game, for which a game graph is a suffix automaton of reversed string and you use its suffix link tree as a suffix tree to get the answer. |
| 4 | Apr 2016 | Dihedral Subgroup | Ad Infinitum 15 | Given $$$n$$$, find the smallest symmetric group $$$S_m$$$ that contains the dihedral group $$$D_n$$$ as a subgroup. |
| 5 | Sep 2016 | Gears of War | Week of Code 23 | Simple problem on bipartiteness. |
| 6 | Sep 2016 | Lighthouse | Week of Code 23 | Implementation grid problem. |
| 7 | Sep 2016 | Treasure Hunting | Week of Code 23 | Simple geometry problem. Has 1-line solution with complex numbers. |
| 8 | Sep 2016 | Unexpected Problem | Week of Code 23 | When is it true that $$$st = ts$$$ for strings $$$s$$$ and $$$t$$$? |
| 9 | Sep 2016 | Gravity Tree | Week of Code 23 | Data structures on trees. |
| 10 | Sep 2016 | Enclosure | Week of Code 23 | Construct a polygon with given sides $$$L_1, \dots, L_n$$$ and maximum area. |
| 11 | Sep 2016 | Sasha and the Swaps II | Week of Code 23 | Find the number of ways to represent a permutation as $$$k$$$ swaps. |
| 12 | Dec 2016 | The Axis of Awesome | Ad Infinitum 17 | Given $$$n$$$ points in 3D, add minimum number of points so that sum of squared distances to any axis passing through the origin is the same. |
| 13 | Apr 2016 | 667B - Coat of Anticubism | CF Round #349 | Given $$$L_1, \dots, L_{n-1}$$$, add shortest $$$L_n$$$ so that it's possible to make a polygon with such side lengths. |
| 14 | Apr 2016 | 666E - Forensic Examination | CF Round #349 | Construct a suffix structure for each vertex of the segment tree. |
| 15 | Dec 2017 | 901A - Hashing Trees | CF Round #453 | Construct counter-examples for specific tree hashing approach. |
| 16 | Dec 2017 | 901B - GCD of Polynomials | CF Round #453 | Construct two polynomials with smallest coefficients and largest possible amount of Euclidean algorithm steps for GCD. |
| 17 | Dec 2017 | 901E - Cyclic Cipher | CF Round #453 | Solve a system of equations with a circulant matrix. |
| 18 | Dec 2017 | 906D - Power Tower | CF Round #454 | Compute $$$a_l^{(a_{l+1}^{(\dots^{a_r})})}$$$ modulo $$$m$$$. |
| 19 | Dec 2017 | 906E - Reverses | CF Round #454 | Reverse some substrings of $$$A$$$ to obtain $$$B$$$. Involves palindromes. |
| 20 | Sep 2019 | 1220G - Geolocation | CF Round #586 | Given $$$n$$$ random points $$$(x_i, y_i)$$$ and unordered set of distances $$$\rho_i$$$ to some $$$(x, y)$$$, find all possible $$$(x, y)$$$. Input is randomized. |
| 21 | Jul 2020 | 1375I - Cubic Lattice | CF Global Round 9 | Given $$$n$$$ points $$$(x_i, y_i, z_i)$$$, find a cubic lattice with largest cell size that contains all the given points. Involves integer quaternions. |
| 22 | Jul 2017 | Tree Expectancy | July Challenge 2017 | Find the expected number of vertices having exactly one child in a random ordered tree. |
| 23 | Sep 2018 | Table Game | September Challenge 2018 | A simple 2-dimensional game. |
| 24 | Aug 2019 | FourSquareSum | SRM 764 | You're given $$$a,b,c,d$$$ such that $$$a^2 + b^2 + c^2 + d^2 = 2n$$$. Find $$$s,x,y,z$$$ such that $$$s^2+x^2+y^2+z^2=n$$$. |
| 25 | Aug 2018 | Alice and Bob and a string | Ptz Summer 2018. MIPT Contest | Similar to "Alice and Bob (and string)", but now characters are appended on both sides. |
| 26 | Feb 2019 | 102129A - Tritwise Mex | Ptz Winter 2019. OKC 1 | Tritwise mex convolution. |
| 27 | Feb 2019 | 102129B - Associativity Degree | Ptz Winter 2019. OKC 1 | Construct a binary operation with a specified number of associative triplets. |
| 28 | Feb 2019 | 102129C - Medium Hadron Collider | Ptz Winter 2019. OKC 1 | Long story short, do some combinatorics or polynomial GCD. |
| 29 | Feb 2019 | 102129D - Basis Change | Ptz Winter 2019. OKC 1 | Change the basis of linear recurrence in a specific manner. |
| 30 | Feb 2019 | 102129E - Scored Nim | Ptz Winter 2019. OKC 1 | Some simple game. |
| 31 | Feb 2019 | 102129F - Milliarium Aureum | Ptz Winter 2019. OKC 1 | Data structures on a tree. |
| 32 | Feb 2019 | 102129G - Permutant | Ptz Winter 2019. OKC 1 | Find the determinant of a matrix, in which each row is the same permutation of the previous one. |
| 33 | Feb 2019 | 102129H - Game Of Chance | Ptz Winter 2019. OKC 1 | Compute a gain expectation in randomized game. |
| 34 | Feb 2019 | 102129I - Incomparable Pairs | Ptz Winter 2019. OKC 1 | Compute the number of substring pairs of a given string that are not substrings of each other. |
| 35 | Feb 2019 | 102129J - The Zong of the Zee | Ptz Winter 2019. OKC 1 | I don't remember, but it was somehow inspired by Sunless Sea. |
| 36 | Feb 2019 | 102129K - Expected Value | Ptz Winter 2019. OKC 1 | Constraints should push you into $$$O(n^2)$$$ dp, right? |
| 37 | Aug 2019 | 102354A - Square Root Partitioning | Ptz Summer 2019. OKC 2 | Find the number of ways to split $$$\sqrt{a_1}, \dots, \sqrt{a_n}$$$ in equal sum sets. |
| 38 | Aug 2019 | 102354B - Yet Another Convolution | Ptz Summer 2019. OKC 2 | $$$\max\vert a_i - b_j\vert$$$ convolution over $$$\gcd(i, j) = k$$$. |
| 39 | Aug 2019 | 102354C - Money Sharing | Ptz Summer 2019. OKC 2 | Some warm-up problem. |
| 40 | Aug 2019 | 102354D - Magic Strings | Ptz Summer 2019. OKC 2 | Compute a number of distinct subsequences of specific string pattern. |
| 41 | Aug 2019 | 102354E - Decimal Expansion | Ptz Summer 2019. OKC 2 | Compute the expansion of $$$\frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \dots $$$ |
| 42 | Aug 2019 | 102354F - Cosmic Crossroads | Ptz Summer 2019. OKC 2 | Find a rotation that matches two sets of random points in 3D. |
| 43 | Aug 2019 | 102354H - Defying Gravity | Ptz Summer 2019. OKC 2 | Notice something about symmetry in 2D. |
| 44 | Aug 2019 | 102354I - From Modular to Rational | Ptz Summer 2019. OKC 2 | Given $$$\frac{p}{q}$$$ modulo $$$m > (p+q)^2$$$, find $$$p$$$ and $$$q$$$. |
| 45 | Aug 2019 | 102354J - Tree Automorphisms | Ptz Summer 2019. OKC 2 | Find a generating set for an automorphism group of a given tree. |
| 46 | Feb 2023 | 104234A - Square Sum | OCPC 2023. OKC 3 | Count solutions to $$$x^2 + y^2 \equiv z \pmod m$$$. |
| 47 | Feb 2023 | 104234B - Super Meat Bros | OCPC 2023. OKC 3 | Given linear recurrences $$$a_i$$$ and $$$b_j$$$, find a linear recurrence for |
| 48 | Feb 2023 | 104234C - Testing Subjects Usually Die | OCPC 2023. OKC 3 | Guess random number with memory loss. |
| 49 | Feb 2023 | 104234D - Triterminant | OCPC 2023. OKC 3 | Terry Tao solved this on my MathOverflow question 5 years ago. |
| 50 | Feb 2023 | 104234E - Garbage Disposal | OCPC 2023. OKC 3 | Too similar to 1818B - Indivisible? |
| 51 | Feb 2023 | 104234H - Graph Isomorphism | OCPC 2023. OKC 3 | Check if a graph has at most $$$n$$$ distinct isomorphic graphs. |
| 52 | Feb 2023 | 104234I - DAG Generation | OCPC 2023. OKC 3 | Find the probability of two DAGs generated by a given process to be the same DAG. |
| 53 | Feb 2023 | 104234J - Persian Casino | OCPC 2023. OKC 3 | What if Prince of Persia cheated in casino using the dagger of time? |
| 54 | Feb 2023 | 104234K - Determinant, or...? | OCPC 2023. OKC 3 | Given $$$a_i$$$, find $$$\det A$$$ for $$$A_{ij} = a_{i | j}$$$. |
| 55 | Feb 2023 | 104234L - Directed Vertex Cacti | OCPC 2023. OKC 3 | Count digraphs on $$$n$$$ vertices such that their SCCs are cycles or isolated vertices and they have $$$m$$$ edges outside SCCs. |
| 56 | Feb 2023 | 104234M - Siteswap | OCPC 2023. OKC 3 | I like juggling. |
| 57 | Apr 2023 | 1818A - Politics | CF Round #869 | Wouldn't you be upset if somebody disagrees with you? |
| 58 | Apr 2023 | 1818B - Indivisible | CF Round #869 | Too similar to 104234E - Garbage Disposal? |
| 59 | Apr 2023 | 1817C - Similar Polynomials | CF Round #869 | Given $$$A(x)$$$ and $$$B(x)$$$, find $$$s$$$ such that $$$B(x) = A(x+s)$$$. |
| 60 | Apr 2023 | 1817D - Toy Machine | CF Round #869 | This game was inspired by a puzzle in God of War. |
| 61 | Apr 2023 | 1817E - Half-sum | CF Round #869 | This problem was inspired by 102129K - Expected Value. |
| 62 | Apr 2023 | 1817F - Entangled Substrings | CF Round #869 | Find number of pairs of substrings $$$a$$$ and $$$b$$$ that only occur in $$$s$$$ as substrings of $$$acb$$$ for some $$$c$$$. |
I think that's mostly it. There might be some other problems here and there which were difficult for me to retrieve. I also prepared a number of problems for internal educational use and some problems based on somebody else's ideas, but I think they shouldn't be included here.
Well, it seems I haven't set any new problems in a while. Hope it will change soon!
UPD: Added OKC 3 and CF Round #869.
I love Sasha and swag strings and Alice and Bob (and string) concerning compacted suffix automaton very much! Thanks!
You might like 1817F - Entangled Substrings too, though it's simpler than those :)