satyam343's blog

Problems that I authored so far
By satyam343, 8 months ago, In English

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.
  • Vote: I like it
  • +268
  • Vote: I do not like it

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

satyam343 orz!

→ Reply
»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

An Epic History in authoring !

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how much money you have made by writing these 86 problems?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Maybe around 3500 dollars(including the compensation for the think-cell round, which I am yet to receive)

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you come up with such high level counting problems so often ?, Also how do you know if the solution always exists ?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    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]

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply