adamant's blog

By adamant, history, 19 months ago, In English

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
$$$c_k = \sum\limits_{i+j=k} \binom{k}{i} a_i b_{j}.$$$
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.

  • Vote: I like it
  • +104
  • Vote: I do not like it

19 months ago, # |
  Vote: I like it +36 Vote: I do not like it

I love Sasha and swag strings and Alice and Bob (and string) concerning compacted suffix automaton very much! Thanks!