Yandex.Algorithm 2017, third elimination round: editorial (with challenges, bells and whistles)

Revision en6, by Endagorion, 2017-06-04 13:51:43

Problem A. Shifts

Topics: dynamic programming.

Suppose that we are allowed to make left circular shifts as well as right ones.

Can you solve the problem in this case?
What is the difference when we have only right shifts?
Challenge (hard/research):

Problem B. Number as a gift

Topics: greedy.

Since we aim to maximize the number, let us look what is the largest first digit we can possibly place. Let d denote the first digit of n.

There are several cases...
In some of these cases the rest is easy to find...
While in others we have to involve further...
How to proceed?
The complexity is...
Still WA?
Challenge (easy):

Problem C. Recursive Generator

Topics: hashing/string algorithms.

As a start, how can we prove why the Fibonacci sequence as described in the statement is not 1-recursive?

Assume that it is...
Can we make this into a criterion for k = 1?
What about extending this to any k?
How to check is the sequence has no k-contradictions?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Endagorion 2017-06-06 16:14:50 23910 Первая редакция перевода на Русский
en10 English Endagorion 2017-06-04 17:07:12 26 (published)
en9 English Endagorion 2017-06-04 17:05:38 33
en8 English Endagorion 2017-06-04 17:04:45 10870 Tiny change: 'ler>\n\n\n</spoiler>\n\n#### P' -> 'ler>\n\n\n#### P'
en7 English Endagorion 2017-06-04 16:18:23 5367 Tiny change: 'iler>\n\n<spoil' -> 'iler>\n\n</spoiler>\n\n\n<spoil'
en6 English Endagorion 2017-06-04 13:51:43 1634 Tiny change: '>\n$O(n^2 log n)$ ti' -> '>\n$O(n^2 \log n)$ ti'
en5 English Endagorion 2017-06-04 13:15:00 22 Tiny change: '0^9 + 7$) numbers that cons' -> '0^9 + 7$) positive numbers are there that cons'
en4 English Endagorion 2017-06-04 13:14:11 506
en3 English Endagorion 2017-06-04 13:08:22 2456 Tiny change: '### Proble' -> '#### Proble'
en2 English Endagorion 2017-06-04 11:50:31 6467 Tiny change: 'r, to any $X$ we can pr' -> 'r, to any X we can pr'
en1 English Endagorion 2017-06-04 10:31:12 960 Initial revision (saved to drafts)