By adamant, history, 4 months ago,

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) Solve a system of equations with a circulant matrix.
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!

• +104

 » 4 months ago, # |   +36 I love Sasha and swag strings and Alice and Bob (and string) concerning compacted suffix automaton very much! Thanks!