antontrygubO_o's blog

By antontrygubO_o, 13 months ago, In English

Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs by adamant and by tibinyte; I finally decided to do it after my Universal Cup contest. This is not a super-comprehensive list, I also set some problems for some local contests, but that's most of it.

I want to encourage other setters to write such blogs. For me, it's very interesting to read about the backstories of some problems and also to see all the problems by some author gathered in one place (as most authors give problems to several platforms).

One important point. As you will see from the comments, many of my problems were improved by other people, and I myself improved some problems by other people. I think that it's crucial to have someone to discuss your problems with (apart from the coordinator).

So, here we go.

# Date Problem Contest Comment
1 June 2019 Vus the Cossack and Strings Codeforces Round #571 (Div. 2)
2 June 2019 Vus the Cossack and a Graph Codeforces Round #571 (Div. 2) My first problem
3 July 2019 Keanu Reeves Codeforces Round #572 (Div. 2) Split binary string into the smallest number of substrings, in each of which # of 0s is not equal to # of 1s. Initially, we wanted to ask to split into any number of substrings (and the model solution was to split into n characters), but we were told that this is not a real problem
4 July 2019 Number Circle Codeforces Round #572 (Div. 2)
5 July 2019 Candies! Codeforces Round #572 (Div. 2)
6 July 2019 Add on a Tree Codeforces Round #572 (Div. 1)
7 July 2019 Add on a Tree: Revolution Codeforces Round #572 (Div. 1) We were told to add this problem so that the contest would have at least some implementation
8 July 2019 Count Pairs Codeforces Round #572 (Div. 1) One of my best problems. Pinnacle of problemsetting...
9 July 2019 Make Equal Codeforces Round #572 (Div. 1) I came up with the statement, 244mhq with solution
10 July 2019 Problem from Red Panda Codeforces Round #572 (Div. 1) 244mhq came up with the statement, I with solution
11 August 2019 Choose Two Numbers Codeforces Round #580 (Div. 2)
12 August 2019 Make Product Equal One Codeforces Round #580 (Div. 2)
13 August 2019 Almost Equal Codeforces Round #580 (Div. 1)
14 August 2019 Shortest Cycle Codeforces Round #580 (Div. 1)
15 August 2019 Palindromic Paths Codeforces Round #580 (Div. 1)
16 August 2019 Almost All Codeforces Round #580 (Div. 1) One of my best problems. Unfortunately, a similar idea was used in a problem from IOI 2019
17 August 2019 Expected Value Again Codeforces Round #580 (Div. 1)
18 August 2019 Beauty of a Permutation Codeforces Round #580 (Div. 1) Sadly, I didn't know about permutation tree back then
19 October 2019 Find the Array SEERC 2019 My best interactive problem
20 October 2019 Cycle String? SEERC 2019
21 October 2019 Game on a Tree SEERC 2019 This is not a good problem, as it indeed is well known for general graphs... Don't do this
22 October 2019 Tree Permutations SEERC 2019
23 October 2019 Graph and Cycles SEERC 2019
24 December 2019 Make Good Good Bye 2019 I initially had solution only with adding $$$3$$$ elements. In testing, some testers discovered a solution with $$$2$$$ elements, and after the contest, we realized that it can be solved with only $$$1$$$ element!
25 December 2019 Strange Device Good Bye 2019
26 December 2019 Divide Points Good Bye 2019 One of my best problems
27 December 2019 Awesome Substrings Good Bye 2019 There is a very nice $$$n\log^2{n}$$$ solution, but we were not able to find it :(
28 December 2019 Subset with Zero Sum Good Bye 2019 One of my best problems. Initially, I was going to send it to IMO, and there was another problem at this position, but this problem by a recent round by hugopm turned out to be too similar to it :(, so we had to replace it.
29 December 2019 Xor on Figures Good Bye 2019 Initially, I sent it to IOI 2020, but then decided that it doesn't have meaningful subtasks and that it would be better to use it on CF. I wrote to the PSC and told them that I am retracting the proposal, apologizing. It seems that they missed my email, as in a few months, I received an email from PSC saying: The ISC would like to remind you that this strongly violates the rules of the IOI Call for Tasks, which requires all submitted tasks to be kept strictly confidential until the end of IOI 2020. In the future, if you would like to submit the task elsewhere and not have your task be considered for the IOI, you should email the host directly to let them know of this decision.
30 February 2020 So Mean Codeforces Round #618 (Div. 1) I just became a coordinator on Codeforces, and wanted to help to conduct the round as soon as possible, so I donated this problem. Now I don't think that it's a good problem... Mostly casework
31 March 2020 Kuroni and Impossible Calculation Ozon Tech Challenge 2020
32 March 2020 Kuroni and the Score Distribution Ozon Tech Challenge 2020
33 March 2020 Kuroni and Antihype Ozon Tech Challenge 2020 One of my best problems. Initially, the problem was about the general graph. Unfortunately, minimum arborescence solves the problem, so we had to adjust it this way.
34 July 2020 Integer Game Codeforces Global Round 9 244mhq suggested the setup, and I solved it. I will just leave this comment here
35 July 2020 Tree Modification Codeforces Global Round 9 This is one of the last problems which I created when I still thought that solution->statement is better than statement->solution is a much better way of problemsetting. This problem is a good example of why I switched... making statements not artificial with solution->statement is very hard.
36 September 2020 Permutation Forgery Codeforces Round #668 (Div. 2)
37 September 2020 Watermelon September Lunchtime 2020 (Div. 2)
38 September 2020 GCD operations September Lunchtime 2020 (Div. 2)
39 September 2020 Root the Tree September Lunchtime 2020 (Div. 1)
40 September 2020 Robot Detector September Lunchtime 2020 (Div. 1)
41 September 2020 Permutation Split September Lunchtime 2020 (Div. 1) I was thinking about this problem for quite some time in the background, and then at some point 244mhq brought up the following (old) problem: "Given a graph, check if we can split it into two graphs with same numbers of edges." I realized this problem was a partial case, but the statement was so natural, and the original problem wasn't too well-known from what I've searched, so I decided to still use this problem. Generally, using partial cases of some other problems is a very bad practice...
42 September 2020 Few Different Elements September Lunchtime 2020 (Div. 1)
43 September 2020 Adding on Segments September Lunchtime 2020 (Div. 1) My first problem that wasn't solved in the contest
44 November 2020 XOR-gun Technocup 2021 — Elimination Round 2
45 December 2020 String Operations Codechef December Challenge 2020 (Div. 1)
46 March 2021 Long Common Subsequence AtCoder Grand Contest 052
47 March 2021 Tree Edges XOR AtCoder Grand Contest 052 One of my best problems
48 March 2021 Nondivisible Prefix Sums AtCoder Grand Contest 052 The idea of the setup is by 244mhq in 2020, then I solved it and improved to the counting version
49 March 2021 Equal LIS AtCoder Grand Contest 052
50 March 2021 3 Letters AtCoder Grand Contest 052 One of my best problems. Thanks to maroonrk for coming up with this nice trick, my initial solution was much more complicated
51 March 2021 Tree Vertices XOR AtCoder Grand Contest 052 My second problem that wasn't solved in the contest
52 May 2021 Reverse Game SEERC 2020
53 May 2021 3-colorings SEERC 2020 Initially this was going to be used as AGC52F, but we were afraid of not intended solutions. Sadly, all AC solutions on the mirror were indeed not intended :( In the latter half of $$$2020$$$, I almost stopped coming up with problems; solution->statement didn't work well for me anymore, and I didn't believe I could come up with hard problems in the statement->solution way. This was the first hard problem that I came up with in statement->solution way, and it was the reason why I believed that I can make an AGC set; I messaged maroonrk after I came up with it.
54 May 2021 Divisible by 3 SEERC 2020
55 May 2021 Fence Job SEERC 2020 Initially, I wanted to solve the problem "Choose segment, replace all its elements by their OR, find the number of possible arrays", but my solutions turned out to be wrong. Then bicsi helped to revise the problem into this version
56 May 2021 AND = OR SEERC 2020 One of my few good data structure problems
57 May 2021 Modulo Permutations SEERC 2020
58 August 2021 Eulerian? GP of IMO
59 August 2021 Fancy Formulas GP of IMO
60 August 2021 Glory Graph GP of IMO I was inspired by the fact that for a graph, knowing all degrees, we can find the number of triangles plus antitriangles, so I was looking for some sort of relation for graphs on four nodes.
61 August 2021 Hamiltonian GP of IMO
62 August 2021 Intellectual Implementation GP of IMO I was once again inspired by this problem above, and thought that I can try to use this idea for counting something awful. Then, I came up with this statement, and 244mhq helped to solve it
63 August 2021 Joke GP of IMO
64 August 2021 K-onstruction GP of IMO Initially 244mhq proposed this problem, asking to construct a set of size at most $$$3\log{K}$$$ for a given $$$K$$$. We were then able to improve it to the bound in the statement.
65 August 2021 Little LCS GP of IMO Sorry for this problem... but if it fits anywhere, it's a camp training contest
66 September 2021 One Pile September Cook-Off 2021 (Div. 1) Utkarsh.25dec initially proposed version without counting (just determine who wins). I helped to make it harder, as we needed some hard problems for Cook-Off
67 October 2021 Permutating Inversions October Cook-Off 2021 (Div. 1) My third problem that wasn't solved in the contest. I wanted to add a pre-last problem to a Cook-Off, as I thought that the contest would be too easy otherwise. Apparently, this problem turned out to be the hardest, with 0 solves, with the next hardest problem having 1 solve...
68 October 2021 ABC Identity AtCoder Grand Contest 055 Jason Bourne 1
69 October 2021 ABC Supremacy AtCoder Grand Contest 055 Jason Bourne 2
70 October 2021 Weird LIS AtCoder Grand Contest 055
71 October 2021 ABC Ultimatum AtCoder Grand Contest 055 Jason Bourne 3. Initially, the problem was just to check whether a string is good ($$$N \le 2\cdot 10^5$$$), but then AmShZ submitted an unproven greedy in testing, and we were able to improve it to the current version
72 October 2021 Set Merging AtCoder Grand Contest 055 Certainly my best problem ever, and my fourth problem that wasn't solved in the contest. Read the comment for problem 55 from this list... I decided to solve this problem for OR when $$$a_i = 2^i$$$ initially, and bruteforce + OEIS showed that the answer is the number of sequences with LDS<=3. I was shocked and was stuck on proving this for three days until I finally realized the solution.
73 October 2021 Creative Splitting AtCoder Grand Contest 055 My initial proposal was: Let's call an array $$$a$$$ of length $$$2n$$$, consisting of integers from $$$1$$$ to $$$n$$$, good, if it is possible to split it into two subsequences of length $$$n$$$, such that in each subsequence $$$i$$$-th element doesn't exceed $$$i$$$ for every $$$i$$$ from $$$1$$$ to $$$n$$$. You are given array $$$a$$$ of length $$$2n$$$, where some numbers are given, and some are $$$−1$$$ (unknown). Find the number of ways to replace $$$−1$$$s with integers from $$$1$$$ to $$$n$$$ so that $$$a$$$ becomes good. With brute force, I knew that the number of "splittable" arrays is $$$\frac{(2n)!}{2^n}$$$ for several months, but I couldn't prove this. Thanks a lot to maroonrk for providing the proof and then for improving my initial proposal to this version.
74 November 2021 Many LCS SEERC 2021 Initially I needed length of order $$$\sqrt{K}$$$, thanks to Um_nik for improving the problem to the current constraints
75 November 2021 Max Pair Matching SEERC 2021
76 November 2021 ABC Legacy SEERC 2021 Jason Bourne 4
77 November 2021 Counting Phenomenal Arrays SEERC 2021
78 November 2021 LIS Counting GP based on SEERC 2021 I was really into LIS problems at the time...
79 December 2021 Sorting Segments SnackDown 2021 Online Elimination Round Yes, this is very similar to Stooge Sort, but I haven't heard about it before setting the problem
80 December 2021 Sorter Prodigy SnackDown 2021 Online Elimination Round Unfortunately, coincided with CCO '18 P6 :(. This happens
81 December 2021 Prefix Suffix LIS Constructing SnackDown 2021 Online Elimination Round
82 January 2022 Equal Number of Prefix Maximums SnackDown 2021 Final Round Unfortunately, this is an easier version of AGC028E :(
83 January 2022 Circular Permutation Recovery January Lunchtime 2022 (Div. 1) Unfortunately, this turned out to be an easier version of IOI 2020 plants...
84 January 2022 Divisible Distances January Lunchtime 2022 (Div. 1)
85 April 2022 Modular Circular Permutations April Lunchtime 2022 (Div. 1)
86 April 2022 Odd Split April Lunchtime 2022 (Div. 1)
87 May 2022 Doubled Distances May Cook-Off 2022 (Div. 2)
88 May 2022 Triple Inversions May Cook-Off 2022 (Div. 1)
89 May 2022 Different Subarrays Rearrange May Cook-Off 2022 (Div. 1)
90 May 2022 Split Powers Of 2 May Cook-Off 2022 (Div. 1)
90 May 2022 Max Min Circle Difference May Cook-Off 2022 (Div. 1)
91 May 2022 Plus Xor Increase May Cook-Off 2022 (Div. 1) Another rare good algorithmic problem...
92 May 2022 Make Grid Comparable May Cook-Off 2022 (Div. 1)
93 May 2022 Catch Me If You Can May Cook-Off 2022 (Div. 1) My fifth problem that wasn't solved in the contest
94 May 2022 Everything Everywhere All But One Codeforces Round #794 (Div. 2) Watch Everything Everywhere All At Once!
95 May 2022 Odd Subarrays Codeforces Round #794 (Div. 2)
96 May 2022 Circular Local MiniMax Codeforces Round #794 (Div. 1)
97 May 2022 Bring Balance Codeforces Round #794 (Div. 1)
98 May 2022 Permutation Weight (Easy Version) Codeforces Round #794 (Div. 1)
99 May 2022 Permutation Weight (Hard Version) Codeforces Round #794 (Div. 1)
100 May 2022 The Ultimate LIS Problem Codeforces Round #794 (Div. 1) One of my best problems
101 June 2022 Split AND Sum June Cook-Off 2022 (Div. 1)
102 June 2022 Prefix Suffix Distinct June Cook-Off 2022 (Div. 1)
103 June 2022 Max Minus Min June Cook-Off 2022 (Div. 1) This problem was initially proposed by jainmilind for $$$A, B, C \le 10^6$$$, I was able to improve it to the current constraints
104 June 2022 XOR, The Detective June Lunchtime 2022 (Div. 1)
105 June 2022 SPLIT With XOR Not X June Lunchtime 2022 (Div. 1) Filler problem, made just for all XOR contest
106 September 2022 Longest Unfriendly Subsequence EJOI 2022
107 September 2022 Permutations LCS EJOI 2022 Dear EJOI 2022 participants. I am deeply sorry for your destroyed mental health
108 September 2022 Anti-Increasing Addicts Codeforces Global Round 22
109 November 2022 Anti-median (Easy Version) Pinely Round 1 (Div. 1 + Div. 2)
110 December 2022 My Last ABC Problem AtCoder Grand Contest 059 From now on, only problems about 123
111 December 2022 Arrange Your Balls AtCoder Grand Contest 059
112 December 2022 Guessing Permutation for as Long as Possible AtCoder Grand Contest 059 When I first came up with a statement and solved it, I thought that the problem is standard and garbage. It turned out I was extremely wrong...
113 December 2022 Distinct Elements on Subsegments AtCoder Grand Contest 059 I came up with the statement in May of $$$2022$$$ and couldn't solve for three months.
114 December 2022 Grid 3-coloring AtCoder Grand Contest 059 Initially, I proposed a version with construction for $$$n<=100$$$, and my proof was extremely hard (and greedy). A week before the contest maroonrk realized that we can use the same idea as in AGC052E, and the problem became much nicer. Unfortunately, this idea turned out to be present in some papers...
115 December 2022 LIDS AtCoder Grand Contest 059 My sixth problem that wasn't solved in the contest, and, probably, the hardest problem that I ever made. In March 2022, I noticed that the number of permutations of length $$$n$$$ with $$$LIS = x, LDS = n+1-x$$$ is $$$C(n-1, x-1)^2$$$. (Yes, this is easy with the Robinson–Schensted correspondence, but I didn't know it). I was able to prove this only in August, and after finding a nice bijection in the process, I decided that I can try to write a third AGC.
116 December 2022 Divisible by 4 Spanning Tree SEERC 2022
117 December 2022 Exercise SEERC 2022
118 December 2022 Inadequate Operation SEERC 2022
119 February 2023 Adjacent Product Sum Universal Cup 1 Stage 4: Ukraine
120 February 2023 Binary Arrays and Sliding Sums Universal Cup 1 Stage 4: Ukraine
121 February 2023 Count Hamiltonian Cycles Universal Cup 1 Stage 4: Ukraine My initial solution was in $$$O(n^2)$$$, thanks to Um_nik for improving it to $$$O(n)$$$
122 February 2023 Distance Parities Universal Cup 1 Stage 4: Ukraine
123 February 2023 Excellent XOR Problem Universal Cup 1 Stage 4: Ukraine
124 February 2023 F*** 3-Colorable Graphs Universal Cup 1 Stage 4: Ukraine Like... who tf likes 3-colorable graphs?
125 February 2023 Graph Problem With Small $n$ Universal Cup 1 Stage 4: Ukraine This problem was born when me and 244mhq were discussing how to implement checker to Hamiltonian from our Ptz contest... We were surprised that we haven't seen it before, and it seems that almost no one has seen it. Apparently, Golovanov399 showed that this is standard exercise :(
126 February 2023 Help Me to Get This Published Universal Cup 1 Stage 4: Ukraine Please, help me to get this published
127 February 2023 Increasing Grid Universal Cup 1 Stage 4: Ukraine One of my most standard problems, but I decided that having such problem in an ICPC contest is good
128 February 2023 Jewel of Data Structure Problems Universal Cup 1 Stage 4: Ukraine
129 February 2023 King of Swapping Universal Cup 1 Stage 4: Ukraine
130 February 2023 Least Annoying Constructive Problem Universal Cup 1 Stage 4: Ukraine My best constructive problem
131 February 2023 Most Annoying Constructive Problem Universal Cup 1 Stage 4: Ukraine My seventh problem that wasn't solved in a contest, and the first one that wasn't solved in ICPC format
132 February 2023 No Zero-Sum Subsegment Universal Cup 1 Stage 4: Ukraine
  • Vote: I like it
  • +460
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it +126 Vote: I do not like it

132 problems... It's like... 132 more than I ever did... It's almost a problem a week. Fascinating!

»
13 months ago, # |
  Vote: I like it +15 Vote: I do not like it

orz sir

What do you want to focus on: participating, coordinating or authoring contests?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    I will focus more on some not cp-related things. As for cp, I want to train for WF22, so I won't do coordinating and problemsetting for a while. I have around 20 unused semi-good/good problems, which you might see in some upcoming contests, but I probably won't actively create new problems this year.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the IMO problem proposal of 1270G - Subset with Zero Sum?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    If I sent it, I would ask to prove that for such integers, there exists some nonempty subset with zero sum.

»
13 months ago, # |
  Vote: I like it +94 Vote: I do not like it

Just imagine, if BledDest create a blog like this.

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

From now on, only problems about 123

I have to imagine that there is a "My Last 123 problem" :P

»
13 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

UPD: I understood the problem incorrectly. Ignore everything I said here.

I've found a mistake in your problem 102392F - Game on a Tree (your 21st problem on the list).

A few days ago I first tried to solve it using a complicated dp which should just solve the problem, but I got WA on test 32. I decided to wait a couple of days and now I looked at the editorial and saw the correspondence with "perfect mathing" on the tree. I implemented a dp to calculate if that is possible, but I got WA on test 32 again!?

I couldn't understand what was wrong, so I decided to look at the editorial explanation for the dp. It was different to my dp, but I didn't see why my solution would be incorrect. I decided to copy the editorial dp and got AC. Now I was even more confused.

Image of submissions

Submissions (links don't work since it's a gym contest):

Submission 1 (general dp, WA on 32)
Submission 2 (perfect matching dp, WA on 32)
Submission 3 (copy of editorial, AC)

After thinking for a moment, I realized that the editorial solution (the one I got AC with) is wrong! I have a simple test case where the editorial solution fails:

Failing test
Image of the tree

It's pretty clear that Alice can win this: Alice places the chip on node 4. Bob has to move it to node 3. Alice can now move the chip to node 5. Bob has no moves so Alice wins.

There are 11 pages of submissions of problem F with WA on 32. Is is possible to fix the correct solution now or is it too complicated after this much time?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's not mentioned anywhere that ancestor/descendant has to be direct. Bob can move to node 1.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Oh, I guess I didn't read it carefully enough. Sorry.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for sharing! I happened to notice that 1186F - Vus the Cossack and a Graph coincides with HMMT February 2018 Team Round problem 9. Seems like a harmless coincidence; it's not the only time that the HMMT February Team Round unintentionally overlapped with a coding contest.

»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How can you find the number of triangles plus antitriangles in a graph given all degrees? Why is it uniquely determined? Do you know a ressource on this?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Problem

    Let's calculate the total number of chains of length 2 and anti-chains of length 2: it's $$$\sum_{v} \binom{deg_v}{2}$$$ and $$$\sum_{v} \binom{n - 1 - deg_v}{2}$$$ respectively, since each chain/anti-chain has a unique middle vertex, and we should choose 2 edges/anti-edges from it. Each triangle contributes 3 unique chains, and each anti-triangle contributes 3 unique anti-chains; when 3 vertices are not triangles/anti-triangles, they contribute either 1 chain or 1 anti-chain. Therefore, if $$$\Delta$$$ is the number of triangles and anti-triangles together, $$$3 \Delta + (\binom{n}{3} - \Delta) = \sum_{v} \binom{deg_v}{2} + \sum_{v} \binom{n - 1 - deg_v}{2}$$$, from where $$$\Delta = \frac{1}{2} (\sum_{v} \binom{deg_v}{2} + \sum_{v} \binom{n - 1 - deg_v}{2} - \binom{n}{3})$$$.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share some initial solution or proof? orz