Разбор задач квалификации: Engine
A. Скрытый друг
Сохраним в двумерный массив размера n на n информацию о том, кто кого добавил в друзья. В j-й клетке i-й строки сохраним 1, если пользователь j находится в друзьях у i, и 0 в противном случае.
Тогда необходимо найти все такие пары (i, j), чтобы в клетке (i, j) находилась единица, а в клетке (j, i) — ноль. Это можно сделать, проверив все пары за O(n^2).
B. Code Review
Когда человек приходит в чат с новым коммитом, предыдущее сообщение в чате всегда ещё никем не просмотрено. Если оно оставлено другим автором, разработчик сможет сделать ему ревью, а если его оставил этот же автор, он ничего не сделает.
Таким образом, нужно вывести в ответ хеши всех коммитов, сразу же после которых не было коммита от другого автора.
C. #define Задача B ...
Сколько всего чисел, написанных через запятую, скрывается за An(x)? Всего их 4^n.
Исходно в A25(x) передали x = 0. Всего чисел в массиве 4^25. Разобьём их на 4 группы подряд идущих чисел одинакового размера — группы 0, 1, 2 и 3. Какой группе принадлежит число, находящееся на позиции pos? Номер этой группы равен i = ⌊pos/4^24⌋. В зависимости от номера группы к числу x прибавляется 0, 1, 3 или 4. Прибавим к текущему значению x соответствующее число и перейдём к списку чисел в группе, которой принадлежит число на позиции pos. Этот список создаётся с помощью директивы A24(x). Для этого надо вычесть из pos значение 4^24⋅i, так как именно столько чисел мы пропустили, забыв про группы, предшествующие группе i.
Повторим процесс: вычислим номер группы по формуле i = ⌊pos/4^23⌋, прибавим соответствующее число к текущему значению x, вычтем из pos значение 4^23⋅i и перейдём к A23(x). Будем так делать, пока не придём к A0(x). Директива A0(x) раскрывается в x, так что текущее значение x и есть значение массива на исходной позиции pos.
Итого, мы можем найти ответ для одного запроса, используя 25 или 625 итераций цикла в зависимости от реализации.
D. Storage2
В этой задаче возможны всего 29 разных входных данных, поэтому можно было написать программу, которая считает все 29 ответов на задачу, но не укладывается в Time Limit, а потом отправить решение с вбитыми константами.
Чтобы написать такую программу, достаточно просто перебрать все 2^28 вариантов потерянных блоков и для каждого варианта восстановить всё, что можно восстановить согласно алгоритму, описанному в условии. На основе этих данных легко посчитать вероятность и матожидание, требуемые в задаче.
E1. Контрольная сумма
В простой версии задачи можно написать совершенно любое решение. Например, для каждого запроса перебрать 2^32 вариантов того, как можно изменить числа, запустить стандартную утилиту CRC32 (или скачать где-нибудь её реализацию) и проверить, изменяется ли чек-сумма.
E2. Контрольная сумма
Во второй версии задачи подразумевалось, что нужно сделать что-нибудь чуть более содержательное. Решение с явным перебором ответов и подсчётом чек-суммы, скорее всего, не уложится в разумное время выполнения (8⋅50000⋅2^32 — больше, чем 10^15 операций, хотя с оптимизациями и можно успеть посчитать это за несколько часов/дней).
Есть несколько способов оптимизировать это решение, избавившись от зависимости либо от nn, либо от 2^32. Например, можно заметить, что при изменении одного любого бита в любую сторону (с 0 на 1 и с 1 на 0) к значению CRC32 применяется XOR с числом, не зависящим от остальных битов. Так, можно для каждого бита исходной последовательности посчитать, как изменится чек-сумма при изменении данного бита. После этого можно снова решать задачу за 2^32 на каждый запрос.
E3. Контрольная сумма
Существует несколько полных решений данной задачи. Например, можно воспользоваться наблюдением из подзадачи E2.
Пусть b_0, b_1, …, b_(8⋅n−1) — последовательность битов, соответствующая последовательности a_0, a_1, …, a_n−1. Для каждого бита j существует такое число t_j, что CRC32(b_0⊕d_0, b_1⊕d_1, …, b_(8⋅n−1)⊕d_(8⋅n−1)) = CRC32(b_0, b_1, …, b_(8⋅n−1)) ⊕ d_0t_0 ⊕ d_1t_1 ⊕ … ⊕ d_(8⋅n−1)t_(8⋅n−1) — изменения данной последовательности.
Для каждого запроса у нас есть 32 варианта, чтобы выбрать между 0 и 1 для соответствующих значений d_j, которые можно изменять в данном запросе. Зная соответствующие значения t_j, можно составить систему из 32 линейных уравнений с 32 неизвестными над полем по модулю 2. Можно показать, что у неё есть единственное решение, из которого и получается ответ к задаче.
Значения t_j можно посчитать за 32⋅8⋅n, используя рекурренту вида t_j = ∑ (k = 0…31) P_k⋅t_(j+1+k), где P_k — 32 бита, соответствующие записи развёрнутого полинома, используемого в алгоритме.
F. Шардирование постов
Для каждого сервера будем поддерживать отрезок постов, среди которых, возможно, есть k-й. Изначально в этот отрезок будут попадать все посты. Для каждого отрезка возьмём средний пост в нём и узнаем его ID.
Рассмотрим отрезок, у которого ID среднего поста самый маленький (пусть он равен X). Тогда всего существует не более ∑len_i/2 постов с ID не больше X. Если k больше ∑len_i/2, то можно с уверенностью сказать, что первая половина отрезка, у которого самый маленький средний ID поста, нам не интересна. Тогда можно уменьшить этот отрезок в два раза и рекурсивно продолжить решать задачу.
Аналогично в некоторых случаях можно убрать верхнюю половину отрезка с самым большим средним ID.
Можно показать, что всегда получится воспользоваться либо первой опцией, либо второй. А значит, каждый раз один из отрезков уменьшится в два раза. После этого необходимо будет сделать один дополнительный запрос, чтобы узнать ID среднего поста в новом отрезке. Таким образом за Slog(len) запросов можно узнать k-й пост.