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 | Codeforces Round #349 (Div. 2) | 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 | Codeforces Round #349 (Div. 1) | Construct a suffix structure for each vertex of the segment tree. |
| 15 | Dec 2017 | 901A - Hashing Trees | Codeforces Round #453 (Div. 1) | Construct counter-examples for specific tree hashing approach. |
| 16 | Dec 2017 | 901B - GCD of Polynomials | Codeforces Round #453 (Div. 1) | Construct two polynomials with smallest coefficients and largest possible amount of Euclidean algorithm steps for GCD. |
| 17 | Dec 2017 | 901E - Cyclic Cipher | Codeforces Round #453 (Div. 1) | Use DFT to solve a system of equations with circulant matrix. Involves chirp Z-transform to do DFT of arbitrary length. |
| 18 | Dec 2017 | 906D - Power Tower | Codeforces Round #454 (Div. 1) | Compute $$$a_l^{(a_{l+1}^{(\dots^{a_r})})}$$$ modulo $$$m$$$. |
| 19 | Dec 2017 | 906E - Reverses | Codeforces Round #454 (Div. 1) | Reverse some substrings of $$$A$$$ to obtain $$$B$$$. Involves palindromes. |
| 20 | Sep 2019 | 1220G - Geolocation | Codeforces Round #586 (Div. 1 + Div. 2) | 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 | Codeforces 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 given number of associative triplets. Lot of guessery. |
| 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 \gt (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. |
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!
