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.