Thanks to all the participants for successful submissions!

This set has been prepared by snarknews, Chmel_Tolstiy, Gassa and Zlobober. The analysis was prepared by snarknews and Gassa.

## Problem А. Alphabetical E-mail

Note that sets of vowels and consonants does not intersect, which means that, when comparing two subsequences lexicographically, first goes the one with the lesser first letter.

So read the characters one by one and remember first consonant and first vowel. When we meet both of them, immediately compare and print the answer. One of the subsequences can be empty.

## Problem B. Bytaler

Read the first exchange rate and set and to its value. Then read all other exchange rates; if the next rate is greater than , then set to it, and if it is less than , set to it.

Answer will be .

## Problem C. Chesskers

Because black checker can make no more than 7 turns before it will reach the 1st rank (or be removed by a white knight), and the white knight can also make no more than 7 turns (even if white move first, after seventh turn, the black checker reaches rank 1 and wins). Note that, at each turn, the checker has no more than 2 possibilities to move, and knight has not more than 8 possibilities, so we will have not more than 2^{7}·8^{7} = 2^{28} operations, which is small enough to just solve the problem recursively.

Let us implement two functions:

Checker's turn function which checks winning/losing condition, and if they are not reached, call the functions of knight's turn for all possible checker's moves.

Knight's turn function which checks winning/losing condition, and if they are not reached, call the functions of checker's turn for all (no more than eight) possible knight's moves.

So, the main procedure reads the input data, and then calls the appropriate function depending on who starts the game.

## Problem D. Desert City

Consider the diagonal *AC* of the convex pentagon. Two vertices (let us call them *D* and *E*) are lying at one side of it, and one (let us call it *B*) on another, so we have two diagonals *BD* and *BE* intersecting *AC* in inner points *P* and *Q*. Diagonals *AD* and *CE* are diagonals of a convex quadrilateral *ACDE*, so they intersect inside this quadrilateral. Diagonals *BE* and *AD* intersect inside the *ACDE* too (otherwise, we have segment *EQ* which connects vertice *E* of a convex quadrilateral *ACDE* with point *Q* on *AC* and does not intersect diagonal *AD*, which is impossible). The same is true for *BD* and *CE*. So, the three other intersection points are lying at one side of the line *AC*, connecting points *P* and *Q*. This means that intersections of diagonals of the convex pentagon form another convex pentagon *PQRST* with parts of diagonals as its edges.

In this case, vertices of the pentagon *ABCDE* can be reconstructed as the intersections of the lines which contain the pairs of sides which don't share a vertex (let us say these are *PQ* and *RS*). First, *PQ* and *RS* cannot be parallel. Also, because *ABCDE* is convex and edges of *PQRST* are parts of its diagonals, intersection must lie at another side of line *QR* than the other vertices of *PQRST*. So, if this is true for all five pairs of lines, then the convex pentagon *ABCDE* can be reconstructed correctly.

Taking all the above into account, the following solution can be considered We check if all five given points are vertices of their convex hull, then reorder them so that the pentagon *A*_{0}*A*_{1}*A*_{2}*A*_{3}*A*_{4} is convex, then check for each *i* if *A*_{i}*A*_{i + 1} and *A*_{i + 2}*A*_{i + 3} intersect at some point *Q*_{i} which lies at the other side of *A*_{i + 1}*A*_{i + 2} than *A*_{i} (here, the sum in indices is calculated modulo 5). If any of the checks failed, the answer is **No**. Otherwise, the answer is **Yes**.

## Problem E. Encoding

If it is impossible to select such a pair of *p* and *q*, then *f*(*x*) is *permutation polynomial* modulo 2^{m}, which means that it transforms the sequence of consecutive integers from 0 to 2^{m} - 1 into their permutation. Below, we show certain properties of permutation polynomials.

It is easy to see that for *m* = 1 and for any permutation polynomial, the sum *a*_{1} + ... + *a*_{n} must be odd: *f*(0) = *a*_{0} and *f*(1) = *a*_{0} + (*a*_{1} + ... + *a*_{n}); so if *a*_{1} + ... + *a*_{n} is even, then *f*(0) = *f*(1) modulo 2.

If *m* > 1, then *a*_{1} for permutation polynomial must be odd. Otherwise, *f*(2^{m - 1}) - *f*(0) = *a*_{0} + *a*_{1}·2^{m - 1} + 2^{2m - 2}·*R* - *a*_{0}, where *R* is an integer. Now, if *a*_{1} is even, then *f*(2^{m - 1}) - *f*(0) = 2^{m}·(*a*_{1} / 2 + 2^{m - 2}·*R*), so *f*(2^{m - 1}) - *f*(0) is divisible by 2^{m}.

After some more experiments you may notice the following rule: if a polynomial is a permutation polynomial modulo 2^{m}, this polynomial also must have even sum *a*_{3} + *a*_{5} + ... and even sum *a*_{2} + *a*_{4} + .... Proof of this theorem can be found, for example, in this paper by Ronald L. Rivest.

So, all you need is to check that the sum *a*_{1} + *a*_{2} + *a*_{3} + ... + *a*_{n} is even, and if *m* > 1, additionally check that *a*_{1} is odd and the sum *a*_{2} + *a*_{4} + ... is even. If this is true, the answer is **No** (the input contains a permutation polynomial). Otherwise, the answer is **Yes**.

## Problem F. Future Playlists

At first step, we should find a set *K* of vertices that belong to a single strongly connected component such that there is no edge that starts in a vertex from this set and ends in a vertex outside it.

Due to restrictions from the, problem statement it is possible to find such set, this set is unique, and the vertex corresponding to Byteasar's favorite track belongs to this set.

To find this set, we can run a depth-first search from vertex 1.

It is obvious that at 10^{2016}-th track, the probabilities for playing tracks not in our set can be considered as zeroes; moreover, 10^{2016} in this problem can be considered as infinity.

After an infinite number of rounds, the vector *p* of probabilities must conform to linear equation system *pW* = *p*, where *W* is the adjacency matrix of the subgraph built from vertices of the set *K*.

So we have a homoheneous system of linear equations (*W*^{T} - *I*)*p*^{T} = 0, and an additional equation . It is easy to see that system is consistent and it can be solved, for example, by Gaussian elimination.

The value *p*_{1} is the answer.

**P.S. If you find a typo, let me know with a private message.**

Auto comment: topic has been translated by Chmel_Tolstiy (original revision, translated revision, compare)Auto comment: topic has been updated by Chmel_Tolstiy (previous revision, new revision, compare).Hi Chmel, can you please release the problem statements? They are no longer accessible on the Yandex contest page. Thank you.