Всем привет!

Меня зовут Леша, и я уже более 10 лет наслаждаюсь возможностью наблюдать за ростом студентов в Школе анализа данных. За это время много представителей сообщества codeforces окончили программу и получили значительный буст в индустриальной карьере и науке. Но сегодня я хочу сообщить, что самое время подать заявку на поступление в 2025, т.к. времени осталось не слишком много.

Доступ к контесту открыт, мы постарались сделать интересными задачи и по математике, и по программированию.

Если вы еще не заполнили анкету — то скорее заполняйте. Рекомендуем не затягивать — прием анкет до 4 мая, а тестирование занимает время.

Про контест:

• Стартовать можно в любое время до 19:00 5 мая MSK, после этого времени стартовать уже нельзя;
• У вас будет 5 часов на выполнение теста.

Важно: В задачах по программированию вы сразу увидите результат проверки на всех тестах (как открытых, так и скрытых), по математике — нет.

Мы за честность и прозрачность, поэтому убедительная просьба не делиться условиями, решениями и подсказками в открытом доступе.

Удачи! Будет сложно, но вам понравится!

P.S. Также оставлю ссылку на наш уютный канал, где обсуждаем жизнь в ШАД и интересные задачи.

Этот раунд был подготовлен разработчиками Яндекса.

Problem А. НольОдин

Для решения задачи сначала переведём строки в двоичные числа, а после сравним их. Поскольку из условия ясно, что числа могут получиться порядка $$$2^{333}$$$, сравнивать их будем без перевода в числовой тип данных.

#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. Плитки 2x2

Для решения введем классы эквивалентности (совпадения) плиток $$$2 \times 2$$$. Если плиток каждого класса в наборе будет не менее требуемого числа для картинки, то ответ будет положительный.

Для определения класса эквивалентности можно выбрать главного представителя класса. В случае с матрицей $$$2 \times 2$$$ подойдет минимальный кортеж из всех четырех поворотов матрицы.

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. Шары и коробки

Пусть $$$sumA = \sum_{i = 1}^k a_i$$$. Давайте научимся проверять, может ли некоторое число коробок $$$x, 1 \le x \le sumA$$$ удовлетворять всем условиям. Для этого должно выполняться следующее:

• $$$x$$$ является делителем $$$sumA$$$
• $$$a_i - x \cdot b_i \ge 0$$$ для любого цвета $$$i$$$

Таким образом, мы можем перебрать делители числа $$$sumA$$$ и для каждого проверить выполнение второго условия, а среди всех таких $$$x$$$, что условие выполняется, выбрать максимальный.

При выводе ответа нужно аккуратно рассмотреть случай $$$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. Матрица

Для удобства будем использовать следующие обозначения $$$n=2^{n'}$$$, $$$m=2^{m'}$$$.

1. Рассмотрим случай $$$n=m,\,n \gt 1$$$. После первого шага матрица будет иметь следующий вид:

После второго шага матрица будет иметь следующий вид:

Таким образом, после второго шага и до самого конца вся матрица будет заполнена одинаковыми числами.

Имеем, что суммарно различных чисел будет выписано $$$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. Рассмотрим случай $$$n \lt m$$$. После первого шага матрица будет иметь следующий вид:

После $$$i$$$-го из следующих ($$$m'-n'-1$$$) шагов матрица будет иметь следующий вид:

Обратим внимание, что в этих матрицах все числа более $$$nm$$$ встречаются только однажды (занимают целую строку одной из матриц). На следующем шаге и до самого конца вся матрица будет заполнена одинаковыми числами.

В отличие от первого случая мы можем рассмотреть каждую из $$$n$$$ строк матрицы отдельно ($$$n \lt 2^{15}$$$).

1. Рассмотрим случай $$$n \gt m$$$. После первого шага матрица будет иметь следующий вид:

После $$$i$$$-го из следующих ($$$n'-m'$$$) шагов матрица будет иметь следующий вид:

Следует отметить, что максимальный элемент матрицы на шаге $$$i$$$ меньше минимального элемента матрицы на шаге $$$i+1$$$.

Имеем, что суммарно различных чисел будет выписано $$$nm+\frac{m}{2}+m\log_2{\frac{n}{m}}+\log_2{\frac{m^2}{2}}$$$.

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. Сортировка матрицы

Рассмотрим множество нулей в отсортированной матрице. Тогда количество операций, это количество единиц первоначальной матрицы, которые лежат в этом множестве. Множество нулей образует диаграмму Юнга — в каждой строке множество клеток образует отрезок прижатый к левому краю и каждая последующая строка содержит меньше или столько же клеток множества. Поэтому нам нужно построить диаграмму Юнга заданного размера, которая содержит как можно меньше единиц.

Будем решать задачу динамическим программированием. Для каждой клетки матрицы рассмотрим прямоугольник с углами в этой клетке и в правом верхнем угле матрицы. Для каждого размера диаграммы Юнга внутри этого прямоугольника, посчитаем минимальное число единиц, которое в ней может содержаться. Клеток матрицы $$$O(nm)$$$ и размеров диаграммы Юнга $$$O(nm)$$$, поэтому нам надо посчитать ответы для $$$O((nm)^2)$$$ подзадач.

Покажем как подсчитать ответ в каждой из подзадач. Рассмотрим клетку в нижнем левом угле прямоугольника, в котором мы рассматриваем диаграмму Юнга. Она либо принадлежит диаграмме, либо нет.

