### BledDest's blog

By BledDest, history, 8 months ago,

First of all, I would like to thank all testers of the round: Um_nik, IlyaLos, Roms, nuipojaluista, Supermagzzz, Stepavly, hg333. Also huge thanks to co-authors of the contest: Neon, adedalic, vovuh and awoo.

I hope you enjoyed participating in the round!

Okay, now for the editorial itself:

1488A - From Zero To Y

Idea: BledDest, preparation: Neon

Tutorial

1488B - RBS Deletion

Idea: BledDest, preparation: BledDest

Tutorial

1488C - Two Policemen

Idea: vovuh, preparation: vovuh

Tutorial

1488D - Problemsolving Marathon

Idea: vovuh, preparation: awoo

Tutorial

1488E - Palindromic Doubles

Idea: BledDest, preparation: awoo

Tutorial

1488F - Dogecoin

Idea: BledDest and Neon, preparation: Neon

Tutorial

1488G - Painting Numbers

Idea: Neon, preparation: Neon

Tutorial

1488H - Build From Suffixes

Idea: BledDest, preparation: awoo

Tutorial

1488I - Demonic Invasion

Idea: BledDest, preparation: BledDest

Tutorial

1488J - Flower Shop

Idea: BledDest, preparation: Neon and adedalic

Tutorial

• +63

 » 8 months ago, # | ← Rev. 2 →   0 The solution codes will be uploaded shortly.UPD: here they are.
•  » » 8 months ago, # ^ |   +13 When will the Random T-shirt winners will be announce?
 » 8 months ago, # | ← Rev. 2 →   +3 Problem E seems to be well-known after you realize that it's the LCS of $a$ and its reverse, and the number of matches between the two strings is in $O(n)$. If the problem is strengthened to having at most $k$ occurrences of each integer, the problem can be solved in $O(k n \log n)$ time.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +5 Wow, nice observation, I just completely overkilled this.
•  » » 8 months ago, # ^ |   0 can you tell name of algo or provide some link for "how to find no of match between two strings in O(n)"
•  » » » 8 months ago, # ^ |   0 To find the number of elements in string $B$ that match with a given element of string $A$, simply do this:Construct the frequency array/map of $B$, and then for each element in $A$, simply read off the number of elements in $B$ that match with it.However, this was not what I meant by the comment above. I meant that if $B$ is the reverse of $A$, the number of matches between $A$ and $B$ (defined as the sum of the elements found in the above algorithm) is upper bounded by some constant multiple of $n$, and if the maximum frequency of an element of $A$ is $k$, then an explicit upper bound is $nk$.In general, if there are at most $m$ matches between two strings, you can figure out an algorithm to find the LCS in $O((m + n) \log n)$.
 » 8 months ago, # | ← Rev. 4 →   +12 1488C - Two Policemen can be solved in $\mathcal{O}(\log n)$ time via binary search.In an optimal solution, the left policeman (at $l$) will visit $[1,m]$ while the right policeman (at $r$) will visit $[m+1,n]$.With this in our mind, we can binary search for the total time.The lower bound is $\max(l-1, n-r)$ since the left policeman needs to cover $1$, while the right policeman needs to cover $n$. And the upper bound is $n$ since in any case, they would need no more than $n$ minutes to finish.Now for a given time $T$, we can find the largest position $r_l$ that the left policeman can cover, and the smallest position $l_r$ that the right policeman can cover. $r_l=\max(T-l+2,\lfloor\frac{T+l+1}{2}\rfloor)$ $l_r=\min(2n-r-T,\lfloor\frac{r+n-T+1}{2}\rfloor)$Then if $r_l+1\geq l_r$it is possible to cover all positions within $T$ time.Otherwise, we cannot cover.Code: 109510140
 » 8 months ago, # |   +12 A screencast with video solutions if you're into those... and also the first one with a facecam
 » 8 months ago, # |   +5 For J: you can remove the $\log MX$ term because the polynomials we care about are all geometric sums, so you can take the Fourier transform in $O(MX)$ time by precomputing powers of the root of unity.
 » 8 months ago, # | ← Rev. 2 →   0 In problem E, For even length palindromic subsequences, how can the answer be found from longest decreasing subsequence of second occurrences.If a = [4,3,2,1,1,2,3,4] Then the answer should be 8 but finding longest decreasing subsequence of second occurrences will not provide that answer.
•  » » 8 months ago, # ^ |   0 You would need to re-enumerate all elements of $a$ according to the index of the first time they appear. More formally, if $i(x)$ is the first index such that $a[i(x)] = x$, then construct an array defined by $b[j] = i(a[j])$.
 » 7 months ago, # | ← Rev. 2 →   0 Anyone here uses Kotlin with a CLI?Nevermind!