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
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
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, 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
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)$$$.
Solution code: 242417965
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
to be added