Если она принадлежит диаграмме, то все клетки выше нее тоже принадлежат диаграмме Юнга. В таком случае мы свели задачу к прямоугольнику, у которого нижний левый угол на одну клетку правее, а размер диаграммы Юнга меньше на размер столбца. Чтобы посчитать сколько единиц этот столбец добавил к ответу, предпросчитаем для каждой клетки матрицы количество единиц нестрого выше нее в этом же столбце. Этот предпросчет можно сделать за $$$O(nm)$$$, идя сверху вниз.

Во втором случае, клетка в нижнем левом угле не принадлежит диаграмме. В таком случае мы свели задачу к прямоугольнику, у которого нижний левый угол на одну клетку выше. Ни размер диаграммы Юнга, ни ответ при этом не изменяются.

Остается взять минимум из этих двух случаев. Поскольку каждый случай можно рассмотреть за $$$O(1)$$$ времени, то всего нужно $$$O((nm)^2)$$$ действий. Состояния динамики можно рассчитывать сверху вниз и справа налево. Кроме того, можно хранить лишь текущую и следующую строку или столбец динамики. Это позволяет использовать лишь $$$O(\min(n^2m,nm^2))$$$ памяти.

Problem F. Переворот пути

$$$O(n^2)$$$ решение

Чтобы решить задачу за время $$$O(n^2)$$$, достаточно перебрать все пары $$$(p, q)$$$ и для каждой из них найти ответ за $$$O(1)$$$. В этом решении потребуется находить расстояние между любой парой вершин за $$$O(1)$$$. Для этого можно выполнить поиск в глубину или в ширину из каждой вершины, таким образом получим величины $$$d_{ij}$$$ — расстояние между вершинами $$$i$$$ и $$$j$$$.

Если $$$p$$$ и $$$q$$$ зафиксированы, то любая вершина $$$x$$$ находится в одном из следующих четырех состояний:

• $$$x$$$ лежит на пути между $$$p$$$ и $$$q$$$ включительно. В этом случае выполняется условие: $$$d_{px} + d_{xq} = d_{pq}$$$.
• $$$x$$$ лежит в части дерева за вершиной $$$p$$$ — $$$d_{xp} + d_{pq} = d_{xq}$$$.
• $$$x$$$ лежит в части дерева за вершиной $$$q$$$ — $$$d_{pq} + d_{qx} = d_{px}$$$.
• $$$x$$$ лежит на ответвлении на пути $$$p-q$$$. В этом случае, если все три условия выше ложные.

Рассмотрим варианты расположения вершин $$$1$$$ и $$$n$$$ относительно $$$p$$$ и $$$q$$$? Всего может быть 16 вариантов: $$$1$$$/$$$n$$$ (независимо) может иметь одно из описанных выше расположений (выбор из 4). Расстояние между $$$1$$$ и $$$n$$$ изменится только в следующих случаях (8 из 16):

• $$$1$$$ за вершиной $$$p$$$, $$$n$$$ на самом пути или на ответвлении от пути $$$p-q$$$.
• $$$1$$$ за вершиной $$$q$$$, $$$n$$$ на самом пути или на ответвлении от пути $$$p-q$$$.
• $$$n$$$ за вершиной $$$p$$$, $$$1$$$ на самом пути или на ответвлении от пути $$$p-q$$$.
• $$$n$$$ за вершиной $$$q$$$, $$$1$$$ на самом пути или на ответвлении от пути $$$p-q$$$.

Так как эти случаи идентичны, рассмотрим только первый из них. Итак, $$$1$$$ за вершиной $$$p$$$ и $$$n$$$ на пути или ответвлении от пути $$$p-q$$$. Перед разворотом расстояние равно $$$d_{1p} + d_{pn}$$$, а после разворота становится $$$d_{1p} + d_{qn}$$$. Подзадача на 2 балла решена.

Решение для цепочки

В этой подзадаче дерево вытянуто в цепочку. Разберем решение за $$$O(n)$$$. Расстояние изменяется только в том случае, если одна из вершин $$$p$$$ и $$$q$$$ расположена за пределами пути $$$1-n$$$, а вторая — внутри этого пути.

Сперва вычислим расстояние между $$$1$$$ и $$$n$$$ и умножим его на $$$\frac{n(n-1)}{2}$$$. Определим, как изменяется ответ после каждой операции разворота, не вычисляя его каждый раз в явном виде.

Будем считать, что $$$1$$$ расположена слева от $$$n$$$, обозначим количество вершин слева от $$$1$$$ через $$$a$$$, а количество вершин строго между $$$1$$$ и $$$n$$$ — через $$$b$$$.

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

Пусть $$$d$$$ величина, на которую изменяется расстояние между вершинами после разворота. Если $$$p$$$ занимает одно из $$$a$$$ положений слева от $$$1$$$, сколько есть походящих положений для $$$q$$$ на пути $$$1-n$$$ для фиксированного значения $$$d$$$? Рассмотрим иллюстрации для $$$d=1$$$ и $$$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] [ ] [ ] [ ]
...

Проанализировав эти случаи имеем. Для фиксированного $$$d$$$ ответ на вопрос выше $$$\min(a - d + 1, b + 1)$$$ (определяем, какой из участков закончится раньше). Поэтому к ответу следует прибавить $$$d \cdot \min(a - d + 1, b + 1)$$$.

Изменение длины может быть и отрицательным (расстояние между $$$1$$$ и $$$n$$$ уменьшится). Рассмотрим иллюстрации:

$$$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] [ ] [ ] [ ]
...

Количество подходящих под $$$d$$$ пар вершин равно $$$\min(b - d + 1, a + 1)$$$.

