(click on the thumbnail to watch a YouTube video)

Welcome back! Writing this blog feels a bit odd, almost as if I'm starting all over again. For many people, this is what the New Year is all about — a fresh start.

You are probably wondering what I've been doing during this spontaneous break. There is no simple answer to this question, as I was busy with numerous tasks: job, university, and the ICPC season.

New, Slower Pace

Last time I've set the pace pretty fast, releasing multiple videos a week. While taking part in several contests every week is simple, recording screencasts and explanations is not. Because of that, I want to take things slower. Let's first make it a weekly routine. Once we get there, I'll assess how we can proceed.

Google Calendar

I've set up a google calendar to keep track of some contests. You can subscribe if you want to get a rough idea of when to expect a new video. I don't promise to cover every contest on that list, but I will keep it updated and synced with my other activities.

Practice Session

Over the weekend, I solved five problems that I would like to present:

1. I started with a dynamic programming problem from CodeForces: 587B - Duff на пляже . You are given a super long sequence which is a repetition of some smaller array, and you want to count short non-decreasing subsequences. The dynamic programming approach comes from the product constraint. Unfortunately, I spent a lot of time debugging this problem. You can see me trying to change some random bits of the code. Writing down the definition of the dp instead would've helped a lot. 141317398

2. Next up, an ad-hoc problem from AtCoder: ARC 94C — Tozan and Gezan. I spent an hour on it, trying different approaches but still could not figure it out and had to look up the editorial. It appears that I need more practice with ad-hoc problems. 28282329

3. Last for Saturday was a constructive problem from CodeChef: Dec'21 Cook-Off — RGB Construction. I started with some creepy casework but eventually arrived at a better solution. It involves "bipartite" graphs and works for all cases. 55694320

The following problems are from the next day:

1. First, I did a pleasing "geometry" problem on CodeForces: 576C - Точки на плоскости. In this problem, you are given some points and you want to construct a reasonably short Hamiltonian path. After investigating the meaning of "reasonably short" I quickly got some square-root ideas. I had one small off-by-one bug and a minor mistake in the approach but fixed them quickly. I should watch out for such errors. 141416899

2. I proceeded with an AtCoder problem: ABC 128E — Roadwork. Here you are given several people walking on the number line and a series of roadworks that may stop them. Each person starts at their own time and each roadwork blocks some point during some time interval. You need to find where each person will stop. I call ideas related to the time intervals "event processing." Each time interval constitutes two events, the beginning and the end of the segment. In this case, the events are also shifted by their position. Initially, I wanted to overkill this problem with a segment tree (each roadwork stops some range of start times, hence I need to min-assign on segments). Luckily, I soon realized how to solve it without one. 28300315

Thank you all for reading! Hope to see you next time around! ^_^