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

Правка en6, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Endagorion 2017-06-06 16:14:50 23910 Первая редакция перевода на Русский
en10 Английский Endagorion 2017-06-04 17:07:12 26 (published)
en9 Английский Endagorion 2017-06-04 17:05:38 33
en8 Английский Endagorion 2017-06-04 17:04:45 10870 Tiny change: 'ler>\n\n\n</spoiler>\n\n#### P' -> 'ler>\n\n\n#### P'
en7 Английский Endagorion 2017-06-04 16:18:23 5367 Tiny change: 'iler>\n\n<spoil' -> 'iler>\n\n</spoiler>\n\n\n<spoil'
en6 Английский 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 Английский 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 Английский Endagorion 2017-06-04 13:14:11 506
en3 Английский Endagorion 2017-06-04 13:08:22 2456 Tiny change: '### Proble' -> '#### Proble'
en2 Английский 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 Английский Endagorion 2017-06-04 10:31:12 960 Initial revision (saved to drafts)