Положительные $$$d$$$ изменяются от $$$1$$$ до $$$a$$$, отрицательные $$$d$$$ изменяются $$$1$$$ до $$$b$$$ (по модулю). Для каждого значения $$$d$$$ находим изменение ответа за $$$O(1)$$$.

Бонус: зная $$$a$$$ и $$$b$$$, можно без итерирования по $$$d$$$ (из-за чего решение становится $$$O(n)$$$) вычислить ответ за $$$O(1)$$$. Сможете вывести нужную формулу?

Решение в общем случае

В решении за $$$O(n^2)$$$ мы разделили вершины на четыре класса в зависимости от расположения относительно $$$p$$$ и $$$q$$$. В общем случае также потребуется подобный подход, но относительно вершин $$$1$$$ и $$$n$$$.

Пусть величина $$$d_{1x}$$$ равна расстоянию от $$$x$$$ до $$$1$$$, а $$$d_{nx}$$$ — от $$$x$$$ до $$$n$$$. Пусть $$$m$$$ это расстояние между вершинами $$$1$$$ и $$$n$$$. Тогда вершины могут быть:

• за вершиной $$$1$$$ или сама вершина $$$1$$$: $$$d_{1x} + m = d_{nx}$$$,
• за вершиной $$$n$$$ или сама вершина $$$n$$$: $$$d_{1x} = m + d_{nx}$$$,
• строго на пути $$$1-n$$$: $$$d_{1x} + d_{nx} = m$$$, $$$x \ne 1$$$ и $$$x \ne n$$$,
• на ответвлении пути, если все условия выше ложные.

Расстояние изменяется в двух случаях:

• $$$p$$$ строго между $$$1$$$ и $$$n$$$ или одна из них, $$$q$$$ за вершиной $$$1$$$ или вершиной $$$n$$$,
• $$$p$$$ строго между $$$1$$$ и $$$n$$$, $$$q$$$ лежит на ответвлении, и корень ответвления $$$z$$$ лежит строго между $$$1$$$ и $$$n$$$ и $$$p \ne z$$$.

Первый случай:

Переберем значение $$$q$$$. Если вершина $$$q$$$ зафиксирована, как изменится ответ?

... [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] ...

Для первой строки иллюстрации ($$$p=1$$$) изменение равно $$$a$$$ (т.е. расстоянию $$$d_{1q})$$$, для второй строки — $$$a-1$$$, и т.д. Когда $$$n$$$ и $$$p$$$ смежные вершины, изменение равно $$$a-b$$$ (отрицательное при $$$a \lt b$$$). Общее изменение ответа равно сумме последовательных чисел от $$$a$$$ до $$$a - b$$$, может быть вычислено за $$$O(1)$$$.

Если правильно решить этот случай, то будет покрыта группа с линейным деревом.

Второй случай:

Вновь переберем значение $$$q$$$. Зная $$$d_{1q}$$$ и $$$d_{nq}$$$, можно найти корень ответвления $$$z$$$ (т.к. мы можем вычислить длину ответвления $$$\frac{d_{1q} + d_{nq} - m}{2}$$$, где $$$m$$$ это расстояние между $$$1$$$ и $$$n$$$, $$$m = d_{1n}$$$) и величины $$$d_{1z}$$$ и $$$d_{nz}$$$.

У нас вновь два аналогичных случая (выбор между $$$1$$$ и $$$n$$$), рассмотрим один из них.

                                                    ...
                                                    [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] ...

Здесь $$$a = d_{1z} - 1$$$, $$$b$$$ длина ответвления уменьшенная на 1. Как видно из иллюстрации, ответ изменяется, когда $$$p$$$ перемещается от $$$1$$$ к $$$z$$$, не включая $$$1$$$ и $$$z$$$. Вновь потребуется сумма арифметической прогрессии: $$$b + (b-1) + \ldots + (b-a+1)$$$, которую можем вычислить за $$$O(1)$$$.

Таким образом, в обоих случаях итерируемся по вершине $$$q$$$, для каждого выбора $$$q$$$ находим изменение ответа за $$$O(1)$$$, что дает общую трудоемкость $$$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;

Привет, Codeforces!!!

Меня зовут Леша, и я уже почти 10 лет руковожу филиалом ШАД в Минске. За это время много представителей сообщества окончили программу и получили значительный буст в карьере. Но сегодня я хочу сообщить, что самое время подать заявку на поступление в 2021, т.к. времени осталось не слишком много.

Подача заявки открыта до 19:00 4 мая.

За два года учёбы в ШАДе перед вами раскроется множество направлений современных компьютерных наук. Вы познакомитесь (или улучшите уже имеющиеся знания) с продвинутыми алгоритмами и структурами данных и с методами машинного обучения, научитесь делать выводы из данных и находить приближённые решения NP-трудных задач, узнаете, как работает автоматический переводчик и как научить бота разговаривать, разберётесь в устройстве систем, обрабатывающих огромные потоки данных в режиме реального времени, и беспилотного автомобиля. Будет сложно, но вам понравится!

Набор традиционно проходит в три этапа: онлайн-тест, письменный экзамен и очное собеседование. Вы можете поступить как в ШАД в Москве (очное обучение), так и в один из филиалов (в Минске, Екатеринбурге и Нижнем Новгороде, очно-заочное обучение) или на заочное отделение (из любой точки планеты). В Тель-Авиве обучение проходит по программе Y-Data.

Буду рад ответить на любые ваши вопросы про ШАД. И искренне желаю побольше Accepted в самых сложных задачах на вашем пути!

Привет, Codeforces!!!

До 19:00 10 мая открыт набор в Школу анализа данных Яндекса.

