Little Elephant and Retro Strings is an old problem. The intended solution is to use some intelligent grouping. I won't discuss it here because it's not relevant (and also to avoid spoiling), but you can read the details in the editorial. However, getting the right grouping idea is sometimes difficult, especially in problems with multiple parameters. Hence, I decided to go with a naive DP:

dp[progress][color][length] is the number of strings with a suffix of given color and length. Here progress is 0 if we haven't seen "B...B" before, 1 if we have seen "B...B" but not "W...W", and 2 if we have seen both. The answer is the sum of dp[2]. Notice that our position in the string is not a part of the state because we process the updates in place.

How do we process updates in such a dp? When appending a 'B', all strings ending with 'W' terminate, and all strings ending with 'B' get one longer. Since amortized analysis applies here, the strings that terminate can be processed with a naive loop. However, strings that get one longer seemingly require moving all values in our dp by one position. Fortunately, we can do this in O(1) if we use a queue (or a deque) to store our dp values. Instead of moving all values by one, we can just prepend a 0 to our dp. Appending a 'W' follows the same process.

However, when considering an 'X', we cannot use amortized analysis because we cannot erase values. This is because every string has a valid continuation: strings ending with 'W' can get another 'W', and strings ending with 'B' can get another 'B'. Therefore, we need to speed up the updates where the last color changes. Specifically, such updates require us to increment dp[progress][!color][1] by the sum of dp[progress][color]. Therefore, it is sufficient to introduce another dp: sum_dp[progress][color] = sum(dp[progress][color]). There is only a constant number of transitions, so maintaining sum_dp is not an issue either.

You can examine my submission for details. I may clean it up if I get some free time. I've been inspired by this excellent video. The takeaway is that using alternative data structures for your DP can speed up certain operations. Shifting the DP by one is just one example of what one may achieve with it.

Ratings

It's always nice to see them growing.

• codeforces: 2311 + 21 = 2332
• atcoder: 2024 + 29 = 2053
• leetcode: 2701 + 81 = 2782
• dmoj: 2161 + 197 = 2358
• prepbytes: 1853 + 79 = 1932

Contests

A contest a day keeps mental health away.

• rated: 11
• unrated: 14
• fullsolve: 12

Problems

One downside of many contests is that you don't have time to upsolve properly.

• solved: 145
• upsolved: 5
• todo: 23

Hardest problems that I solved in-contest:

• CF #779 E — Gojou and Matrix Game
• ABC 245 G — Foreign Friends
• CC Start 32 — Avoid Alternating
• PB PT P5 — Kevin and his Operation

Easiest problems that I failed to solve in-contest:

• ARC 137 C — Distinct Numbers
• CF #779 D2 — 388535 (Hard Version)
• CC Start 28 — Interactive Tree
• DMOPC P4 — Rocket Race

Most educational blogs (my to-read list):

• Binary lifting
• Little tricks
• Sparse table
• Segtree dp
• Tree diameter
• Flows

Some performance pics

Intense calendar pics

Don’t ask questions, upvote!

