Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs by adamant, by tibinyte, by antontrygubO_o and by wuhudsm. I finally decided to do it after Codeforces Round $$$934$$$.
I would like to thank Non-origination, GoatTamer and KingRayuga for discussing the problems with me.
For each problem, I tried to include the some interesting stuff if I could remember.
I tried to avoid using spoilers for the problems. So you can look at the comments even if you have not tried the problem.
| # | Date | Problem | Difficulty | Contest | Comment |
|---|---|---|---|---|---|
| 1 | Aug 2021 | Tree Distance Sum | Div 2 E | Codechef Starters 10 | My first problem which appeared in some contest. I noticed some nice properties about the dfs traversal and decided to have a problem exploiting those properties. There are alternative solutions too. |
| 2 | Oct 2021 | Equal Beauty | Div 2 C | SnackDown 2021 — Online Round 1A | |
| 3 | Feb 2022 | Or Sum | Div 2 E | CodeChef Starters 27 | Standard problem revolving around counting contribution ideas |
| 4 | Feb 2022 | Non Coprime Neighbours | Div 2 C | CodeChef Starters 27 | |
| 5 | Feb 2022 | Distinct Binary Strings | Div 2 A | CodeChef Starters 27 | Cute easy problem |
| 6 | Mar 2022 | Interactive Tree 2 | Div 2 E | CodeChef Starters 28 | |
| 7 | Jun 2022 | Divisible by 3 | Div 2 A | CodeChef Starters 42 | |
| 8 | Jun 2022 | Minimum or Maximum | Div 2 A | CodeChef Starters 42 | |
| 9 | Jun 2022 | Maximise Set Bits | Div 2 C | CodeChef Starters 42 | My favorite problem from the round |
| 10 | Jun 2022 | Construct An Array | Div 2 D | CodeChef Starters 42 | How to write the checker? |
| 11 | Jun 2022 | Maximise Score | Div 2 E | CodeChef Starters 42 | I misread one of the problems in the qualifying round of Google Code Jam Qualification Round 2022, interpreted it as the mentioned the problem. |
| 12 | Jun 2022 | Divisible by i | Div 2 A | CodeChef June Long One | |
| 13 | Jun 2022 | Gcd and Lcm | Div 2 D | CodeChef June Long Two | |
| 14 | Jun 2022 | Counting Is Fun | Div 2 F | CodeChef June Long Two | Cool educational problem in my opinion |
| 15 | Oct 2022 | Playing with GCD | Div 2 B | Codeforces Round 825 | It was my first Div 2 round on Codeforces. |
| 16 | Oct 2022 | Good Subarrays | Div 2 E | Codeforces Round 825 | Do look at the intended solution. I think it is pretty nice. |
| 17 | Oct 2022 | Equal Binary Subsequences | Div 2 D | Codeforces Round 825 | One of my best problems. Here's the background story about this problem. I was solving the following problem. You are given a binary string $$$s$$$ of length $$$2n$$$. Partition it into two disjoint equal subsequences of equal length. I could not solve the problem above (later learned it is NP-hard). I realized that we could solve this if we could modify $$$s$$$ a bit, and I came up with the setup used in the contest. |
| 18 | Nov 2022 | Avoid Squares Please | Div 3 A | CodeChef Starters 63 | Funny problem |
| 19 | Nov 2022 | Make Length 1 | Div 2 A | CodeChef Starters 63 | |
| 20 | Nov 2022 | Count Partitions | Div 2 D | CodeChef Starters 63 | Good problem. I misread some OpenCup problem and came up with this problem. |
| 21 | Nov 2022 | GCD Sort | Div 2 E | CodeChef Starters 63 | I proposed this problem as Div 2 B. While testing, we realized that the intended solution was wrong. Utkarsh.25dec came up with the correct solution. |
| 22 | Nov 2022 | Distinct Neighbours | Div 2 E | CodeChef Starters 63 | Nice problem. |
| 22 | Nov 2022 | Distinct Neighbours | Div 2 B | CodeChef Starters 64 | Pretty cool problem |
| 23 | Nov 2022 | Count Number Of Pairs | Div 2 D | CodeChef Starters 67 | Cool task |
| 24 | Nov 2022 | Interactive Tree | Div 2 D | CodeChef Starters 67 | |
| 25 | Dec 2022 | Gcd of Subarrays | Div 2 A | CodeChef December Long | |
| 26 | Dec 2022 | Divisible by K | Div 2 A | CodeChef December Long | |
| 27 | Dec 2022 | Divisible by A_i | Div 2 A | CodeChef December Long | |
| 28 | Dec 2022 | Sum of Cube | Div 2 D | CodeChef December Long | |
| 29 | Dec 2022 | Distinct Sequence | Div 2 A | Codechef Starters 69 | |
| 30 | Dec 2022 | Longest Subarray | Div 2 B | Codechef Starters 69 | |
| 31 | Dec 2022 | Sort Permutation | Div 2 E | Codechef Starters 69 | I really like this task. Fun fact — This problem was not planned to be included in the contest. Around 3 hours before the contest, we found some bug in one of the problems, and this problem was prepared to be used as the replacement. |
| 32 | Dec 2022 | Divide and Conquer | Div 2 A | Codeforces Round 838 | |
| 33 | Dec 2022 | Make Array Good | Div 2 B | Codeforces Round 838 | |
| 34 | Dec 2022 | Binary Strings are Fun | Div 2 C | Codeforces Round 838 | One of my best problems. I came up with the problem idea while cycling and solved it while attending a college lecture. |
| 35 | Dec 2022 | Tree Sum | Div 2 E | Codeforces Round 838 | One of the best problems in the round. In the original problem, the weight of each edge was defined in some way. But TheScrasse suggested using the definition of good trees, which resulted in the same assignment of edge weight. |
| 36 | Dec 2022 | Good Pairs | Div 2 F | Codeforces Round 838 | Pretty cool data structure problem in my opinion |
| 37 | Dec 2022 | Unequal Adjacent Elements | Div 1 D | Codeforces Round 838 | I was trying the problem: You are given a tree consisting of $$$n$$$ nodes. Find a permutation $$$p$$$ of $$$[1,2,\ldots n]$$$ such that $$$dist(p_{i-1},p_i) \le dist(p_i,p_{i+1})$$$ for all $$$2 \le i < n$$$, where $$$dist(u,v)$$$ denotes the number of edges in the shortest path from $$$u$$$ to $$$v$$$. I came up with a constructive solution that did not use advanced tree techniques. Later, I learned that it could be bashed with centroid decomposition, which some people found standard. So, I dropped the idea of using the original problem. I thought, why not have a constructive problem revolving around my solution? Bonus: How can we use the solution to this Codeforces problem to solve the tree task? |
| 38 | Feb 2023 | Divisible Subarray Counting | Div 2 D | Codechef Starters 78 | |
| 39 | Feb 2023 | Not Divisible | Div 2 A | Codechef Starters 76 | |
| 40 | Feb 2023 | Expected Value | Div 2 D | Codechef Starters 76 | |
| 41 | Feb 2023 | Counting Is Fun | Div 2 E | Codechef Starters 76 | Nice problem. The original version of this problem was proposed as Div 2 C for the Codeforces round 838. It was removed when I found a better candidate for problem C. The original problem was: You are given two binary arrays $$$A$$$ and $$$B$$$, each of length $$$N$$$. Find $$$F(A,B)$$$. |
| 42 | Apr 2023 | Maximise Score | Div 2 A | Codechef Starters 86 | |
| 43 | Apr 2023 | String Game | Div 2 A | Codechef Starters 86 | |
| 44 | Apr 2023 | Largest Y | Div 2 B | Codechef Starters 86 | |
| 45 | Apr 2023 | Minimum Operation | Div 2 C | Codechef Starters 86 | |
| 46 | Apr 2023 | Least Size | Div 2 D | Codechef Starters 86 | |
| 47 | Apr 2023 | Sum Over All Arrays | Div 2 E | Codechef Starters 86 | Nice counting problem |
| 48 | Apr 2023 | Prefix Max | Div 2 F | Codechef Starters 86 | My opinion on the problem |
| 49 | Apr 2023 | Trees Are Fun | Div 1 D | Codechef Starters 86 | I think it is a really nice problem. While trying a problem in some Universal Cup contest, I came up with an interesting idea, which seemed overkill for that problem. I decided to have a problem revolving around that idea, as I liked it a lot. It is a pity that some inefficient solutions were able to pass the tests. |
| 50 | May 2023 | Printing Binary Array | Div 2 A | Codechef Starters 90 | |
| 51 | May 2023 | Anti Palindrome | Div 2 A | Codechef Starters 90 | |
| 52 | May 2023 | Finding Sum | Div 2 E | Codechef Starters 90 | Nice problem |
| 53 | May 2023 | Good Subarrays | Div 2 E | ICPC Algo Queen 2023 Finals | It was proposed as Div 2 E for Codeforces round 825, but ended up being unused. I came up with this problem by misreading one of the problems in Google Code Jam Qualification Round 2022. |
| 54 | Sept 2023 | Combinatorics Is Fun | Div 2 F | Codechef Starters 90 | I was looking for a second last problem of rated for all Starters. yan.silva sent me a problem. His version was to find $$$F(S, X)$$$ if you are given $$$S$$$ and $$$X$$$. It seemed a bit easier for the position I was looking for. I thought that if we can introduce counting into it, it will be hard as well as interesting enough to be the second last problem of Div 1. |
| 55 | Oct 2023 | Maximise Sum | Div 2 A | Codechef Starters 104 | |
| 56 | Oct 2023 | Lexicographically Largest | Div 2 B | Codechef Starters 104 | |
| 57 | Oct 2023 | Construct An Array | Div 2 C | Codechef Starters 104 | Cute problem |
| 58 | Oct 2023 | Find Diameter | Div 2 D | Codechef Starters 104 | |
| 59 | Oct 2023 | Longest Non Decreasing Subsequence | Div 2 E | Codechef Starters 104 | Cool problem |
| 60 | Oct 2023 | Combinatorics Is Fun | Div 1 D | Codechef Starters 104 | Educational problem |
| 61 | Dec 2023 | Maximum Score | Div 2 A | Codechef Starters 113 | |
| 62 | Dec 2023 | Minimise Maximum Subarray Sum | Div 2 B | Codechef Starters 113 | Pretty nice problem. This was proposed as Div 2 A for think-cell round 1. As it was quite hard for position A, it was not approved. In retrospect, I should have replaced think-cell B with this problem. |
| 63 | Dec 2023 | Count Distinct Arrays | Div 2 D | Codechef Starters 113 | |
| 64 | Dec 2023 | Score Sum | Div 2 C | Codechef Starters 113 | Cute problem. |
| 65 | Dec 2023 | Make All Equal | Div 2 C | Codechef Starters 113 | |
| 66 | Dec 2023 | Maximise The Minimum | Div 1 C | Codechef Starters 113 | Nice problem. |
| 67 | Dec 2023 | Counting Is Fun | Div 1 D | Codechef Starters 113 | One of my best problems. An easy version of this problem was proposed for think-cell round 1, but it did not end up being used. |
| 68 | Dec 2023 | Trees Are Fun | Div 1 E | Codechef Starters 113 | I think it is a good problem. I thought it is not that hard, but standings say otherwise. |
| 69 | Jan 2024 | Counting Is Fun | Div 1 D | Codechef Starters 115 | It was also proposed for thinkcell round 1. It was kept as a reserve. I thought we had enough problems around similar difficulty for the think-cell round, so I decided to use it on Codechef. |
| 70 | Feb 2024 | Count Subarrays | Div 2 B | Codechef Starters 120 | |
| 71 | Feb 2024 | Count Arrays | Div 2 B | Codechef Starters 120 | |
| 72 | Feb 2024 | Find Permutation | Div 2 B | Codechef Starters 120 | Cute problem |
| 73 | Feb 2024 | Construct Permutation | Div 2 B | Codechef Starters 120 | |
| 74 | Feb 2024 | Minimum Operations | Div 2 E | Codechef Starters 120 | I think this problem is pretty nice. Bonus: Come up with proof for your solution. |
| 75 | Feb 2024 | Trees Are Fun | Div 1 D | Codechef Starters 120 | I like this problem too. |
| 76 | Feb 2024 | Maximise The Score | Div 2 A | think-cell Round 1 | I wanted to change this task. But I could not get a better candidate. |
| 77 | Feb 2024 | Permutation Printing | Div 2 B | think-cell Round 1 | It is also possible to solve this for an arbitrary array $$$A$$$ containing $$$n$$$ distinct positive integers. |
| 78 | Feb 2024 | Lexicographically Largest | Div 2 C | think-cell Round 1 | I came up with the original problem on a night walk. The original problem seemed a bit standard. So, I modified it a bit and came up with this version. I really like this problem. But somehow, not many people like this :( |
| 79 | Feb 2024 | Sum over all Substrings | Div 2 E | think-cell Round 1 | Cool problem. Bonus: Prove your solution for this problem. |
| 80 | Feb 2024 | 2..3...4.... Wonderful! Wonderful! | Div 1 C | think-cell Round 1 | One of my best problems. Initially, I came up with $$$k=1$$$ version and discussed it with Non-origination. We both liked it. After some time, I realized we could solve the construction problem for arbitrary $$$k$$$. At that time, I thought counting portion might not be possible for large constraints and abandoned the problem. The next day, I suddenly came up with a cool solution. I coded it and verified it with a brute-force solution. I liked this problem and found it non-trivial as well. Later, I came to know that much simpler solutions exist as well. |
| 81 | Feb 2024 | Maximize the Difference | Div 1 D | think-cell Round 1 | I think it is that kind of problem which you either solve in less than 15 minutes or struggle for a long time. |
| 82 | Feb 2024 | Prefix Max Set Counting | Div 1 D | think-cell Round 1 | One of my best problems. We received an overwhelming response on this problem. Among all the problems that I authored, I think this is the problem that the participants liked the most. |
| 82 | Feb 2024 | Interactive Mex Tree | Div 1 E | think-cell Round 1 | Here is the background story behind this problem. So we(me and amurto) were discussing how to find the mex of some path of tree efficiently in April 2022. At that time, I did not know HLD. I came up with a solution($$$O(n \log(n))$$$). It was proposed for Codeforces round 838. I later came to know that it can be bashed with HLD to solve in $$$O(n \log^2(n))$$$ time. So, I made the problem interactive to cut the HLD solutions. |
| 83 | Feb 2024 | Counting In Fun | Div 1 F | think-cell Round 1 | I like this problem a lot. This problem motivated me for the setup used in Counting In Fun. Huge thanks to Elegia for helping me to solve this problem. |
| 84 | March 2024 | Equal XOR | Div 2 B | Codeforces Round 934 (Div. 2) | This problem was originally proposed for think-cell round 1. |
| 85 | March 2024 | Counting Is Fun | Div 1 D | Codeforces Round 934 (Div. 1) | This problem was originally proposed for think-cell round 1 too. My solution exploited the necessary and sufficient condition to solve it. But some testers solved it using standard techniques and didn't like it that much. So it was removed from the problemset. I proposed the counting task when the coordinator asked for some Div 1 C level problems to bridge the difficulty gap. |
| 86 | March 2024 | Minimum Hamming Distance | Div 1 F | Codeforces Round 934 (Div. 1) | One of my best problems. Here is the background story behind this problem. Have a look at this problem first. Initially, we were asking to find the value of $$$F(s[1,n])$$$, and it was intended to be used as Div 2 C. At that time, we were looking for some Div 1 C-level problems. So I proposed this problem(exact statement of Minimum Hamming Distance, but with $$$1 \le n \le 10^6$$$). At that time, I thought the greedy solution would work. When I stress-tested my greedy idea against brute force, I found out that my greedy idea was wrong. I solved the problem in $$$O(n^2)$$$ later on. We(me and errorgorn) tried to solve this problem in subquadratic time. But we didn't succeed. I underestimated this problem a bit. I thought it was Div 1 E difficulty, and I wanted to use it as problem H in think-cell round 1. But this problem was not used, as problems D and I of that round had the same setups. |
satyam343 orz!
An Epic History in authoring !
how much money you have made by writing these 86 problems?
Maybe around 3500 dollars(including the compensation for the think-cell round, which I am yet to receive)
How do you come up with such high level counting problems so often ?, Also how do you know if the solution always exists ?
He solves it.
[It may seem like a joke, but genuinely, most of the time (unless you constructed the problem backwards from the solution) you need to solve your problem yourself, unless you have high rated friends/testers]
How do you come up with such high level counting problems so often ?I think experience in problem-setting helps a lot. Also, I believe I have a good grasp of counting problems, which makes it easier to come up with new ideas or modify existing (or standard) ones to make them interesting.
Also how do you know if the solution always exists ?I try out ideas for some time. When I realize that I'm making no progress, I abandon the ideas. Gut feeling also helps sometimes. Sometimes, I tweak the problems(ensuring that the problems don't get too artificial) to make my solution work.