За два года учёбы в ШАДе перед вами раскроется множество направлений современных компьютерных наук. Вы познакомитесь (или улучшите уже имеющиеся знания) с продвинутыми алгоритмами и структурами данных и с методами машинного обучения, научитесь делать выводы из данных и находить приближённые решения NP-трудных задач, узнаете, как работает автоматический переводчик и как научить бота разговаривать, разберётесь в устройстве систем, обрабатывающих огромные потоки данных в режиме реального времени, и беспилотного автомобиля. Будет сложно, но вам понравится!

Набор традиционно проходит в три этапа: онлайн-тест, письменный экзамен и очное собеседование. Вы можете поступить как в ШАД в Москве (очное обучение), так и в один из филиалов (в Минске, Екатеринбурге и Нижнем Новгороде, очно-заочное обучение) или на заочное отделение.

В этом году в Школе принимают участие легендарные гроссмейстеры Codeforces как среди студентов V--o_o--V, так и среди преподавателей Zlobober. Ну и, конечно, много других представителей сообщества.

Буду рад ответить на любые ваши вопросы, куратор минского филиала Школы анализа данных

Стартовал ML-трек Яндекс.Алгоритма. Спешите принять участие)

Задачу для вас подготовила команда Яндекс.Алисы в лице Славы Алипова eik0u.

Создание диалоговой системы, которая может разговаривать с пользователем на любые темы, производя впечатление умного и интересного собеседника – одна из самых сложных и важных задач искусственного интеллекта в наши дни. Одна из основных подзадач в создании такой системы – генерация или подбор реплик, подходящих по смыслу для данного момента разговора и способных заинтересовать пользователя в продолжении беседы.

Мы хотим, чтобы участники нашего соревнования почувствовали себя ближе к созданию настоящего диалогового ассистента, способного увлекательно разговаривать с миллионами пользователей, как это ежедневно делает Алиса.

Свои решения можно отправлять до 10:00 23 апреля (МСК). ТОП-128 участников получат крутые футболки с символикой конкурса. А первые три места — денежные призы.

Поделиться идеями и обсудить конкурс с другими участниками можно в канале #proj_algo_alice сообщества OpenDataScience (ссылка на регистрацию http://ods.ai/).

Небольшой рассказ о конкурсе от автора: https://youtu.be/N2WMVUKUt8I?t=14m46s

Этот раунд был подготовлен разработчиками минского офиса Яндекса.

Задача А. Управление задачами

Рассмотрим решение, которое работает с квадратичной асимптотикой. Для этого будем действовать в соответствии с условием задачи: заведем счетчик последней закрытой задачи, будем проходить по списку задач от начала до конца, увеличивая счетчик, когда проходим через элемент массива задач, соответствующий следующей задаче. Из-за достаточно больших ограничений это решение не укладывается по времени.

Рассмотрим, в каком случае, мы уже не найдем никакой подходящей задачи до конца списка. Оказывается, только в том случае, когда после закрытия задачи с номером x следующая задача с номером (x + 1) расположена ближе к началу списка. Следовательно, для решения задачи нужно по каждому номеру задачи узнать ее позицию в списке задач, а затем подсчитать количество различных номеров x таких, что позиция задачи с номером (x + 1) меньше, чем позиция задачи с номером x.

К найденному количеству нужно добавить первый проход по списку задач. Итоговая трудоемкость алгоритма .

Задача B. Междугороднее общение

Задача "Междугороднее общение" не содержит особой алгоритмической идеи, поэтому нужно аккуратно реализовать описанное в условии задачи поведение системы бронирования.

Мы можем зафиксировать число от 0 до 23 (час, в который будем проверять возможность организации встречи). После этого в каждом из городов нужно проверить наличие свободной переговорки.

Отметим, что при больших ограничениях сохранить свободную переговорку для каждой пары (город, час) следовало бы до обработки запросов. Это позволило бы всегда отвечать на запрос за время пропорциональное количеству городов, а не суммарному количеству переговорок.

Задача C. Запуск тестов

Для этой задачи можно придумать несколько различных подходов к решению задачи, рассмотрим два из них.

Первое решение основано на подсчете количества раз, сколько раз тест с номером x будет запущен. В исходной системе каждой тест запускается один раз, а в новой системе 2^d(x), где d(x) расстояние от корневого тест до теста с номером x. Это утверждение несложно доказывается методом математический индукции, также заметить этот факт можно было внимательно изучив описание тестовых примеров из условия. Для подсчете d(x) достаточно обойти дерево любым обходом.

Второй метод решения основан на динамическом программировании. Пусть T(x) равно суммарному времени работы теста с номером x, т.е. времени работы тестов, от которых он зависит, и времени проверки a_x. Запишем соотношение:

Для вычисления ответа T(1) также достаточно одного обхода дерева (в данном случае DFS).

Трудоемкость решения задачи .

Задача D. Среднее арифметическое кодирование

Сразу следует рассмотреть такую задачу: на какое количество слагаемых можно разбить число n, если все слагаемые должны быть степенями двойки с целыми неотрицательными степенями. Покажем, что для любого целого k от popcount(n) до n это возможно (где popcount(n) это количество установленных бит в двоичной записи n).

Очевидно, что нельзя использовать меньшее чем popcount(n) число слагаемых, и большее n. Если у нас есть разложение в x слагаемых (x < n), то среди них есть слагаемое 2^t с положительной степенью t. Его мы можем заменить на два слагаемых 2^t - 1, получив разложение с (x + 1) слагаемым. Разложение из popcount(n) слагаемых строится из двоичного представления числа.

