Since the editorial is still unpublished yet as I was writing this blog, I decided to write an editorial for the problems that were given at yesterday's contest. For tasks A-E I also published video editorials (A-C, D-E)
In order to solve this problem, we must observe that each position is independent from each other and it is enough for us to fix only one position in order to see if we can get both $$$a$$$ and $$$b$$$ match the template while $$$c$$$ doesn't. Thus, it will be enough to check if $$$a_i \neq c_i$$$ and $$$b_i \neq c_i$$$ for that to work, as we could then put an uppercase letter and discard $$$c$$$ right away.
Solution code: 242416975
Video editorial: Link
Alternatively, this can also be done in a much more complicated fashion with bitmask dp where $$$dp_{(i, j)}$$$ is $$$1$$$ if we can get a configuration up to position $$$i$$$ such that strings with mask $$$j$$$ match the template, and the answer is YES if $$$dp_{(n, 6)}$$$ is $$$1$$$.
Bitmask dp solution: 242442065
1922B - Формирование треугольников
This problem is based on a very standard problem, which is finding the number of triples that form a triangle. While the original problem is solvable using binary search in $$$O(n^2 \log n)$$$, given that here we have powers of two, we can find an important observation that allows us to reduce the complexity. Namely, we can never have three distinct lengths of sides as this would make the triangle invalid.
In addition, the two equal sides can't be smaller than the third one too as this would also make the triangle degenerate (for example, $$$2^2 + 2^2 = 2^3$$$). Therefore, the equal sides must be the larger ones. Now, we reduced the problem to two cases:
- When all sides are equal, we can just sum up the values of $$$\frac{freq_i \cdot (freq_i - 1) \cdot (freq_i - 2)}{6}$$$ ($$$n$$$ choose $$$3$$$) and that would be the answer.
- When two sides are equal, we can just sum up the values of $$$\frac{freq_i \cdot (freq_i - 1) \cdot sum}{2}$$$ ($$$n$$$ choose $$$2$$$) where $$$sum$$$ is the sum of the frequencies of the smaller sides and that would be the answer.
In order to find the final answer, we can sum up the answers for the two cases which can be speed up using prefix sums.
Solution code: 242416552
Video editorial: Link
The worst case answer for each query is the distance between the two values, but we now want to find out for each query how many times we can reduce the distance by using the $$$1$$$ instead of the actual distance.
Given that the distances never change and it is never optimal to turn back on our journey, we can precompute this information for all suffixes and prefixes in a prefix sum-like manner and this will help us answer the queries in $$$O(1)$$$ time.
Solution code: 242416485
Video editorial: Link
Let's analyze what happens on a round by round basis. If there is no monster who dies, nothing will change anymore and we can finish the game. Otherwise, let's take the monsters that die and find for every monster next to them the new neighbors.
This will be the basis behind implementing the solution for the problem, as we need to simulate the process fast enough. In order to avoid the $$$O(n^2)$$$ complexity, we need at each step to only deal with the monsters that were killed in the previous round and the adjacent monsters, in order to see if there are any new monsters that could die in the next round. In order to keep track of the new adjacent monsters, we can either use sets or use a linked-list like approach, where for each position we store the previous and the next value, and when we kill monster $$$x$$$, if we knew $$$prev_i$$$ and $$$nxt_i$$$, they will become the new previous/next for each other now.
The solution can now be implemented in $$$O(n \log n)$$$ or $$$O(n \log^2 n)$$$.
Bonus: can you solve this in $$$O(n)$$$?
Solution code: 242417965
Video editorial: Link
1922E - Возрастающие подпоследовательности
Let's start from a very important observation. Every increasing array has all of its $$$2^n$$$ subsequences increasing, where $$$n$$$ is the length of the array. Therefore, we can start the solution with an array like $$$1 \ 2 \ ... \ \log n$$$, which will have $$$2^{\lfloor \log n \rfloor}$$$ increasing subsequences. Now, in order to continue creating subsequences, we can basically rely on the binary representation of $$$k$$$ and if at some step we add $$$2^x$$$ subsequences, we can append at the end a value equal to $$$x+1$$$. Now, we need to be careful to add the new values in decreasing order in order to avoid generating new subsequences.
The final complexity will be $$$O(\log K)$$$ as we need to find the powers of two to add to the array.
Solution code: 242418015
Video editorial: Link
Credits to Dominater069 for writing this solution
In order to solve the problem we can use range dp, but the way to think about it is not very obvious at the first glance. While it seems somewhat obvious that we need to do something around this concept, the states are not very easy to define.
As we usually go about in range dp, assume that we know the answer for a range $$$[l, r]$$$ and try to update larger ranges using smaller ranges information. Let $$$dp_{(l, r, k)}$$$ be the minimum number of moves we need in order to make every value in the subarray $$$[l, r]$$$ equal to $$$k$$$. Now, again using standard range dp thought process, in some optimal solution for a range $$$[l, r]$$$, we divide the subarray into $$$2$$$ parts (namely a prefix and a suffix) where we do not overlap prefix and suffix operations, with the exception of using an operation on the whole subarray $$$[l, r]$$$.
Now, here is finally the slightly tricky part. It's not possible to tell whether we can operate on the whole range $$$[l, r]$$$ with just our $$$dp_{(l, r, k)}$$$. So, we define another auxiliary dp state, let $$$dp2_{(l, r, k)}$$$ be the minimum number of moves in order to make every value in the subarray $$$[l, r]$$$ not equal to $$$k$$$. Transitioning for splitting the subarray into $$$2$$$ parts is simple and standard. Assume that we now use an operation with set to $$$x$$$ for the subarray $$$[l, r]$$$. Then, we need to update $$$dp_{(l, r, x)}$$$ and $$$dp2_{(l, r, y)}$$$ with $$$dp2_{(l, r, x)} + 1$$$ (if $$$y \ne x$$$). Implementing these transitions directly, we get a $$$O(n^3 \cdot x)$$$ solution, which is sufficient to pass comfortably.
Dominater069's solution code: 242258097
