BledDest's blog

By BledDest, history, 4 years ago, In English

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

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
  • Vote: I like it
  • +63
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The solution codes will be uploaded shortly.

UPD: here they are.

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Wow, nice observation, I just completely overkilled this.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 4   Vote: I like it +12 Vote: I do not like it

1488C - Двое полицейских 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

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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