Для решения задачи будет перебирать длину последовательности k (k ≥ 1), пока не найдем подходящее. Как показано выше, нужно найти минимальное k, что popcount(kn) ≤ k, а после этого построить требуемое разложение. Для ограничений задачи k не превосходит 60 (60·(2⁵⁰ - 1) < 2⁶⁰ - 1 = 2⁰ + 2¹ + ... + 2⁵⁹).

Задача E. Соединение серверов

Требуется чтобы в графе соединений не было мостов, следовательно степень всех вершин не менее двух. А так как сумма степеней всех вершин равна 2·n + 2, то у нас возможны два случая:

• есть одна вершина степени 4;
• есть две вершины степени 3.

Рассмотрим первый случай. Граф представляет собой объединение двух циклов длины (m + 1) и (n - m) с общей вершиной. В этом случае нам нужно выбрать какие вершины попадут в первый цикл (остальные попадут во второй), и в каком порядке вершины окажутся на этих циклах. Общая формула имеет следующий вид

Рассмотрим второй случай. В графе есть две вершины степени три, которые соединены между собой цепочками ребер, на которых расположены все остальные (n - 2) вершины. Сразу обратим внимание, что соединение с нулем дополнительных вершин (ребро) может быть только одно. Пусть на соединениях расположены a, b и c вершины (a ≤ b ≤ c). Рассмотрим несколько случаев:

• 0 ≤ a < b < c, тогда количество соединений равно ;
• 0 < a = b < c, тогда количество соединений равно ;
• 0 ≤ a < b = c, тогда количество соединений равно ;
• 0 < a = b = c, тогда количество соединений равно .

Собирая все формулы вместе, получаем итоговый результат.

Задача F. Повторения

Для решения этой задачи обратимся к строковой терминологии. Бордером строки s называется какая строка y, что x начинается и заканчивается на y.

Тогда в задаче нам для каждого префикса исходного текста нужно найти максимальный по длине бордер, которых имеет еще хотя бы одно дополнительное вхождение. Для этого можно найти все бордеры префикса, и в порядке убывания длин найти найти первый, который имеет дополнительное вхождение.

Для поиска всех бордеров можно использовать префикс-функцию. Дополнительно вспомнив, что π(i) — длина максимального бордера, а длины всех бордеров префикса длины i можно перечислить, пройдя по последовательности π(i), π(π(i)), π(π(π(i))), ... и т.д.

Следующий интересный факт: у бордера длины π(π(i)) всегда есть не менее трех вхождений: первое начинается в начале строки, второе заканчивает в позиции i, а третье заканчивается в позиции π(i).

Следовательно, для полного решения задачи нам осталось научиться проверять, есть ли дополнительное вхождение максимального по длине бордера (длины π(i)). Чтобы такое вхождение было, должна найтись позиция j (j < i), в которой π(j) ≥ π(i). Для быстрой проверки такого неравенства достаточно хранить префиксный максимум значений префикс-функции.

Трудоемкость решения задачи линейная от длины текста.

Спасибо всем участникам нашего соревнования за множество успешных посылок по задачам!

Этот комплект для вас подготовили: Romka, Chmel_Tolstiy и Ixanezis. Спасибо Ивану Gassa Казменко за помощь в подготовке текстов задач и разбора.

Задача А. Правописание

В задаче достаточно маленькие ограничения для того, чтобы можно было решить её "в лоб", за O(N²L), где N — количество слов в словаре, а L — длина слова.

Для получения такой сложности достаточно для каждого слова проверить, может ли оно являться тем самым "правильным" словом, не содержащим ошибок. Для этого нужно проверить, что все остальные слова отличаются от него не более чем в одной букве: проходим по всем словам ещё раз и вычисляем количество позиций, в которых выбранное слово отличается от всех других слов. Если для всех слов отличия есть не более чем в одной позиции, выбранное слово вполне имеет право быть тем "правильным" словом, что мы ищем.

Для этой задачи также существует более быстрое решение за O(NL), но его не обязательно было здесь применять.

Задача B. Голосовые предупреждения

Для каждого варианта предупреждения вычислим расстояние D_i, за которое нужно начинать произносить данный вариант. Это можно сделать по формуле: D_i = X_i + V·(t_i + T_phrase). После вычисления нужно выбрать минимальный вариант, а среди нескольких одинаковых — вариант с минимальным индексом, как требуется в условии задачи.

Задача C. Турнир по настольному теннису

Для решения этой задачи необходимо сделать следующее наблюдение. Из условия задачи следует, что участники соревнования набрали 2·N - 2, 2·N - 3, \ldots, N - 1 очков. А отсюда следует, что победитель выиграл матчи у всех остальных, участник, занявший второе место, победил всех, кроме победителя, и так далее. Участник, занявший последнее место, проиграл все матчи.

Следовательно, если мы зафиксируем порядок номеров участников, в котором они должны закончить турнир, то мы можем найти вероятность именно такого окончательного исхода. Для этого достаточно найти произведение необходимых вероятностей из матрицы вероятностей p_ij. Для генерации всех перестановок можно использовать метод std::next_permutation (C++) или, к примеру, реализовать рекурсивный перебор.

Таким образом, исходная задача решается описанным алгоритмом за время O(N²·N!). Используя идеи динамического программирования, этот подход можно ускорить и получить алгоритм, работающий за O(N·2^N).

Задача D. Числовое сжатие

Будем решать задачу методом динамического программирования. К задаче есть несколько различных подходов, мы опишем только один из них.

Заметим, что битовых последовательностей длины L c K чередующимися группами битов, начинающихся с группы с нулевым битом, в точности C(L - 1, K - 1). Действительно, так как все группы не пустые, то нам среди L - 1 границ между соседними элементами последовательности битов нужно выбрать K - 1, которые и будут разделять соседние группы с различными битами.

