(click on the thumbnail to watch a YouTube video)
Welcome back to what I called "ds in dp week", and you'll see in a second what this is all about. But first I wanted to share some stats with you:
Contests
This week I took part in 7 contests. Four of them are rated for me, and in the remaining three, I participated unofficially.
I took second place in the Hacker Earth's Easy competition, got on the first standings page of LeetCode Biweekly Contest 69, and had my best TopCoder performance so far, which saw 164 points rating increase.
Codeforces' Hello 2022 didn't go so well, with me managing to solve only A-D. Luckily I only got -15, a surprisingly forgiving rating change for an underperformance.
The remaining three competitions were unrated for me, so I didn't pay much attention to them. It partially explains my questionable results on CodeChef Starters 21, AtCoder Beginner Contest 234, and yukicoder contest 326.
Saturday was a busy day for me, featuring a total of four competitions. I managed to get a refreshing walk in-between but still was too tired to wake up at 4:30 a.m. on Sunday for LeetCode Weekly Contest 275.
I think 7 contests a week is as far as it gets for me if I want to upsolve a reasonable portion of all the problems I see.
Problems
There were 44 problems in total. I solved 32 of them in-contest and upsolved nine more. I am yet to solve the most difficult two from the Hello 2022 Codeforces round and a challenging TopCoder problem.
The topic I had most difficulties with this week is dynamic programming with data structures. We will see not one but two such examples in the upsolving timelapse.
Surprisingly, I also missed several mathematical observations in a couple of problems. It is something that I thought I had covered by my high school math olympiad experience. Apparently, progress is still possible in how quickly and naturally I arrive at such observations.
With that in mind, let's jump into a superfast practice session.
Practice Session
We'll start off with problem G from CodeForces' Hello 2022. It is rated 3200, but trust me, it is not that difficult, with the main ideas being crystal clear. First, we notice that we want to compute a double sum. It is a standard idea to change the order of summation. Hence we'll calculate how many sequences each element contributes to. Second, we observe that conditions under which we count given array entry lead to easy quadratic dynamic programming. Last, it is common to optimize such dp to O(n log n) by using some data structure. In our case, Fenwick Tree helps a lot, as our dp essentially sums up a range of values. The implementation gets simpler if we replace the array with a permutation, adding indices as tiebreakers. 142311633
Next up, another problem G, this time from AtCoder Beginner Contest. In this problem, we have to optimize another quadratic dynamic programming. First, we observe that each dp value is a linear combination of the previous ones. Second, the coefficients are suffix minimums and maximums, which can be efficiently updated with monotonic stacks. The implementation may get messy, but the ideas should be transparent. 28442072
Finally, we have a fancy problem H (Ex) from the same contest. Here we are given a set of plane points, and we want to find all close pairs. The first reaction is that it is impossible to do faster than in quadratic time, as all points can be "close." The statement guarantees a limited number of close pairs to address this issue. Hence we need an algorithm with complexity proportional to the answer size, a rare thing to see in my experience. Funnily enough, such an algorithm arises from simply grouping points into close squares. There is also a randomized approach, but I prefer the grouping solution. 28441485
Finishing thoughts
So far, I am satisfied with how it is going. Unfortunately, next week I'll have a bit more work to do. Hopefully, I will still find time for many contests, at least on the mainstream platforms.
