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

Revision en10, by Endagorion, 2017-06-04 17:07:12

This time I've decided to play with spoilers to faciliate the presentation as some of the guys here did before. Tell me what you think about this write-up!

#### Problem A. Shifts

Topics: dynamic programming.

Summary: the first "hard" problem of the contest. Knowing your basic DP problems helps a lot, but coming up with the precisely correct solution may take a lot of persistence.

Solution: 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.

Summary: a gatekeeper for inexperienced and/or impatient contestants. Many details to take into account, but otherwise tractable.

Solution: 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.

Summary: while this is a simple problem, some approaches are better than others in terms of complexity, memory, and implementation tediousness. Pick your poison!

Solution: 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?
Finally...
Challenge (easy/exercise):

Topics: greedy, sorting, implementation.

Summary: while the solution is not exactly evident from the start, one has to jumps a lot of hoops and dodge a lot of spikes to avoid all possible mistakes with precision, query limit and whatnot.

Solution:

Can we solve the problem if we know the vendor's values of d?
What to do if we do not know d_i's?

This pretty much concludes the idea description.

Still, there are many nasty details...
Challenge (medium):

#### Problem E. Manhattan Walk

Topics: maths, shortest paths in graphs.

Summary: even if you don't come up with a simple mathematical solution, graph algorithms save the day. Easy!

Solution:

Looks standard, right?
I'm lazy, can I do better?
Challenge (easy, I gueess):

#### Problem F. Tree Game

Topics: game theory, graphs, math.

Summary: frankly, I anticipated a lot more solutions on this problem. All ideas seemed basic to me, and the code is very easy. Still, it seems that cracking the whole thing was not that simple. Did you enjoy solving it? =)

Solution:

Phase 1!
Phase 2!
Phase 3!
Assemble?
Challenge (nasty):

#### History

Revisions

Rev. Lang. By When Δ Comment
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)