Рассмотрим функцию F(L, K) — сумма результатов битового сжатия всех численных последовательностей длины L с K чередующимися группами битов, которых, как мы уже знаем, C(L - 1, K - 1).

Для вычисления значения F(L, K) можно воспользоваться следующим подходом. Переберём размер t самой правой группы (младший двоичный разряд результата сжатия). Тогда легко получить следующее соотношение:
F(L, K) = sum(t = 1..L - 1) 2·F(L - t, K - 1) + is_even(K)·C(L - t - 1, K - 2) при L > 1; кроме того, F(1, K) = 0.

Для решения исходной задачи найдем сумму результатов числового сжатия для всех чисел X, меньших N + 1. Все эти числа можно разбить на несколько групп. Пусть в группу G_i попадут все числа X, у которых старший отличающийся бит от числа N + 1 стоит в позиции i. Обратим внимание, что это автоматически означает, что в X этот бит равен 0, а в N + 1 — равен 1. Для вычисления результата суммирования по числам из одной группы нам пригодятся результаты числового сжатия префикса N + 1 до позиции i и функция F(L, K).

Функция должна вычислить результат на префиксе числа N + 1, но только без учёта последней группы, если она содержит бит 0. Это связано с тем, что такую группу мы осознанно включаем в F(L, K).

Описанное решение имеет трудоёмкость , но вы его можете ускорить до . Может даже быстрее?

Задача E. Сборка велосипедов

Заметим, что в условии того, подходит ли нам четвёрка шестерней, можно заменить деление на умножение: четыре шестерни нам подходят, если их можно разбить на пары так, чтобы произведения диаметров в парах были равны.

Для каждого диаметра D посчитаем количество шестерней C_D с таким диаметром, а также для всех возможных P посчитаем количество Cnt_P пар, дающих произведение P. Это можно сделать либо за O(N²) с использованием контейнера HashMap / unordered_map или аналогичного, либо с использованием сортировки за . Теперь рассмотрим все пары чисел. Для каждой пары шестерней с диаметрами D1 и D2 с произведением D1·D2 = P добавим к ответу Cnt_P - 1: как количество "других" пар с таким же произведением. К сожалению, при этом, возможно, среди добавленных пар оказались и те, которые включают в себя шестерни, уже использованные в текущей рассматриваемой паре. Поэтому, если в текущей паре диаметры шестерней отличаются, то из ответа нужно вычесть C_D1 + C_D2 - 2, а если не отличаются, то (C_D1 - 2)·2.

После этого у нас будут учтены все необходимые четвёрки шестерней, однако, к сожалению, по нескольку раз. Каждый набор из 4 шестерней вида D D D D (одинакового диаметра) будет учтён 6 раз, каждый набор вида D E D E будет учтён 4 раза, каждый набор вида D E F G или D E E F будет учтён 2 раза. Для того, чтобы это исправить, нужно для каждого диаметра D вычесть из результата , для каждой пары диаметров D E вычесть C_D·(C_D - 1)·C_E·(C_E - 1)·2, и затем весь результат разделить на два.

Задача F. Радары

Сначала рассмотрим случай, когда у нас всего одна контрольная точка. Ответ здесь тривиален: проще всего установить радар в точку, совпадающую с контрольной, и получить эффективность, равную 1.

Теперь рассмотрим случай, когда у нас две или больше контрольных точек. Пусть мы нашли ответ — расположение радара с наибольшей возможной эффективностью. Можно заметить, что мы можем перемещать радар относительно точки его расположения до тех пор, пока как минимум какие-то две контрольные точки не окажутся на целочисленных расстояниях от радара. Дальнейшее перемещение радара в любом из направлений, в результате которого любая из этих точек переходит через границу целочисленного радиуса, приводит к неувеличению эффективности радара (иначе наше предположение о том, что мы нашли расположение радара с наибольшей эффективностью, неверно).

Поэтому попробуем найти именно такое оптимальное расположение радара, при котором как минимум две контрольные точки лежат на целом расстоянии от него. Для этого переберём пару точек и расстояния r₁ и r₂, на которые эти точки отстоят от радара. Далее нам нужно найти точку на плоскости для размещения радара — это точка пересечения окружностей с радиусами r₁ и r₂ и с центрами в выбранных точках.

Таких точек может быть разное количество:
- 0, если окружности не пересекаются вообще,
- 1, если окружности касаются друг друга (в том числе внутренним образом),
- 2, если окружности пересекаются.

Для каждой точки пересечения окружностей посчитаем эффективность расположения радара в ней по определению и выберем глобальный максимум их всех таких расположений.

Итоговая сложность алгоритма получается равной O(N³·R²), где N — количество контрольных точек, а R — максимальный рассматриваемый нами радиус. Поскольку точки находятся в квадрате с координатами от 0 до 50, максимальное расстояние, которое вообще имеет смысл рассматривать, равно .

P.S. Если вы заметили опечатку сообщите мне об этом личным сообщением.

Буквально вчера завершился очередной ACM ICPC World Finals. Мы передаем наши поздравления всем победителям, медалистам и обладателям специальных призов!

Сегодня мы хотим напомнить, что завтра, 21 мая, в 00:00 (UTC+3) начнется квалификационный раунд Яндекс.Алгоритма. Для участия в квалификации вам следует зарегистрироваться и начать виртуальное соревнование в любой момент до 23 мая 00:00 (UTC+3).

