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