(click on the thumbnail to watch a YouTube video)
Welcome back to "better than tourist" week. Keep reading, and you'll find out what this is all about!
Contests
This week I took part in 7 contests:
two rated: HackerEarth's DSA and LeetCode's Weekly;
five unrated: CF Div. 3 (AK), two CF Div. 2 (both all but one problems), Atcoder Beginner (A-G), yukicoder (AK).
Both rated contests went well. I am now ranked above tourist on HackerEarth and surpassed the 2700 mark on LeetCode.
(HackerEarth's rated contests leaderboard)
All unrated events were also good. I solved all problems in CF Div. 3 and yukicoder. I also figured out everything but one task in two CF Div. 2 rounds. AtCoder's Beginner contest was a bit more questionable because I couldn't solve either of the two last problems, but I still felt good about it.
Besides that, I also did virtual last week's LC and got first place (too bad they hold contests at 5 am and not pm my time).
Technically speaking, I also attempted unrated CodeChef's Starters, but it was straight after a challenging CF Div. 2. My head ached like hell, so I quit ten minutes into the contest, so I don't count it in the stats.
I finished the week off with a team contest with Denys dendi239 Smirnov — an extraordinary teammate and admirable person!
Problems
Overall, there were 45 problems. I solved 41 of them in-contest, which shows that this week was more leisurely than the previous one. I also upsolved 3 of the remaining ones, letting aside only the last problem from one of the CF Div. 2s.
Let me walk you through the problems I upsolved. I feel like I learned the most from them, and not nearly as much from the ones I solved in-contest. In Um_nik's terms, these were the problems directly above my interesting interval, and upsolving them makes this interval move up.
With all that in mind, let's jump straight into the superfast practice session!
Practice session
First, we have a combinatorics problem G — Gardens AtCoder Beginner Contest. We need to precompute factorials and inverse factorials in such problems. It lets you compute binomial coefficients in constant time. I even got an idea of the inclusion-exclusion formula, which was enough for a quadratic solution. Unfortunately, I didn't notice that we can speed things up with a recurrence relation. It is not difficult at all. I guess I have to solve more combinatorics not to miss such trivial "grid"-like relations. 28607190
Next up, there was a brilliant CF problem 1627F - Not Splitting. I got the general idea about the graph right. Then I started thinking about minimum cuts, but it was not the way to go. This problem is, in fact, about the shortest paths from the center of the board to the boundary. It follows from the fact that each cut should be centrally symmetrical about the center of the square. Once you notice it, the problem becomes a simple implementation. 143221640
Finally, let's look at problem H — Painting Weighted Graph from the same AtCoder contest. This problem is dynamic programming on graphs. The first massive obstacle you had to overcome to solve it was to notice that it is useless to operate on most graph edges. Indeed, only the links in a minimum spanning tree are necessary. Try to figure out why if you feel comfortable with MSTs. However, once you notice it, it becomes clear that we want to compute some dp on connected components and merge them with DSU. It takes some time to figure out the exact transitions when you combine several parts simultaneously, but ultimately the problem is solved. It may look like complexity is $$$O(NK^2)$$$, but it is $$$O(NK)$$$. You may perform a case analysis on the sizes of components that we merge to see that large merges are rare enough. 28621556
I wish everyone a great time and see you next week! (＾▽＾)
Comments (0)