Как и во всех раундах Яндекс.Алгоритма, будет предложено 6 задач различной сложности. Для того, чтобы квалифицироваться в отборочные раунды и сразиться за поездку на финал в Минск, денежные призы и футболки, необходимо решить хотя бы одну задачу.

В этом году специально для студентов Яндекс.Алгоритм предлагает поучаствовать в стажерском треке. Более подробную информацию о нем можно найти в правилах чемпионата.

Успехов! До встречи на Яндекс.Алгоритме!

P.S. Квалификационный раунд уже начался! Задачи подготовили Romka, Ixanezis и Chmel_Tolstiy.

EDIT. Опубликован разбор задач квалификационного раунда.

Спасибо всем участникам нашего соревнования за множество успешных посылок по задачам!

Этот комплект для вас подготовили: snarknews, Chmel_Tolstiy, Gassa, Zlobober. Разбор для вас подготовили snarknews и Gassa.

Задача А. Буквы адреса

Поскольку множества гласных и согласных не пересекаются, при лексикографическом сравнении раньше будет та последовательность, которая начинается с буквы, которая раньше идёт в алфавите. Так что просто идём по строке, запоминаем первую гласную и первую согласную, которая нам встретилась. Как только встретились обе, сравниваем и немедленно выдаём ответ. Необходимо не забыть про случай, когда одна из строк пустая.

Задача B. Байтландский талер

Считываем первый обменный курс, инициализируем считанным значением переменные и . Затем в цикле считываем N - 1 оставшихся курсов. Если курс больше , присваиваем считанное значение переменной , если курс меньше — переменной .

Ответ равен .

Задача C. Шашматы

Так как чёрная шашка каждый ход уменьшает номер горизонтали, то всего шашка может сделать не более 7 ходов, на каждом ходу у неё не более двух вариантов выбора. Соответственно, конь тоже может сделать не более 7 ходов (даже если конь ходит первым, то, если шашка сделала 7 ходов, она дошла до первой горизонтали и игра заканчивается победой чёрных, то есть восьмого хода коня не происходит). Итого получаем не более 2⁷·8⁷ = 2²⁸ вариантов.

Все эти варианты можно за отведённое время перебрать рекурсивно. Для этого реализуем две функции:

• функция хода шашки, которая проверяет условия выигрыша/проигрыша на данном ходу (то есть что шашка достигает после этого хода первой горизонтали, берёт коня или же оказывается "запертой"), если ни одно из этих условий не выполнено, то вызывается функция хода коня для всех возможных вариантов хода шашки;

• функция хода коня, которая проверяет условия выигрыша на данном ходу (то есть что конь может взять шашку), если соответствующее условие не выполнено, вызывается функция хода шашки для всех возможных ходов коня (которых не более восьми).

В основной функции считываются данные и в зависимости от того, кто ходит первым, вызывается функция хода коня или функция хода шашки.

Задача D. Город в пустыне

Рассмотрим диагональ выпуклого пятиугольника. Одна из вершин лежит по одну сторону этой диагонали, две по другую и две лежат на этой диагонали. Первая вершина, соединённая диагоналями с двумя вторыми, даёт две точки пересечения, лежащие на выбранной диагонали. Остальные четыре вершины образуют выпуклый четырёхугольник, одной из сторон которого является исходная диагональ. Соответственно, точки пересечения остальных диагоналей пятиугольника (это точка пересечения диагоналей четырёхугольника и точки пересечения отрезков, соединяющих точки на одной из сторон с вершинами, с диагоналями четырёхугольника) лежат внутри четырёхугольника. Получаем, что точки пересечения диагоналей, не лежащие на данной диагонали, находятся от неё с одной стороны. Тем самым точки пересечения диагоналей выпуклого пятиугольника должны быть вершинами некоторого выпуклого пятиугольника D (сторонами которого являются отрезки диагоналей).

В этом случае исходные вершины восстанавливаются как точки пересечения прямых, содержащих несмежные стороны пятиугольника D. При этом точка пересечения каждой пары сторон должна существовать (то есть стороны не должны быть параллельны) и лежать по разные стороны с вершинами пятиугольника D относительно прямой, которая соединяет вершины сторон соответствующей пары (это следует из выпуклости исходного пятиугольника). Легко увидеть, что, если все эти требования выполняются, то восстановленный пятиугольник является выпуклым.

Тем самым решение состоит в построении выпуклой оболочки заданных точек, проверке, принадлежат ли все 5 точек выпуклой оболочке, и проверке для каждого i, существует ли точка пересечения прямых A_iAi + 1 и A_i + 2A_i + 3 и лежит ли она по разные стороны с точкой A_i (или любой другой из трёх оставшихся точек) от прямой A_i + 1A_i + 2 (сложение в индексах производится по модулю 5). Если какая-то из проверок не прошла — ответ No, иначе ответ Yes.

Задача E. Кодирование

Если найти соответствующие p и q невозможно, то f(x) — перестановочный многочлен по модулю 2^m (то есть он переводит последовательность из целых чисел от 0 до 2^m - 1 в какую-то их перестановку).

Рассмотрим некоторые свойства перестановочных многочленов.

• Если m = 1, то сумма всех коэффициентов, кроме свободного члена, обязана быть нечётной. Иначе f(0) = a₀ и f(1) = a₀ + (a₁ + a₂ + ... + a_n) имеют одинаковый остаток от деления на 2, и многочлен перестановочным не является.

