Kotlin Heroes: Episode 6 — Editorial

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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 - От нуля до Y

Idea: BledDest, preparation: Neon

Tutorial

1488B - Удаление ПСП

Idea: BledDest, preparation: BledDest

Tutorial

1488C - Двое полицейских

Idea: vovuh, preparation: vovuh

Tutorial

1488D - Марафон решения задач

Idea: vovuh, preparation: awoo

Tutorial

Consider the minimum possible answer. Since you have to do all $$$s$$$ problems in $$$n$$$ days, you can do $$$\lfloor \frac s n \rfloor$$$ in some of them and then $$$\lceil \frac s n \rceil$$$ in the rest of the days. Thus, $$$\lceil \frac s n \rceil$$$ is the minimum possible $$$a_n$$$.

Now it would be great if the function that tells if some $$$x$$$ can be the number of problems during the last day was monotonous for all $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$\infty$$$. So that function first returns true for some prefix of values, then it returns false. Intuitively, it sounds monotonous: the smaller values allow a lot of freedom for the construction and the larger values fail because they require too many problems in total.

The difficulty rises from the fact we not only have to prove that, but we also have to find a way to ask the result of that function quickly.

If we didn't have to, the proof would not be too hard.

Proof

Now that we are absolutely sure that the function is monotonous, let's change our approach.

Obviously, we should try binary search on $$$x$$$. So we have the total number of problems $$$s$$$, the number of days $$$n$$$ and some fixed number of problems during the last day $$$x$$$.

Our second educated guess can be of the following kind. Given fixed $$$n$$$ and $$$x$$$, all the possible values of $$$s$$$ that can correspond to some construction are some segment of integers. That can actually be proven in the similar manner.

Proof

So we can binary search for a solution for $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$s$$$. $$$f(x)$$$ can be the smallest total number of problems such that there exists a distribution. Since that value is monotonous, you can look for the largest $$$x$$$ such that $$$f(x) \le s$$$.

To calculate the function you can observe that the sequence $$$x$$$, $$$\lceil \frac x 2 \rceil$$$, $$$\left\lceil \frac{\lceil \frac x 2 \rceil}{2} \right\rceil$$$, $$$\dots$$$ has only ones after $$$\log(x)$$$ values.

Overall complexity: $$$O(\log^2 s)$$$ per testcase.

1488E - Палиндромные пары

Idea: BledDest, preparation: awoo

Tutorial

1488F - Dogecoin

Idea: BledDest and Neon, preparation: Neon

Tutorial

1488G - Раскраска чисел

Idea: Neon, preparation: Neon

Tutorial

1488H - Построй из суффиксов

Idea: BledDest, preparation: awoo

Tutorial

1488I - Вторжение демонов

Idea: BledDest, preparation: BledDest

Tutorial

1488J - Цветочный магазин

Idea: BledDest, preparation: Neon and adedalic

Tutorial

Comments (11)

Show archived | Write comment?

BledDest

3 years ago, # |

← Rev. 2 →

The solution codes will be uploaded shortly.

UPD: here they are.

→ Reply

submitkotlin

3 years ago, # ^ |

+13

When will the Random T-shirt winners will be announce?

nor

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.

kasparovian

Wow, nice observation, I just completely overkilled this.

Into_Your_Arms

can you tell name of algo or provide some link for "how to find no of match between two strings in O(n)"

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)$$$.

lucifer1004

← 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

galen_colin

A screencast with video solutions if you're into those... and also the first one with a facecam

ecnerwala

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.

aryan57

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.

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])$$$.

BledDest's blog