[Unofficial] Educational Codeforces Round 161 Editorial (tasks A-E)

Правка en3, от stefdasca, 2024-01-19 17:39:19

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)

1922A - Tricky Template

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 - Forming Triangles

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

1922C - Closest Cities

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

1922D - Berserk Monsters

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

1922E - Increasing Subsequences

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

1922F - Replace on Segment

to be added

Теги editorial, tutorial, explanation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский stefdasca 2024-01-19 18:04:44 2 Tiny change: 'rray into 2 parts is ' -> 'rray into $2$ parts is '
en6 Английский stefdasca 2024-01-19 18:04:28 1 Tiny change: '}$ and $dp_{(l, r, y' -> '}$ and $dp2_{(l, r, y'
en5 Английский stefdasca 2024-01-19 17:55:25 360
en4 Английский stefdasca 2024-01-19 17:53:24 1675
en3 Английский stefdasca 2024-01-19 17:39:19 94
en2 Английский stefdasca 2024-01-19 17:25:38 96
en1 Английский stefdasca 2024-01-19 17:23:52 4629 Initial revision (published)