• Если многочлен является перестановочным по модулю 2^m, то он является перестановочным и по модулю 2^m - 1. Пусть это не так, тогда существуют два таких числа p и q (0 ≤ p, q < 2^m - 1), которые дают одинаковые остатки f(p) и f(q) от деления на 2^m - 1. Рассмотрим числа p, q, p + 2^m - 1 и q + 2^m - 1. Значения f(p + 2^m - 1) и f(p) имеют одинаковые остатки от деления на 2^m - 1: вычтем полиномы друг из друга и заметим, что разность делится на 2^m - 1. Аналогично сделаем для f(q + 2^m - 1) и f(q), то есть получаем четыре числа f(p), f(q), f(p + 2^m - 1), f(q + 2^m - 1), которые дают различные остатки от деления на 2^m и одинаковые — на 2^m - 1. Но таких чисел может быть не более двух. Противоречие.

• Если многочлен является перестановочным по модулю 2^m и m > 1, то a₁ нечётно. В самом деле, пусть a₁ чётно. Тогда берём p = 0 и q = 2^m - 1. Легко видеть, что f(q) = a₀ + a₁·2^m - 1 + a₂·2^2m - 2 + ... + a_n·2^nm - n = f(0) + (a₁ / 2)·2^m + 2^m·r, где r — целое число (так как при m > 1 k(m - 1) - m ≥ 0), тем самым f(p) и f(q) дают одинаковые остатки от деления на 2^m, что противоречит свойствам перестановочных многочленов.

• Рассмотрев примеры для m = 2 и m = 3, можно заметить, что у перестановочных многочленов сумма коэффициентов при чётных степенях оказывается чётной. Это утверждение верно и для более высоких m; более того, перечисленные свойства являются необходимыми и достаточными. Полное доказательство можно найти в англоязычной статье Ronald R. Rivest.

Таким образом, всё, что вам нужно — это проверить, что сумма a₁ + a₂ + a₃ + ... + a_n нечётна, и что при m > 1 к тому же a₁ нечётно, а сумма коэффициентов при чётных степенях чётна. Если эти требования выполняются, то ответом будет No (то есть многочлен перестановочный, и требуемых p и q найти нельзя). Иначе ответ — Yes.

Задача F. Плейлист в будущем

Вначале найдём множество K вершин, принадлежащих к одной компоненте сильной связности, для которых верно следующее свойство: не существует ни одного ребра, которое начинается в вершине, принадлежащей этому множеству, и заканчивается в вершине, ему не принадлежащей.

Из ограничений задачи видно, что такое множество можно выбрать единственным способом, и оно будет содержать вершину 1. Найти это множество можно, например, поиском в глубину, начиная с вершины 1.

Очевидно, что после 10²⁰¹⁶ проигранных композиций вероятность исполнения композиции извне этого множества можно при требуемой в задаче точности считать нулевой (а 10²⁰¹⁶ — бесконечным количеством итераций).

Вектор вероятностей p после бесконечного количества композиций должен удовлетворять системе линейных уравнений pW = p, где W — матрица смежности подграфа, построенного на вершинах из множества K.

Таким образом, мы имеем однородную систему уравнений (W^T - I)p^T = 0 и нормирующее уравнение . Довольно просто можно показать, что система всегда будет совместной; система может быть решена, например, методом Гаусса.

В качестве ответа в таком случае надо взять p₁.

P.S. Если вы заметили опечатку сообщите мне об этом личным сообщением.

Мы открываем Алгоритм-2016 — чемпионат Яндекса по программированию с оригинальными правилами, подарками и денежными призами для лучших участников. 512 лучших участников отборочного этапа получат футболки с символикой конкурса.

Если вы чувствуете в себе силы побороться с опытными программистами за призовой фонд в 540 тысяч рублей, ещё не поздно зарегистрироваться и показать, на что способны. Регистрация открыта до конца квалификационного раунда.

10 мая в 21:00 по московскому времени (UTC+3) пройдёт разминочный раунд, а весь день 21 и 22 мая можно будет поучаствовать в квалификационном. Все, кто решит в них хотя бы одну задачу, перейдут в отборочный этап, в трёх раундах которого определятся 25 финалистов. Финал пройдёт 28 июля в Минске.

Подробная информация о сроках проведения доступна в правилах чемпионата. Полное расписание чемпионата доступно по ссылке.

Ожидая начала чемпионата, можно посмотреть на то, как проходил чемпионат в 2015 году.

Желаем удачи!

UPDATE 01. Разминочный раунд состоится уже сегодня в 21:00 (UTC+3). Вы можете квалифицироваться в отборочные раунды, решив хотя бы одну задачу сегодня.

UPDATE 02. Опубликован разбор задач разминочного раунда.

Не так давно я решил попробовать все же отмечать некоторые соревнования как тренировки для важных для меня команд.

Оказалось, что механизм добавления соревнования в группу, не добавляет его сразу в созданный здесь рейтинг. Лично мне кажется, что возможность выставить сразу галочку в какой рейтинг его добавить лишило бы меня необходимости делать двойную работу.

Но более меня беспокоит, что я не могу влить никакие внешние результаты в группу и пересчитать на их основании рейтинг. Меня бы устроил любой вариант. Например, я создаю размеченный файл, в котором в состав команды вписываю логины с CodeForces тех, кто этот контест решали и их результаты, а если будет в этом необходимость, то после дорешивания еще и дополнительную информацию добавляю (чтобы было понятно, что рейтинг еще раз нужно пересчитать). Я бы хотел добавлять соревнования с TopCoder, OpenCup и других.

Уважаемое сообщество, убедите меня, что я хочу странного. Никто из вас не сталкивался с подобной трудностью?

P.S. Я признателен за возможность вести группу и там ставить множество контестов из Тренировок и собирать Mashup, но внешние соревнования никто не отменял.