(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

1. 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

2. 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

3. 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! (＾▽＾)

(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

1. 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

2. 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

3. 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.

(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 in Beach . 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 - Points on Plane. 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! ^_^

Yesterday my 2021-22 ACM season came to an end at SEERC. Team KNU_LL consisting of giraffeh, MStrechen, and myself solved 8 problems and took place #12 (and even got an honorable mention, complete results). It was the last ACM season for us, and now the boys want to focus on career and personal life, a decision which I respect and support.

However, I want to keep going with competitive programming, simply because I enjoy solving problems in a good company. Let me know if you are a competitive programmer living in Kyiv and want to participate in some OpenCup contests. The next one is the Grand Prix of Poland which will take place on December 5th.

I was upsolving AtCoder Beginner Contest 195 problem F, aka "Coprime Present" where you need to count subsets (of a special set of size < 72) with pairwise coprime elements.

My solution is a bitmask dp over prime factors that were used and a prefix of the set. My first submission.

Fairly straightforward, nothing smart, $$$O(N \cdot 2^n)$$$ time and memory. However, I was disappointed by the memory usage of 600+ Mb. Therefore, I implemented a two-layer version of the same dp. Here is my second submission.

The difference is minimal, I just take layer_number & 1, and don't forget to clear the previous layer before proceeding to the next one

Obviously, it uses way less memory, only 30 Mb. What surprised me is that the running time has also decreased, from 472 ms to just 147 ms, for an improvement by a factor of 3!

I have two hypotheses on why this happens:

• two layers fit into the better cache level, facilitating memory lookups;

• memory allocation itself takes some time (there must be a reason why people write custom allocators, right?).

Can someone more experienced please tell me what actually happens there?

Interactive problems are still a new topic which confuses many participants. Recently I failed to solve some of the interactive problems during contests, so I decided to practice this kind of question. For this purpose, I put together a mashup with 12 problems per 5 hours, with difficulties from Div 2 B to Div 1 C. You can upsolve the problems at your own pace.

my solutions on github

UPD: video editorial live in 15 minutes:

It's been a while, but we are back with another Codeforces Gym!

Translated statements and my solutions are here, and statements are also added to the gym itself.

Today I will talk about various problems involving range queries in general, and segment trees in particular.

First, I describe simple problems with range queries, such as sum/min/max on a segment without any updates. It is essential to understand that sometimes you don't need any advanced data structures to process range queries. In some problems, you can write a for loop, use prefix sums, or precompute a sparse table. However, when update queries come into play, the need for better data structures arise, and here segment tree, and lazy segment tree come into play. Their applications can seem practically unlimited, but at the very end, we realize that there are some limitations. Because of that, we introduce our final data structure, which supports Split and Merge operations.

Watch the theory here, or skip straight to the practice session if you already know the theory.

Later today we'll have CF Round #698, and one of the problem-setters is triple__a. I could not help but notice that he already has set problems for one contest, so I decided to give it a try and participated in a virtual contest. It was a Div. 2 Round # 630, but I still think you can make some useful observations. You can watch mine in the YT video.

tl;dr

Be careful with constraints, some of them are unnecessarily tight, in my opinion. Topics are standard: three implementation problems for div. 2 only, some number theory and combinatorics, dp on a tree, and later more advanced stuff. There was also an unusual problem about finding the bug in the given code.

General observations

The modint class helps a lot, and you should have it. A good sleep schedule is crucial. Do not write contests straight after you wake up after a short sleep, or at least be very careful. Finally, you can save a lot of time if you just keep solving problems instead of complaining about them :upside_down_face:

my solutions on github, variable names are mostly reasonable so that you can read it alongside explanations. The screencast with video editorial is coming soon on my YT channel

A. Odd Divisor

A number has an odd divisor iff it is not a power of two.

B. New Year's Number

$$$2020 x + 2021 y = n$$$. Mod out by $$$2020$$$, you get $$$y = n \% 2020$$$. Then simply check that $$$x = (n - 2021 y) / 2020$$$ is nonnegative.

C. Ball in Berland

We have a bipartite graph. All pairs of pairs are good except for the pairs that share a common vertex. There are $$$\binom{k}{2}$$$ pairs in total and $$$\binom{\deg v}{2}$$$ pairs that share a vertex $$$v$$$, hence the answer is $$$\binom{k}{2} - \sum_v \binom{\deg v}{2}$$$.

D. Cleaning the Phone

Among the applications of equal importance we want to delete the heaviest ones first, hence it makes sense to sort. We will delete some prefix of important apps and some prefix of regular apps, so it makes sense to compute prefix sums of both. The for every given important prefix we can find the corresponding regular prefix with a binary search because prefix sums are sorted.

E. Advertising Agency

Some bloggers are marginal (equal to $$$k$$$-th in sorted order) and some are not. If a blogger is strictly better than marginal, then we take it, if it is strictly worse then we don't, and among marginal we can choose for the remaining places. The answer will be some binomial coefficient. To compute them quickly you can precompute factorials.

F. Unusual Matrix

If you flip all rows and all columns nothing will change. In linear algebra, such a set of operations is called linearly-dependent. It means that you can exclude one operation wlog. Let's exclude the first column so that we will never flip it. THen judging by its entries we can determine which rows we have to flip. Once we flipped the rows we can determine which columns (except for the first one) we have to flip. Then we check if we succeeded or not.

G. Strange Beauty

dp[i] will count the max number of elements in a good set whose max element is $$$i$$$. Then dp[i] = max(dp[i/d] + f[i] for d|i), where $$$d\mid i$$$ means that $$$d$$$ is a divisor of $$$i$$$, and f[i] is the frequency map of the array. To ind divisors quickly one can run Erathospenes' sieve once.

Takeaways: prewritten NT helps with speed

solutions on github, video on YouTube. Short text solutions:

A. Puzzle From the Future

Greedy: first optimize the length (no consecutive equal numbers), then the individual digits starting from the most significant ones. $$$O(t \cdot n)$$$ overall.

B. Different Divisors

The least prime divisor $$$p$$$ should be at least $$$d + 1$$$. Then the second prime divisor should be at least $$$p + 1$$$. Selecting the least prime number bigger than something is a binary search in the array of primes. The array of primes can be generated with a sieve. $$$O(\max d \log \log \max d + t)$$$ overall.

C. Array Destruction

Each operation should involve max because it can't be removed later. If we know the initial $$$x$$$ then the simulation of this process takes $$$O(n \log n)$$$ with std::multiset or $$$O(n)$$$ with some smart solution from neal. Because the initial value of $$$x$$$ also includes $$$\max_i a_i$$$, it remains to try all $$$n$$$ values of the form $$$a_j + \max_i a_i$$$. $$$O(n^2 \log n)$$$ overall. No $$$t$$$ because $$$n \mapsto n^2 \log n$$$ is convex, and we can apply Jensen.

D. Cleaning

Write $$$a_1 = x_1$$$, $$$a_i = x_i + x_{i - 1}$$$ for $$$i = 2, \dots, n$$$. We want $$$x_i \ge 0$$$ and $$$x_n = 0$$$. If we swap $$$a_i$$$ and $$$a_{i+1}$$$ then $$$x_i$$$ changes by $$$\Delta$$$, and $$$x_j$$$ changes by $$$\pm 2 \Delta$$$ where $$$\Delta = a_i - a_{i+1}$$$, and the sign depends on the parity of the position. We therefore can process the array in reverse, maintaining the suffix min of odd positions and even positions and checking several conditions. Note that we also need all negative $$$x_i$$$ to be on the suffix, because prefix does not change when swapping $$$a_i$$$ and $$$a_{i+1}$$$.

E. What Is It?

This is a somewhat tricky construction problem. I could not figure out the exact construction during the contest but had some close ideas, and fixed my solutions shortly after. The general idea is to maximize the number of long swaps (you'll get one swap of length $$$n - 1$$$, two swaps of length $$$n - 2$$$, two swaps of length $$$n - 3$$$, etc). It is also very convenient to construct the permutation in reverse.

My solutions on GitHub

A. Replacing Elements

The minimum value that an element can get is the sum of the two smallest elements of the initial array. Constraints allowed to find such pair in $$$O(n^2)$$$ by brute force. One can also sort the array in $$$O(n \log n)$$$ and take a[0] + a[1]. However, the optimal method to select $$$k$$$ min elements is, of course, a heap with a size limit of $$$k$$$ elements which performs this job in $$$O(n \log k)$$$. We then change every element to this value if such a change reduces it, and compare against the limit.

B. String LCM

We have to print the lcm anyways, so we can just generate it by looping over two string simultaneously with a pair of indices. If lcm exists then its length is the lcm of lengths of the two strings, hence it is relatively short. If we encounter a pair of different symbols while iterating then lcm does not exist and we print -1.

C. No More Inversions

If you swap $$$(i, j)$$$ before the maximum element and $$$(j, i)$$$ after it, then the number of inversions does not change. Moreover, it follows that the number of inversions does not change for any set of numbers that are placed like $$$w,x,\dots,y,z,y,\dots,x,w$$$. Therefore, we can take the permutation $$$1,2\dots,a_n-2,a_n-1$$$, $$$k,k-1,\dots,a_n+1,a_n$$$. Finally, we can't change the first part because it is currently sorted, and any change will lead to more than $$$0$$$ inversions.

D. Program

The number of different coordinates is the maximum coordinate minus the minimum coordinate plus one (example: there are $$$3-(-2)+1=6$$$ integers in the range $$$[-2,3]$$$). If we exclude all commands from $$$[l, r]$$$, then what remains is a prefix $$$[0,l)$$$ and a suffix $$$(r,n)$$$. It now makes perfect sense to compute max and min on all prefixes and all suffixes, along with the current coordinate after every prefix. From here with the help of some drawings, we can restore min and max as follows:

min = min(prefix_min[left - 1], prefix_current[left - 1] + suffix_current[right] - suffix_max[right])
max = max(prefix_max[left - 1], prefix_current[left - 1] + suffix_current[right] - suffix_min[right])

Here index $$$0$$$ corresponds to the empty prefix/suffix.

E. Minimum Path

Every edge can turn out to be min-, max-, or a regular edge. weight of min-edge is twice the weight of the regular edge, and the weight of max-edge is 0. Each path may use at most one edge as its min-edge and at most one edge as its max-edge (a total of four options, according to the product rule). It follows that we can run Dijkstra on the graph with $$$4n$$$ vertices, but for the answer, we only consider paths that use both min and max-edge (or use neither, which can happen for paths of length 1).

F. Strange Set

It is an interesting problem that can be reduced to maximum flow. UPD: I changed my opinion about Dinic. First, it is not all that hard, and second, I actually had it in my library, I just forgot where it was. Added solution to github

G. Tiles

Hello $$$998'244'353$$$ my old friend. It is unlikely that you will implement NTT in half an hour that remains after you solved first six problems, so it is basically impossible unless you have NTT in your library, and hence not a good fit for Div. 2 Round. On the other hand, if you do then the problem is rather straightforward, which makes it not a good fit Div. 1 Round. Therefore we see it in Educational Round, popularizing the idea of NTT among lower-rated participants, and reminding higher-rated ones that they should add it to their library.

Overall, I think that this educational round was very good for the purposes of educating people about standard techniques, and problems were used wisely.

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one somewhat advanced gym that I want to cover today, and the reason is that it is only available in Russian :| Or should I say "was" instead of "is"? :D

I translated the statements to English and added them to the contest materials. As usual, I also recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

First I describe the LCA problem itself and explain the binary lifting approach to solve it in $$$\langle \mathcal{O}(n \log n), \mathcal{O}(\log n) \rangle$$$. I then reduce LCA to RMQ, and use Sparse Table to solve RMQ in $$$\langle \mathcal{O}(n \log n), \mathcal{O}(1)\rangle$$$ afterwards. I also give a short preview of Farach--Colton and Bender's $$$\langle \mathcal{O}(n), \mathcal{O}(1)\rangle$$$ algorithm. Finally, we solve an involved problem where you have to find bridges before finding LCA in the condensation graph.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

Problems, my solutions, YT link

A. Three-Point Shot

The team behind has min(x, y) points, and the team ahead has max(x, y), so we can check if min(x, y) + 3 > max(x, y).

B. Orthogonality

Just compute inner product according to the given formula. Use int64_t if you are as paranoid about overflows as I am :)

C. ABC Tournament

Two finalists are max of their halves, so left = max(a[:middle]) and right = max(a[middle:]). Second place is min of finalists.

D. Snuke Prime

All these interval processing problems can be solved in the same way, by splitting each interval into two events: start and end. After sorting events we can process them in a sequential fashion, maintaining the current daily cost.

E. Peddler

DP on DAG, which is already conveniently represented in its topological sort order. Create a dp storing min price at ancestors, and update it along the edges of the graph.

F. +1-1x2

Solve problem backwards: try to get from $$$y$$$ to $$$x$$$ with $$$\pm1$$$ and $$$/2$$$ operations. If we make at least one $$$/2$$$ operation, then it is reasonable to make at most one $$$\pm1$$$ operation before each $$$/2$$$ operation. Therefore, we can write a recursive solution as follows:

• base cases are $$$x \ge y$$$, with $$$x - y$$$ operations, and no $$$/2$$$ operations with $$$y - x$$$ operations;

• if $$$y$$$ is odd then take min with $$$2 + \text{solve}((y-1)/2)$$$ and $$$2 + \text{solve}((y+1)/2)$$$;

• if $$$y$$$ is even then take min with $$$1 + \text{solve}(y/2)$$$;

It works in logarithmic time if you cache answers, because on each layer we have only two consecutive numbers: $$$\{2k, 2k+1\} \mapsto \{k,k,k+1\} = \{k,k+1\}$$$, and $$$\{2k-1,2k\}\mapsto\{k-1,k,k\}=\{k-1,k\}$$$.

CF seems to be the most reasonable place to post about AtCoder, as there are no blogs on AtCoder itself, so here we go.

Problems, my solutions, YT video.

Short text editorial:

A. If $$$10^N = A \cdot M^2 + B \cdot M + C$$$ then answer is $$$B$$$, and it remains to compute $$$10^N \pmod{M^2}$$$ with binary exponentiation.

B. Cards form a graph. Connected components can be optimized independently. We can take all vertices from a component iff it is not the tree. Otherwise, we can take all vertices but one.

C. Every permutation is a product of cycles. Process people in the increasing order of weight. Every cycle (and hence the entire permutation) will be resolved optimally unless you ran into smth that makes overall permutation impossible.

D. If c[u] > c[v] then we must have u -> v as all vertices reachable from v are also reachable from u. The rest of the graph can be oriented arbitrarily, as long as each connected component of the remaining graph stays strongly connected. One way to do it is to run a series of DFSs.

First of all, apologies for a rather long absence, I was a bit tired after Round #694 (Div. 1) in which I got a significant positive rating change. It is always nice to see your work paying off, but let us get back to business.

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one beginner-friendly gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough, in case you ever get stuck.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

I solved six problems during the contest and had a correct idea for the last one, but only got AC 10 minutes after the contest. I explain my solutions along the way, including the post-contest solution to the last problem. Here is the YT link, and here is the link to my solutions.

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one beginner-friendly gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

YT link. This contest is rated for me, so I am very focused and don't spend much time explaining things :|

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

Also Happy New Year to everyone who will see this on Jan. 1!

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

I guess the title says it all, here it the YT link. Of course, there was a post-contest stream by Neal Wu with the discussion of the solutions, but maybe you will find my explanations useful as well.