Problemset was prepared by Yandex employees.

Problem А. ZeroOne

Firstly, let's convert input strings into two binary strings. Because the numbers can be approximately $$$2^{333}$$$ we shouldn't convert them into the numeric type and should compare their string representations

#include <iostream>
#include <algorithm>

int main() {
    std::string s[2];
    std::cin >> s[0] >> s[1];


    std::string r[2];

    for(int i = 0; i < 2; ++i) {
        while (!s[i].empty()) {
            if (s[i].substr(s[i].size() - 3, 3) == "one") {
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                r[i] += "1";
            } else {
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                r[i] += "0";
            }
        }
    }

    for(auto & s : r) {
        std::reverse(s.begin(), s.end());
    }
    
    if (r[0].size() > r[1].size()) {
        std::cout << ">";
    } else if (r[1].size() > r[0].size()) {
        std::cout << "<";
    } else if (r[0] > r[1]) {
        std::cout << ">";
    } else if (r[0] == r[1]) {
        std::cout << "=";
    } else {
        std::cout << "<";
    }

    return 0;
}

Problem B. Tiles 2x2

To solve to problem we can introduce equivalence classes of tiles $$$2 \times 2$$$. If the number of tiles of each class in the set is not less than the required number for the picture, the result will be positive.

To determine the equivalence class one can choose the main representative of the class. In the case of the matrix $$$2\times 2$$$ the minimum tuple of all four rotations of the matrix is suitable.

import collections


def normalize(a, b): # write cells in clockwise order
	return min(a[0] + a[1] + b[1] + b[0], 
		a[1] + b[1] + b[0] + a[0], 
		b[1] + b[0] + a[0] + a[1],
		b[0] + a[0] + a[1] + b[1])


def main():
	k = int(input())
	tile_set = collections.defaultdict(int)
	for _ in range(k):
		a = input()
		b = input()
		tile = normalize(a, b)
		tile_set[tile] += 1
	n, m = map(int, input().split())
	for _ in range(n // 2):
		a = input()
		b = input()
		for j in range(0, m, 2):
			tile = normalize(a[j:j+2], b[j:j+2])
			tile_set[tile] -= 1

	print('Yes' if min(tile_set.values()) >= 0 else 'No')


if __name__ == '__main__':
	main()

Problem C. Balls and Boxes

Let $$$sumA = \sum_{i = 1}^k a_i$$$. To check whether a certain number of boxes $$$x, 1\le x\le sumA,$$$ satisfies all conditions the following must be fulfilled:

• x is a divisor of $$$sumA$$$
• $$$a_i - x \cdot b_i \ge 0$$$ for each color $$$i$$$

So, we can iterate over the divisors of the number $$$sumA$$$, check the fulfillment of the second condition, and choose the maximum $$$x$$$ that the condition is met.

The tricky part of the problem is to print the result. One should be attentive with the case $$$b_i=0$$$.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int k;
    std::cin >> k;


    int sum = 0;
    std::vector<int> a(k);
    for(int i = 0; i < k; ++i) {
        std::cin >> a[i];
        sum += a[i];
    }

    std::vector<int> possible;

    for(int i = 1; i <= sum; ++i) {
        if (sum % i == 0) {
            possible.push_back(i);
        }
    }

    std::reverse(possible.begin(), possible.end());

    std::vector<int> every_need;

    int sumb = 0;
    std::vector<int> b(k);
    for(int i = 0; i < k; ++i) {
        std::cin >> b[i];
        sumb += b[i];
        for(int j = 0; j < b[i]; ++j) {
            every_need.push_back(i + 1);
        }
    }

    int ans = -1;

    for(auto i : possible) {
        bool ok = true;

        for(int j = 0; j < k; ++j) {
            if (b[j] != 0) {
                if (a[j] / b[j] < i) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            ans = i;
            break;
        }
    }


    if (ans == -1) {
        std::cout << -1;
        return 0;
    }

    std::vector<int> free;
    for(int i = 0; i < k; ++i) {
        a[i] -= b[i] * ans;
        for(int j = 0; j < a[i]; ++j) {
            free.push_back(i + 1);
        }
    }

    int in_every = sum / ans;
    std::cout << ans << ' ' << in_every << std::endl;

    for(int i = 0; i < ans; ++i) {
        for(auto j : every_need) {
            std::cout << j << ' ';
        }

        for(int j = 0; j < in_every - sumb; ++j) {
            std::cout << free.back() << ' ';
            free.pop_back();
        }
        std::cout << std::endl;
    }
    
    return 0;
}

Problem D. Matrix

For convenience, we will use the following notation $$$n=2^{n'}$$$, $$$m=2^{m'}$$$.

1. Let's consider the case $$$n=m,\,n>1$$$. After the first step the matrix has the following form:

After the second step the matrix has the following form:

Thus, after the second step and until the very end, the entire matrix is filled with the same numbers.

Summarizing this information, the total of different numbers will be written out is $$$n^{2}+\frac{n}{2}+\log_2{\frac{n^2}{2}}$$$ ($$$1$$$, $$$2$$$, ..., $$$n^2$$$, $$$n^2+2$$$, $$$n^2+4$$$, ..., $$$n^2+n$$$, $$$2(n^2+1)$$$, $$$2^2(n^2+1)$$$, ..., $$$\frac{n^2(2n^2+1)}{2}$$$.

1. Let's consider the case $$$n<m$$$. After the first step the matrix has the following form:

After the $$$i_{th}$$$ of following ($$$m'-n'-1$$$) steps the matrix has the following form:

Note that in these matrices any number over $$$nm$$$ occurs only once (an entire row of one of the matrices). At the next step and until the very end, the entire matrix is filled with the same numbers.

Unlike the first case, we can consider each of the $$$n$$$ rows of the matrix separately ($$$n < 2^{15}$$$).

1. Let's consider the case $$$n>m$$$. After the first step the matrix has the following form:

After the $$$i_{th}$$$ of following ($$$n'-m'$$$) steps the matrix has the following form:

It should be noted that the maximum element of the matrix at step $$$i$$$ is less than the minimum element of the matrix at step $$$i+1$$$.

Summarizing this information, there are $$$nm+\frac{m}{2}+m\log_2{\frac{n}{m}}+\log_2{\frac{m^2}{2}}$$$ different numbers will be written out .

import sys
import math


def log2(n):
	return 0 if n <= 1 else int(math.log(n, 2))


def main():
	n, m = map(int, input().split())
	_n = n * m
	result = _n
	if n == m:
		result += n // 2
		result += log2(n ** 2 // 2)
	elif n < m:
		for i in range(n):
			x = 1 + (2 * i + 1) * m
			for j in range(log2(m // n)):
				if x > _n:
					result += 1
				x *= 2
		result += log2(n ** 2)
	else:
		result += m // 2
		result += m * log2(n // m)
		result += log2(m ** 2 // 2)

	print(result)


if __name__ == '__main__':
	main()

Problem E. Matrix sort

Let us consider the set of zeros in the sorted matrix. The number of operations is the number of ones in the original matrix inside this set. The set of zeros forms a Young tableau which is the set of cells, such that in each row and column zeroes form a prefix. So we need to construct Young tableau of the given size which contains the least amount of ones in the original matrix.

We are going to solve the problem with dynamic programming. For each cell of the matrix we consider the rectangle with one corner in this cell and the opposite corner in the right upper corner of the matrix. For each possible size of Young tableau inside this rectangle we calculate the least number of ones it can contain. There are $$$O(nm)$$$ cells in the matrix and $$$O(nm)$$$ sizes of Young tableau so we need to solve $$$O((nm)^2)$$$ subproblems.

Let us show how to solve each subproblem. Let us consider the cell in the left lower corner of the rectangle where we consider our Young tableaus. It is either belongs to the Young tableau(meaning that it will contain zero in the end) or not.

If it belongs to the Young tableau, then all cells above it belong to the Young tableau too. In this case we reduced our problem to the rectangle with left lower corner one cell to the right from our cell and Young tableau size is reduced by the size of the column. In order to calculate how many ones we got inside the column, we precalculate for each cell of the matrix the number of ones non-strictly above it in the same column. This precalculation can be made in $$$O(nm)$$$, if we go from top to bottom.

In the second case, the left lower corner does not belong to the Young tableau. In this case we reduced our problem to the rectangle with left lower corner one cell above from our cell and Young tableau size as well as the answer remained unchanged.

All what is left, is to take the minimum of these two cases. Each case requires $$$O(1)$$$ time, so all cases require $$$O((nm)^2)$$$ time. The states of the dynamic programming can be calculated from top to bottom and from right to left. Moreover, we can only store current and the next row or column. So we only need $$$O(\min(n^2m, nm^2))$$$ memory.

Problem F. Path Reverse

$$$O(n^2)$$$ solution

To solve this problem in $$$O(n^2)$$$, it's enough to iterate over all pairs $$$(p, q)$$$ and for each of them find the answer in $$$O(1)$$$.

In this solution, we must be able to find the distance between every pair of vertices in $$$O(1)$$$. We can precalculate them: just run dfs or bfs from each vertex and get $$$d_{ij}$$$ — the distance between vertices $$$i$$$ and $$$j$$$.

When $$$p$$$ and $$$q$$$ are fixed, each vertex $$$x$$$ belongs to one of the four following kinds:

• $$$x$$$ lies on the path between $$$p$$$ and $$$q$$$, inclusively. This can be checked with this condition: $$$d_{px} + d_{xq} = d_{pq}$$$.
• $$$x$$$ lies in the part of tree behind vertex $$$p$$$, or $$$d_{xp} + d_{pq} = d_{xq}$$$.
• $$$x$$$ lies in the part of tree behind vertex $$$q$$$, or $$$d_{pq} + d_{qx} = d_{px}$$$.
• $$$x$$$ lies on a branch connected to the path $$$p-q$$$. This happens if all three of the conditions above are false.

How can vertices $$$1$$$ and $$$n$$$ be located relative to $$$p$$$ and $$$q$$$? There are 16 cases in general: $$$1$$$/$$$n$$$ (independent) can have one of four relations above (4 choices). The distance between $$$1$$$ and $$$n$$$ changes only in these cases (actually in 8 cases out of 16):

• $$$1$$$ is behind $$$p$$$, $$$n$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$1$$$ is behind $$$q$$$, $$$n$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$n$$$ is behind $$$p$$$, $$$1$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$n$$$ is behind $$$q$$$, $$$1$$$ is on path $$$p-q$$$ or lies on a branch.

As they are identical, consider only the first one. So, $$$1$$$ is behind $$$p$$$, and $$$n$$$ lies on a path $$$p-q$$$ or on a branch. Before the reverse operation the distance was $$$d_{1p} + d_{pn}$$$, and after the swap it becomes $$$d_{1p} + d_{qn}$$$. Problem solved, 2 points are ours.

Solution for a line case

Here our tree is a line, but we must do it in $$$O(n)$$$. The distance changes only when one of $$$p$$$ and $$$q$$$ lies outside path $$$1-n$$$ and the other one lies inside.

First of all, calculate the distance between $$$1$$$ and $$$n$$$ and multiply it by $$$\frac{n(n-1)}{2}$$$. We will find how answer changes after reverse operations, not calculate it from scratch every time.

Let's say $$$1$$$ is to the left of $$$n$$$, and denote the number of vertices strictly to the left of $$$1$$$ as $$$a$$$, and strictly between $$$1$$$ and $$$n$$$ as $$$b$$$.

.... (a slots) .... [1] .... (b slots) .... [N] ....

Let $$$d$$$ be the delta the answer increases by after the reverse. If $$$p$$$ is in one of the $$$a$$$ slots to the left of $$$1$$$, how many slots for $$$q$$$ on path $$$1-n$$$ can produce this delta $$$d$$$? Let's show the pictures for $$$d=1$$$ and $$$d=2$$$:

$$$d = 1$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [p] [q] [ ] [ ] [ ] [ ] [ ] [N] [ ] [ ]
[ ] [ ] [ ] [ ] [p] [ ] [1] [q] [ ] [ ] [ ] [ ] [N] [ ] [ ]
[ ] [ ] [ ] [p] [ ] [ ] [1] [ ] [q] [ ] [ ] [ ] [N] [ ] [ ]
...

$$$d = 2$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [p] [ ] [q] [ ] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [p] [ ] [ ] [1] [q] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [p] [ ] [ ] [ ] [1] [ ] [q] [ ] [ ] [N] [ ] [ ] [ ]
...

Hope you got the pictures. For fixed $$$d$$$, the answer is $$$\min(a - d + 1, b + 1)$$$ (one of the segments with slots ends sooner, that's why there is minimum in the formula). So we add $$$d \cdot \min(a - d + 1, b + 1)$$$ to the total answer.

Deltas can be negative (the distance between $$$1$$$ and $$$n$$$ can decrease). This are the pictures for negative deltas:

$$$d = 1$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [ ] [q] [p] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [q] [1] [ ] [p] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [q] [ ] [1] [ ] [ ] [p] [ ] [N] [ ] [ ] [ ]
...

$$$d = 2$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [ ] [q] [ ] [p] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [q] [1] [ ] [ ] [p] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [q] [ ] [1] [ ] [ ] [ ] [p] [N] [ ] [ ] [ ]
...

Here, the formula for a certain $$$d$$$ is $$$\min(b - d + 1, a + 1)$$$.

Positive $$$d$$$ can change from $$$1$$$ to $$$a$$$, and negative $$$d$$$ can change from $$$1$$$ to $$$b$$$ (by absolute value). For each of these $$$d$$$ we find the answer's delta in $$$O(1)$$$.

Challenge: actually, knowing $$$a$$$ and $$$b$$$, it's possible not to iterate over $$$d$$$ (which would be $$$O(n)$$$), but calculate everything in $$$O(1)$$$. Can you discover the formula?

Solution for a general case

In $$$O(n^2)$$$ solution, we divided all vertices into four classes depending on their location relative to $$$p$$$ and $$$q$$$. Here we will need the similar thing but relatively to $$$1$$$ and $$$n$$$.

Let's say $$$d_{1x}$$$ is the distance from $$$x$$$ to $$$1$$$, and $$$d_{nx}$$$ — from $$$x$$$ to $$$n$$$. Also let's say $$$m$$$ is the distance between $$$1$$$ and $$$n$$$. Then, vertices can be:

• behind $$$1$$$ or equal to $$$1$$$: $$$d_{1x} + m = d_{nx}$$$,
• behind $$$n$$$ or equal to $$$n$$$: $$$d_{1x} = m + d_{nx}$$$,
• strictly inside the path $$$1-n$$$: $$$d_{1x} + d_{nx} = m$$$, but $$$x \ne 1$$$ and $$$x \ne n$$$,
• on a branch, if all three conditions above are false.

Answer changes in two general cases:

• $$$p$$$ is strictly between $$$1$$$ and $$$n$$$ or equal to one of them, and $$$q$$$ is behind $$$1$$$ or $$$n$$$,
• $$$p$$$ is strictly between $$$1$$$ and $$$n$$$, and $$$q$$$ lies on a branch, and the root of the branch $$$z$$$ is strictly between $$$1$$$ and $$$n$$$, and $$$p \ne z$$$.

First case:

Let's iterate over $$$q$$$. Now we have fixed $$$q$$$. How can the answer change?

... [Q] ..... (a slots) ... [1] ... (b slots, P is somewhere on [1, N)) ... [N] ...

... [Q] [ ] [ ] [ ] [ ] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [N] ...

For the first row ($$$p=1$$$), the delta is $$$a$$$ (which is equal to $$$d_{1q})$$$, for the second row — $$$a-1$$$, and so on. Finally, when $$$n$$$ and $$$p$$$ are neighbors, it's $$$a-b$$$ (it may be negative if $$$a < b$$$, it's fine). So the result is the sum of consecutive numbers between $$$a$$$ and $$$a - b$$$ and can be found in $$$O(1)$$$.

If you solve this case correctly and completely ignore the second case, you will get 2 points, as this solves the line subtask.

Second case:

Let's again iterate over $$$q$$$. Knowing $$$d_{1q}$$$ and $$$d_{nq}$$$, we can find the branch root $$$z$$$ (as we can calculate the length of the branch, which is $$$\frac{d_{1q} + d_{nq} - m}{2}$$$, where $$$m$$$ is distance between $$$1$$$ and $$$n$$$, $$$m = d_{1n}$$$) and its $$$d_{1z}$$$ and $$$d_{nz}$$$. Here we again have two identical cases (choice between $$$1$$$ and $$$n$$$), let's show one of them.

                                                    ...
                                                    [N]
                                                    [ ]
                                                    ...
                                                    [ ]
... [1] ... (a slots, P is somewhere on (1, Z)) ... [Z] ... (b slots) ..... [Q] ...

... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [ ] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
...
... [1] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...

Here, $$$a = d_{1z} - 1$$$, $$$b$$$ is the branch length minus 1. As shown at the picture, answer changes when $$$p$$$ runs from $$$1$$$ to $$$z$$$, not including $$$1$$$ and $$$z$$$. It is again a sum of consecutive numbers: $$$b + (b-1) + \ldots + (b-a+1)$$$ and again can be calculated in $$$O(1)$$$.

So for each of two general cases, we iterate over all $$$q$$$ and for each $$$q$$$ find the answer is $$$O(1)$$$, which gives the total complexity $$$O(n)$$$.

int64_t arithmSum(int64_t first, int64_t last) {
    if (first > last) {
        swap(first, last);
    }
    const int64_t len = last - first + 1;
    return (first + last) * len / 2;
}

// vertices in the solution are 0-indexed
vector<int> d1; // d1[x] is the distance between x and 0
vector<int> dn; // dn[x] is the distance between x and (n - 1)

const int m = d1[n - 1];
const int64_t initialAns = int64_t(m) * n * (n - 1) / 2;

auto isOnPath = [&](const int x) -> bool {
    if (x == 0 || x == n - 1) return false;
    return d1[x] + dn[x] == m;
};
auto isOutside1 = [&](const int x) -> bool {
    return d1[x] == dn[x] - m;
};
auto isOutsideN = [&](const int x) -> bool {
    return dn[x] == d1[x] - m;
};
auto isOnBranch = [&](const int x) -> bool {
    if (isOnPath(x)) return false;
    if (isOutside1(x)) return false;
    if (isOutsideN(x)) return false;
    return true;
};

// case 1
auto f1 = [](const int64_t a, const int64_t b) -> int64_t {
    // a + (a-1) + ... + (a-b)
    return arithmSum(a, a - b);
};
int64_t add1 = 0;
for (int q = 0; q < n; q++) {
    if (isOutside1(q)) add1 += f1(d1[q], m - 1);
    if (isOutsideN(q)) add1 += f1(dn[q], m - 1);
}

// case 2
auto f2 = [](const int64_t a, const int64_t b) -> int64_t {
    // b + (b-1) + ... + (b-a+1)
    if (a == 0) return 0;
    return arithmSum(b, b - a + 1);
};
int64_t add2 = 0;
for (int q = 0; q < n; q++) {
    if (isOnBranch(q)) {
        const int branchLength = (d1[q] + dn[q] - m) / 2;
        const int lenFrom1ToZ = d1[q] - branchLength;
        const int lenFromNToZ = dn[q] - branchLength;
        add2 += f2(lenFrom1ToZ - 1, branchLength - 1);
        add2 += f2(lenFromNToZ - 1, branchLength - 1);
    }
}

const int64_t ans = initialAns + add1 + add2;

Yandex.Algorithm ML track started! Hope you will participate it)

The task has been prepared by the Yandex.Alice team and personally Slava Alipov eik0u.

Building an open-domain conversational assistant that is clever and fun is one the most exciting applications and research frontiers of artificial intelligence nowadays. The core and very challenging task of such an assistant is providing coherent and entertaining replies to the users at all steps of their conversation with the assistant.

Participating in our competition you can to feel closer to the creation of the conversational assistant able to talk with millions of users like Alice does every day.

Submissions should be sent until 10:00 23rd April (MSK). Top 128 participants will receive cool t-shirts. The best three will receive cash prizes.

One can share approaches and discuss the contest with other participants in #proj_algo_alice Open Data Science community channel (registration link http://ods.ai/).

Problemset was prepared by Yandex employees from Minsk.

Problem А. Task Management

Consider a solution with the complexity . Use a variable to track the last closed task and go through the list of tasks from the beginning to the end. Increase the counter when passing through the element corresponding to the next task. The constrains are quite large, so this solution doesn't fit the timelimit.

What is the case when we can not find any suitable tasks up to the end of the list? There is only one case: the task number (x + 1) is closer to the beggining of the list then the closed task number x. Therefore, to solve the problem we can determine position of each task in the task list and count the number of distinct numbers x such that the position of task number (x + 1) is less than the position of task number x.

Don't forget to consider the first pass through the task list. The final complexity of the solution is .

Problem B. Cross-City Communication

Problem ''Cross-City Communication`` does not contain any special algorithmic ideas, so we have to implement behavior described in the problem statement.

For each hour from 0 to 23 we need to check the free conference rooms in the reqired cities.

Note that for larger constrains determining of free conference room for each pair (city, hour) can help to answer queries faster. This information allows to answer a query in time proportional to the number of cities instead of the total number of conference rooms.

Problem C. Test Invocation

There are several different approaches to solve the problem, consider two of them.

The first solution is based on counting the number of times the test number x will be run. In the original system each test runs once, and in the new system it runs 2^d(x) times, where d(x) is the distance from the root test to test number x. This can be easily proved by the induction (this fact can be guessed from the description of the samples). d(x) can be calculated by any traversal of the tree.

The second approach is based on dynamic programming. Let T(x) be equal to the total running time of the test number x, i.e. sum of the running timeS of the tests it depends and the checking time a_x. So we have:

To compute the answer T(1) we run a tree traversal and calculate T(x) values using the recurrent formula above.

The complexity of solution is .

Problem D. Artihmetic Mean Encoding

Сonsider next problem. If n = b₁ + b₂ + ... + b_c and all b_i are powers of two with non-negative integer exponents, find all possible values of c. We will show that c can be equal to any integer from popcount(n) to n (where popcount(n) is the number of set bits in binary representation of n).

It is obvious that we cannot use less than popcount(n) numbers and more than n. If we have a sequence b_i of length x (x < n) it always contains an element 2^t with a positive value t. We can replace it with the two elements 2^t - 1, obtaining a sequence of length (x + 1). The sequence b_i of length popcount(n) can be build from the binary representation of the number n.

To solve the problem we can start from k equals to 1 and check existence of the sequence a_i. As shown above, we need to find the minimum k that popcount(kn) ≤ k and construct the answer.

For problem constraints k does not exceed 60 (60·(2⁵⁰ - 1) < 2⁶⁰ - 1 = 2⁰ + 2¹ + ... + 2⁵⁹).

Problem E. Cluster Connection

Graph should not contain brigdes, so the degree of each vertice is not less than two. Since the sum of degree of all vertices is equal to 2·n + 2 we have two possible cases:

• there is one vertex of degree 4;
• there are two vertices of degree 3.

Consider the first case. Graph is an union of two cycles of length (m + 1) and (n - m) with a common vertex. In this case, we need to choose which vertices will be in the first cycle (other will go to the second), and the order in which vertices will be on these cycles. The number of ways to construct such graph is

Consider the second case. In the graph there are two vertices of degree three connected by chains of edges. All the other (n - 2) vertices are located on this chains. Note that there can be only one connection with zero additional vertices (an edge). Let the chains have a, b and c vertices are (a ≤ b ≤ c). Consider a few cases:

• 0 ≤ a < b < c, then the number of graphs is equal to
• 0 < a = b < c, then the number of graphs is equal to
• 0 ≤ a < b = c, then the number of graphs is equal to
• 0 < a = b = c, then the number of graphs is equal to

Combine all formulas together and obtain the final result.

Problem F. Repetitions

To solve this problem, refer to the string terminology. A border of a string s is some string y that x starts with and ends with y.

For each prefix p of the text we need to find the maximum length of the border, which has at least one additional occurrence in this prefix. To do this, we can find all borders of p, go through this list in descending order of lengths to find the first with additional occurence.

To search for all borders we can use the prefix-function. Additionally, remembering that π(i) is the maximal border of the prefix with length i, and length of all the borders form sequence π(i), π(π(i)), π(π(π(i))), ... etc.

Interesting fact: the border of length π(π(i)) always has at least three occurrences in the prefix with length i (the first starts in the first position, the second ends in the position i and the third ends in position π(i)).

To find the answer of the problem we need the way to check whether the additional entry of the maximum length border (of length π(i)) exists. If such occurrence exists then text has a position j (j < i), where π(j) ≥ π(i). For a quick check of this inequality, it is sufficient to compute the prefix maximum values of the prefix-function.

The complexity of algorithm is .

Thanks to all the participants for successful submissions!

This set has been prepared by Romka, Chmel_Tolstiy and Ixanezis. Special thanks to Gassa for his help in the preparation of statements and analysis.

Problem А. Orthography

The task has rather small constraints, so that it can be solved easily in O(N²L) complexity, where N is the number of words in the set and L is the length of a word.

In order to achieve such complexity, it is enough to check what happens if we choose each word as ''correct'' (a word with no errors). So, for each word in the set, we iterate over the set of words again and calculate the number of positions in which our chosen word differs from each other word. If all the numbers do not exceed 1, the chosen word perfectly suits us as being ''correct''.

There also exists a better solution in O(NL) complexity, but it was not necessary to apply it here.

Problem B. Voice Alerts

For each recorded phrase, we can calculate the corresponding distance D_i using the formula D_i = X_i + V·(t_i + T_phrase). Then we must find the minimal D_i and its index (also minimal with such distance in case of multiple answers).

Problem C. Table Tennis Tournament

To solve this problem, the following observation is necessary. The problem statement implies that the participants scored 2·N - 2, 2·N - 3, ..., N - 1 points. And it follows that the winner won all matches, the runner-up won all matches except the match against the winner, and so on. The participant who took the last place lost all matches.

If we fix the order of participants in the tournament results, we can find the probability of such final outcome. For this, just multiply the necessary probabilities from the probability matrix p_ij. To generate all permutations, you can use the method std::next_permutation (C++) or, for example, implement a recursive search.

The original problem can be solved with the described algorithm in time O(n²·n!). Using the ideas of dynamic programming, this approach can be sped up, and one can obtain an algorithm running in O(n·2ⁿ).

Problem D. Numeric Compression

Let us solve the problem using dynamic programming. For this problem, there are several different approaches, we will describe only one of them.

Note that the number of bit sequences of length L with K alternating groups of bits starting with a group with a zero bit are exactly C(L - 1, K - 1). Indeed, each of the groups is not empty, and among L - 1 of the boundaries between adjacent elements of a bit sequence, we need to choose K - 1 (which will separate the adjacent groups with different bits).

Consider the function F(L, K): the sum of bit compression results of all numerical sequences of length L with K alternating groups of bits (as we already know, there are C(L - 1, K - 1) such sequences).

To compute the value F(L, K) one can use the following approach. Iterate the size of the right group t (the lowest binary digit of the compression result). It is easy to obtain the following relationship:
F(L, K) = sum(t = 1..L - 1) 2·F(L - t, K - 1) + is_even(K)·C(L - t - 1, K - 2) for L > 1; for the base case, F(1, K) = 0.

For the solution of the original problem, find the sum of the numerical compression results for all numbers X smaller than N + 1. All these numbers can be divided into several groups. Let the group G_i consist of all the numbers X such that the highest bit where it differs from N + 1 is at position i. Note that this automatically implies that i-th bit of X is equal to 0, and i-th bit of N + 1 is equal to 1. To calculate the result of summing the numbers from one group, we will use the results of numerical compression of the prefix of N + 1 up to position i and the function F(L, K).

The function calculates the result of compression for the prefix of the number N + 1, but if the last group contains bit 0, it is excluded from the sum. We consciously included this group in F(L, K).

The solution described above has complexity , but you can speed it up to . Maybe even faster?

Problem E. Bicycle Construction

Let us notice that condition of 4-gears set satisfiability can be rewritten as follows: we can complete a bike using given 4 gears if and only if we can split them into pairs such that products of diameters in each pair are equal.

For each gear diameter D, we can calculate the number of gears with this diameter C_D, and for each possible P, we can calculate number Cnt_P of pairs of gears that give us product of diameters P. It can be done in O(N²) time using HashMap / unordered_map or similar container, or in time with help of Quicksort or other sorting algorithm that is fast enough. Now let us consider all pairs of gears. For each pair with diameters D1 and D2 with product P = D1·D2, we can increase answer by Cnt_P - 1, thinking of it as of ``the number of other pairs with such product of diameters''. Unfortunately, it is possible that we added some pairs which included one of the gears we are currently considering. In order to prevent this, we need to decrease the answer by C_D1 + C_D2 - 2 if current gears have different diameters, and by (C_D1 - 2)·2 if they are equal.

Now we had taken into account all needed 4-gears sets, but each of them was considered several times. It's easy to notice that every set of the form D D D D (4 gears with equal diameters) is considered 6 times, every set of form D E D E is considered 4 times and every set of form D E F G or D E E F is considered 2 times. Thus, to obtain the final answer, we need to decrease our answer by for each gear diameter D, then decrease it by C_D·(C_D - 1)·C_E·(C_E - 1)·2 for each pair of different diameters D E, and finally divide the answer by 2.

Problem F. Radars

First, let us consider the case when we have a single control point. This is trivial: the easiest way is to place the radar into the same point as the single control point. We get efficiency of exactly 1 in such case.

Now let us consider a case when we have two or more control points. Suppose we have found an answer: radar placement with maximum total efficiency. After that, we can move the radar around such point until at least two control points are at integer distances from the radar. Further movement in any direction, which leads some of these points to cross the integer border of that radius around the radar, does not increase the total efficiency (otherwise, our initial assumption about the initial optimal placement is incorrect).

So we will try to find precisely such radar placement that at least two control points lie at an integer distance from it. In order to achieve it, let us iterate over all pairs of control points and over distances r₁ and r₂, which are the distances from these points to the radar. Eventually, we will find points on the plane for the radar itself: these are the points of circle intersections with radii r₁ and r₂ and with centers in chosen control points.

We can have numerous such points:
- 0, if circles do not intersect at all,
- 1, if circles touch each other (including the inner touching case),
- 2, if circles intersect.

For each of the circles' intersection points, we calculate the total radar efficiency by definition, and choose the global maximum of all such placements.

The final algorithm complexity is O(N³·R²) where N is the number of control points and R is the maximum considered radius. Considering that points are located in a square with coordinates from 0 to 50, the highest total distance that makes sense to examine is .

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

Yesterday ACM ICPC World Finals finished. We congratulate all winners, medalists and special prize winners!

We want to remind you that tomorrow, May 21, at 00:00 (UTC+3) the qualification round of Yandex.Algorithm will start. For participation in qualifications you should register and start a virtual contest at any time prior to May 23 (UTC+3).

As usual 6 problems of varying difficulty will be provided at Yandex.Algorithm rounds. In order to qualify for the elimination stage rounds and compete for a trip to the finals in Minsk and other prizes you should solve at least one problem.

Also Yandex.Algorithm offers students to participate in the internship track. For more information see the rules of the championship.

Good luck! See you at Yandex.Algorithm!

P.S. The qualification round has started. Problems prepared by Romka, Ixanezis and Chmel_Tolstiy.

EDIT. Analysis has been posted.

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⁷·8⁷ = 2²⁸ 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₀A₁A₂A₃A₄ is convex, then check for each i if A_iA_i + 1 and A_i + 2A_i + 3 intersect at some point Q_i which lies at the other side of A_i + 1A_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₁ + ... + a_n must be odd: f(0) = a₀ and f(1) = a₀ + (a₁ + ... + a_n); so if a₁ + ... + a_n is even, then f(0) = f(1) modulo 2.

If m > 1, then a₁ for permutation polynomial must be odd. Otherwise, f(2^m - 1) - f(0) = a₀ + a₁·2^m - 1 + 2^2m - 2·R - a₀, where R is an integer. Now, if a₁ is even, then f(2^m - 1) - f(0) = 2^m·(a₁ / 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₃ + a₅ + ... and even sum a₂ + a₄ + .... 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₁ + a₂ + a₃ + ... + a_n is even, and if m > 1, additionally check that a₁ is odd and the sum a₂ + a₄ + ... 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²⁰¹⁶-th track, the probabilities for playing tracks not in our set can be considered as zeroes; moreover, 10²⁰¹⁶ 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₁ is the answer.

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

Flex your programming muscles in Yandex.Algorithm, an annual international programming championship organised by Yandex, one of the largest internet companies in Europe and Russia's leading search provider.

Anyone over 18 – regardless of education, profession or programming style – has a chance of reaching the finals and winning up to the equivalent of $4,500, while participation in the preliminary rounds is also open to younger competitors from age 6. The top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt.

The warm-up round takes place online on May 10, starting at 21:00 Moscow time (UTC+3). It is followed by the qualification round, which takes place online on May 21 starting at 00:00 Moscow time (UTC+3), and running for 48 hours. To qualify for the elimination stage rounds you need to solve at least one problem in the warm-up or qualification rounds. The top 25 competitors after the elimination rounds advance to the finals in Minsk, Belarus.

See the schedule of all rounds here. Read more about Yandex.Algorithm and register for participation no later than May 22.

Take a look at 2015 problems and results here.

Good luck!

UPDATE 01. The warm-up round takes place tonight at 21:00 (UTC+3). You can qualify for the elimination in this round.

UPDATE 02. Analysis of the warm-up round.