Pro для редактирования документа

1.

есь на DeepL Pro для редактирования данного документа.
ную информацию можно найти на странице www.DeepL.com/pro.

2.

Решите второй раунд
вопросов PMCC
79brue / azberjibiou / blackking26

3.

Оглавление
• Отдел 2: Решения от A до F
• Отдел 1: Решения от A до F
• Решения G, H

4.

Div2A: Создание пароля
• Автор: 79brue
• Количество решенных задач: 21

5.

Div2A: Создание пароля
• Тело
• Вам дана строка длины и строка , в которой она
является подстрокой.
• Выведите любой , такой, что и - единственные
длины , которые являются общими подстроками .

6.

Div2A: Создание пароля
• Решить
• Если установлено, длина подстроки равна только
.
• также является общей подстрокой для и , так что
это решает проблему.

7.

Div2A: Создание пароля

8.

Div2B: Игрушки из волшебного
камня
• Представлено: azberjibiou
• Количество решенных задач: 18

9.

Div2B: Игрушки из волшебного
камня
• Тело
• Вам дана перестановка длины .
• Отсортируйте со 100 или менее интервальными
переворотами.

10.

Div2B: Игрушки из волшебного
камня
• Подзадача 1 (20 баллов)
• так что должен справиться с этим.
• Использует пузырьковую сортировку, алгоритм
сортировки на основе сравнения.
• Если вы выполняете сортировку пузырьками, то
вполне можно заменить две замены чисел в
соседних позициях операцией перелистывания
диапазона, включающей два числа.
[2 1 3] → [1 2 3]
• Это можно решить, перевернув интервал примерно
раз.

11.

Div2B: Игрушки из волшебного
камня
• Подзадачи 1, 2 (45 баллов)
• поэтому нам нужно перевернуть секцию примерно
раз.
• Давайте рассмотрим, как мы применили сортировку
вставкой.
• Вставить любое число в любую позицию можно,
перевернув два бина, как показано ниже.
[1 2 4 5 6 3] → [1 2 3 6 5 4] → [1 2 3 4 5 6]
• Сортировка
таким
образом
позволяет
отсортировать
последовательность,
перевернув

12.

Div2B: Игрушки из волшебного
камня
• Подзадачи 1, 2, 3 (100 баллов)
• поэтому нам нужно перевернуть секцию примерно
раз.
• Найдите в массиве и переверните секцию из
положения в крайнее правое, чтобы оказалась в
крайнем правом углу.
• Повторите этот процесс для оставшегося
количества .
• Вы можете выровнять , перевернув секции в
пачке.

13.

Div2C: Перемещение светлого
камня
• Автор: 79brue
• Количество решенных задач: 18

14.

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

15.

Div2C: Перемещение светлого
камня
• Подзадача 2 (5 баллов)
• поэтому за такой выбор не полагается наказание.
• Поэтому оптимально выбрать меньший из .
• Ответ: .
• Временная сложность составляет .

16.

Div2C: Перемещение светлого
камня
• Подзадача 1 (12 баллов)
• очень мала, поэтому вы можете попробовать все
возможные варианты.
• Временная сложность составляет .

17.

Div2C: Перемещение камня света
• Подзадачи 1, 2, 3 (100 баллов)
• Это типичная проблема DP, и вы можете создать
таблицу DP, как показано ниже.
• Минимальная сумма затрат и штрафов при выборе в
качестве первого варианта, в качестве второго
варианта и в качестве третьего варианта.
• Минимальная сумма затрат и штрафов при выборе в
качестве первого варианта, в качестве второго
варианта и в качестве третьего варианта.

18.

Div2C: Перемещение светлого
камня
• Соответствующее выражение для зажигания можно
вычислить и получить ответ .

19.

Div2D: Копаем колодец
• Представлено: azberjibiou
• Количество решенных задач: 6

20.

Div2D: Копаем колодец
• Тело
• Вам дана последовательность длины .
• определяется как последовательность для ,
которая является .
• Учитывая размер , найдите -е наименьшее число
от до .

21.

Div2D: Копаем колодец
• Подзадача 1 (35 баллов)
• чтобы вы могли создать свой собственный ,
отсортировать его и получить ответ.
• Временная сложность составляет .

22.

Div2D: Копаем колодец
• Подзадачи 1, 2 (100 баллов)
• Поскольку диапазон чисел велик, выполним
двоичный поиск.
• Мы ищем ответ, по крайней мере, на , который
удовлетворяет следующим условиям
имеет или меньше, чем , или больше, чем .
• Таким образом, мы можем изменить задачу на
решение
задачи
принятия
решения
(задача
принятия решения - это задача, ответ на которую

23.

Div2D: Копаем колодец
• Есть два способа найти количество отсчетов в ,
которые меньше или равны .
• Первый способ - это прикрепить и провести
биссектрису , чтобы найти и сосчитать их, что
занимает в общей сложности времени для одного .
• Второй способ заключается в том, чтобы управлять и
как двумя указателями. Когда фиксирован,
максимальный , который является , уменьшается по
мере увеличения . Поэтому это свойство позволяет
решить задачу с общей временной сложностью для
одного .
• Используя описанный выше метод, мы получим решения и
соответственно. Оба бассейна пройдут.

24.

Div2E: Фейерверк
• Представлено: azberjibiou
• Количество решенных задач: 12

25.

Div2E: Фейерверк
• Тело
• Вам дана последовательность длины .
• Выбираем число, которое не является
двусторонним, удаляем его и вычитаем 1 из числа
по обе стороны от него раз.
• Уменьшите наибольшее из двух чисел, оставшихся
в конце, и выведите это значение.

26.

Div2E: Фейерверк
• Подзадача 1 (10 баллов)
• чтобы мы могли попробовать все возможные
варианты.
• Временная сложность составляет .

27.

Div2E: Фейерверк
• Подзадача 2 (32 балла)
• Здесь нам необходимо сделать важное замечание.
• Два числа, оставшиеся в конце, получены из
чисел, которые были в начале.
• Поэтому неважно, какое среднее число, важно,
сколько их по обе стороны.

28.

Div2E: Фейерверк
• Рассмотрим следующую ситуацию
[3 4 6 7 10]
• Каждый раз, когда мы удаляем число, мы вычитаем 1 из
числа, стоящего по обе стороны.
• Поскольку цель состоит в том, чтобы уменьшить
количество чисел с каждой стороны, всегда лучше
убрать второе число слева или второе число справа, а
не тратить ход на ненужное удаление числа в
середине.
• В данном случае , поэтому если мы продолжим удалять
только второе число справа, то число справа будет
больше, чем число слева. Это оптимально, и ответ - .

29.

Div2E: Фейерверк
• Подзадачи 1, 2 и 3 (100 баллов)
• Для
выполнения
этого
подзадания
отнимите
соответствующее число от обеих сторон.
• Пусть - это количество раз, когда 1 вычитается
из крайнего левого числа, а - количество раз,
когда 1 вычитается из крайнего правого числа.
не могут увеличиваться одновременно, за
исключением случая, когда число оборотов равно
3. Кроме того, для
оптимально, чтобы хотя бы
один из них увеличивался, так что . (так как
очередь - это очередь)

30.

Div2E: Фейерверк
• На самом деле эту проблему можно решить и с
помощью исключения ввода .
• Ответ: .
• Или, если это , вычтите из большего.
• то ответ заключается в том, чтобы сначала
сделать
большую
сторону
меньшей,
вычесть
разницу от до , а затем вычесть половину
деления. Выражение для этого выглядит так

31.

Div2F: Подготовка к войне
• Предоставлено: blackking26
• Количество решенных задач: 7

32.

Div2F: Подготовка к войне
• Та же проблема, что и в Div1F, только с меньшим
лимитом.
• См. подзадачу 3 в Div1F.

33.

Оглавление
• Отдел 2: Решения от A до F
• Отдел 1: Решения от A до F
• Решения G, H

34.

Div1A: Забыли пароль
• Автор: 79brue
• Количество решенных задач: 9

35.

Div1A: Забыли пароль
• Вам даны две струны , зубцы которых .
• Найдем количество различных общих подстрок
длиной .

36.

Div1A: Забыли пароль
• Подзадача 1 (9 баллов)
• Поэтому нам просто нужно найти число, которое
существует и в , и в .
• Сделать это можно разными способами, но самый
простой - проверить массивы и на наличие в
каждом из них чисел от 1 до 9 и подсчитать
количество проверок в обоих массивах.
• Временная сложность составляет .

37.

Div1A: Забыли пароль
• Подзадача 1, 3 (23 балла)
• Если мы применим этот подход как есть, то
получим решение из 23 пунктов.
• Поскольку все подстроки длины равны целому
числу или меньше, мы можем проверить их в
массиве и решить их так же, как и раньше.
• Временная сложность составляет .

38.

Div1A: Забыли пароль
• Подзадачи 1, 2 и 3 (37 баллов)
• и и извлечение из них подстрок длины и хранение
их в структуре данных типа unordered-set может
решить проблему с временной сложностью
порядка .

39.

Div1A: Забыли пароль
• Подзадачи 1, 2, 3, 4 (100 баллов)
• Чтобы получить 100 очков, нам нужен способ
быстро сохранить все строки и определить, равны
ли они.
• Если вы хэшируете и храните подстроку всех длин
, вы можете решить проблему либо для , либо для
, в зависимости от того, как вы ее хэшируете.
• Наиболее распространенным способом хеширования
строк является rolling hash, который хранит
строку как . и со скромными десятичными

40.

Div1A: Забыли пароль
• Если просто хэшировать их и сравнивать, можно
получить хэш-коллизии, когда разные строки
имеют одинаковое хэш-значение и думают, что они
одинаковые. Чтобы избежать этого, следует
хэшировать разные более одного раза, чтобы
увеличить шансы на то, что вы все сделаете
правильно.
• достаточно велик, то можно уместить все данные
в одном хэше, и некоторые участники так и
поступили.

41.

Div1A: Забыли пароль
• После завершения хэширования вам нужно подсчитать различные
числа, которые являются общими для обеих
последовательностей.
• Это также легко сделать с помощью unordered-set, но есть и
другой способ.
• Отсортируйте две последовательности и сократите количество
вхождений в каждый массив до одного. Это можно легко
сделать с помощью функций STL std::sort, std::unique.
• Теперь заведите по одному указателю в каждую из двух
последовательностей. Перемещайте указатель слева направо и
подсчитывайте количество вхождений в обе последовательности
так же, как и при сортировке муджа.

42.

Div1B: Игрушки из волшебного
камня
• Автор: 79brue
• Количество решенных задач: 1

43.

Div1B: Игрушки из волшебного
камня
• Тело
• У вас есть последовательность натуральных чисел
от 1 до 5.
• Мы можем запросить несколько значений и
несколько натуральных чисел от 1 до 5, чтобы
посмотреть, насколько они отличаются друг от
друга.
• Найдите все значения каждого элемента в с
помощью небольшого количества запросов.

44.

Div1B: Игрушки из волшебного
камня
• Подзадачи 1, 2 и 3 (20 баллов)
• Каждый элемент можно вычислить самостоятельно.
• Вы можете получить 10 баллов за определение
каждого элемента с помощью 5 запросов, 14
баллов за определение с помощью 4 запросов и 20
баллов за определение с помощью 3 запросов.
• Чтобы выяснить это с помощью трех запросов,
можно составить их вместе, например [[1][2]]
[[3][[4][5]]] а затем выполнить двоичный поиск,
чтобы выяснить, какой из них верен.

45.

Div1B: Игрушки из волшебного
камня
• Подзадача 4 (52 балла)
• Найдите число три в восьми запросах.
• при делении на 3 у нас может остаться 1 или 2
числа, в зависимости от остатка, которые нам
нужно найти в шагах 3/6 соответственно, что
можно решить так же, как и предыдущую
подзадачу.

46.

Div1B: Игрушки из волшебного
камня
• При задании пяти вышеуказанных запросов
результат будет один из [1, 2, 2, 2, 2, 2], [2,
2, 3, 3, 3, 4, 4], соответственно.

47.

Div1B: Игрушки из волшебного
камня
• Если диапазон [1, 2, 2, 2, 2, 2, 2]: - это все
одно и то же, и мы знаем, что это такое
(например, если дает 1, то ), поэтому нам не
нужно делать больше никаких запросов. Мы
использовали пять запросов.
• Если результат [2, 2, 3, 3, 3, 3]: только два
из одинаковы, и мы знаем, сколько типов
существует. (Например, если и равны 2, то либо
1, либо 2.) Таким образом, мы можем определить,
к какому типу относится каждый из них, с
помощью одного запроса, и решить эту проблему с
помощью еще трех запросов. В данном случае мы

48.

Div1B: Игрушки из волшебного
камня
• Если семейство имеет вид [3, 3, 3, 3, 4, 4, 4]:
все разные. Мы знаем, какие это числа, но не
знаем их порядка, поэтому определяем с помощью
двух запросов, - с помощью одного запроса, а
определяется автоматически. Количество
запросов, которые мы использовали, равно
восьми.
• Если сложить все вышеприведенные результаты
вместе, то число 3 можно найти по 8 запросам,
поэтому ответ можно найти по запросу .

49.

Div1B: Игрушки из волшебного
камня
• VTask 5 (100 очков)
• Чтобы решить эту подзадачу, вам понадобятся две
вещи
• Нахождение числа 3 в 7 запросах
• Найдите число два в пяти запросах

50.

Div1B: Игрушки из волшебного
камня
• При решении подзадачи "Линия" результат автоматически
определяется из предыдущих четырех результатов без
необходимости его запрашивать, поэтому число три можно
найти за семь запросов.
• Метод кандидата для нахождения числа два в пяти
задачах заключается в следующем
• и результат - .
•: .
• : , которые мы выясняем с помощью двух запросов
каждый.

51.

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

52.

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

53.

Div1C: Имитация камня света
• Предоставлено: 79brue / blackking26
• Количество решенных задач: 0

54.

Div1C: Имитация камня света
Тело
• Последовательность задана натуральным числом K.
• Каждому запросу дается и требуется найти
значение .

55.

Div1C: Имитация камня света
Подзадача 1
• Само собой разумеется, что никогда не может
быть оптимального решения, если
• Если попробовать наивно для всех в диапазоне,
то можно решить проблему за время .

56.

Div1C: Имитация камня света
Подзадача 2
• (Наша задача - найти минимальное значение ).
• Давайте сделаем это.
• Это должны быть , и минимум .
• Кроме того, если мы решили найти наибольшее
из , которое не меньше , то это должно быть .
• Это означает, что вам нужно проверить только ,
который является .

57.

Div1C: Имитация камня света
Подзадача 2
• встречается на удивление редко.
• 1. если есть разница в разделе , то она должна быть -> .
• 2. отличается от термина
-> находится на границе, где он меняется с
положительного на отрицательный / с отрицательного на
положительный
от положительного к отрицательному / от
отрицательного к положительному.
Другими словами, это должно быть .
• На сайте осталось всего .
• Если мы наивно переберем всех кандидатов, то сможем
решить задачу за время .

58.

Div1C: Имитация камня света
Подзадача 3
• Нужно ли мне написать на , чтобы получить его?
• Давайте рассчитаем
:
• : 0
• :
• По мере увеличения она становится , затем нулевой,
затем .
• Если мы используем биссектрису для поиска
изменяющейся границы и предварительно обработаем
префиксную и суффиксную суммы , мы сможем найти за
время и решить всю задачу за время .

59.

Div1C: Имитация камня света
Подзадача 3
• Нам нужно удалить еще одного.
• является выпуклым.
• является выпуклым.
• является выпуклым.
• является выпуклым.
• Теперь, если мы сделаем триангуляцию, мы сможем
решить проблему с временной сложностью .

60.

Div1C: Имитация камня света
Подзадача 4 (полное задание)
• Чтобы решить "Полное задание", вам нужно
оторвать бревна.
• Теперь давайте вычислим напрямую.
• если , если
счетчик , который является )
• Нас интересует точка, в которой меняет знак,
поэтому найдем , где разность между равна
(число , которое есть ), а - .

61.

Div1C: Имитация камня света
Подзадача 4 (полное задание)
• Не теряя общности, давайте оставим это на .
• Первоначально поместите левый указатель на , а
правый - на .
• Запросы поступают в порядке убывания .
• и переместите указатели влево и вправо на один
пробел, пока они не окажутся в точках
• Теперь, обращая внимание на ошибку off-by-one,
найдите точку, где меняет знак.
• Поскольку рот и запрос согласованы, временная
сложность составляет .

62.

Div1D: Раскопки остатков
колодца
• Автор: gunwookim
• Количество решенных задач: 4

63.

Div1D: Раскопки остатков
колодца
• Тело
• У вас есть граф с вершинами и ребрами.
• Пусть - это разница между количеством ребер,
входящих в вершину и вы одящих из нее, и
количеством ребер, входящих в вершину и
выходящих из нее.
• и найти способ свести его к минимуму.

64.

Div1D: Раскопки остатков
колодца
• Подзадача 1 (26 баллов)
• В качестве обобщения рассмотрим случай, когда
все вершины исходного графа имеют четную
степень.
• Это гарантирует, что эйлерова схема существует.
• Если ориентироваться по эйлеровой схеме, то
каждой вершины будет . Само собой разумеется,
что это оптимальное решение.

65.

Div1D: Раскопки остатков
колодца
• Подзадачи 1, 2 (100 баллов)
• Если существует любая точка нечетной степени, то ответ
будет не меньше 1, так как точка не может быть .
• Существует четное количество точек нечетной степени
(потому что сумма всех степеней равна , что является
четным).
• Если мы создадим новую магистраль, произвольно
соединив две нечетные точки, то получим граф со всеми
четными точками и сможем найти контур Эйлера.
• Применяя здесь метод из подзадачи 1, мы можем получить
ответ , который оказывается оптимальным решением.

66.

Div1D: Раскопки остатков
колодца
• Временная сложность зависит от времени
нахождения схемы Эйлера.
• Существует множество различных реализаций, но
вы можете устранить неполадки на сайте .

67.

Div1E: Круговой фейерверк
• Представлено: azberjibiou
• Количество решенных задач: 10

68.

Div1E: Круговой фейерверк
• Тело
• В круге размещены цифры .
• Мы собираемся удалить одно число и вычесть 1 из
двух чисел по обе стороны от него, раз.
• Давайте минимизируем большее из двух чисел,
оставшихся в конце операции, и выведем это
значение.

69.

Div1E: Круговой фейерверк
• Подзадача 1 (35 баллов)
• Наконец, давайте заморозим два оставшихся
номера и удалим все оставшиеся номера.
• От того, являются ли два числа соседними,
зависит способ их решения.
• Если результаты для каждой пары ветвей можно
найти на сайте , то ответ можно найти на
сайте .

70.

Div1E: Круговой фейерверк
• Пусть - это начальное значение обоих чисел, а значение, которое будет вычтено из в конце
операции.
• Если два числа соседствуют, .
• Если два числа не являются соседними, то .
• тогда ответ будет .
• тогда ответ будет .
• Многие объяснения пересекаются с объяснениями
Div2E, поэтому если вы не уверены в том, что
происходит, прочитайте решение Div2E.

71.

Div1E: Круговой фейерверк
• Подзадачи 1 и 2 (100 баллов)
• Вы не можете попробовать все для каждой пары.
• Вы можете попробовать все из них для смежных
пар и только кандидатов для несмежных пар.
• Каждый кандидат фиксирует число и использует
наименьшее из оставшихся чисел, исключая .
• Реализация может быть непростой задачей, и есть
много способов облегчить ее.
• Временная сложность для этого - .

72.

Див1Ф: Война в мире
• Предоставлено: blackking26
• Количество решенных задач: 0

73.

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

74.

Див1Ф: Война в мире
• Подзадача 1 (6 баллов)
• это.
• Ответ должен выглядеть как , поэтому попробуйте
все , чтобы решить задачу.
• Временная сложность составляет .

75.

Див1Ф: Война в мире
• Подзадача 2 (5 баллов)
• Вычислите GCD элементов, перебирая каждое
подмножество по очереди.
• Временная сложность составляет , но фактический
эффект невелик, поскольку член появляется с
помощью евклидовой арифметики, поэтому он
стабильно ведет себя во времени.

76.

Див1Ф: Война в мире
• Подзадача 3 (29 баллов)
• Ответ всегда должен быть .
• Когда, имеет максимальное количество
сокращений - 1344.
• Теперь, если мы проверим всех кандидатов, это
займет около операций и уложится в срок.

77.

Див1Ф: Война в мире
• Подзадача 4 (62 балла)
• Теперь вы не можете попробовать все
приближения.
• число простых факторов , то самый слабый фактор
может быть представлен точкой в пространстве
размерности .
• Точнее, если вы скажете , то каждый будет
представлен как .
• Представляя дробь в виде -вектора, мы можем
представить ее в -мерном координатном
пространстве, где становится .

78.

Див1Ф: Война в мире
• Подсчет количества кратных в наборе для
приближенного числа превращается в задачу
нахождения префиксной суммы размерности .
• на плоскости размерности , а затем найти
префиксную сумму.
• Используя принцип включения-исключения, задачу
можно решить за (количество приближений)
операций.

79.

Див1Ф: Война в мире
• Подзадача 5 (100 баллов)
• Вместо принципа включения-исключения для получения
префиксной суммы можно использовать стратегию
развертки по размерности (BOJ 18830; см. также
Гиперпоследовательности и Гиперзапросы).
• В этом случае нам нужно (количество приближений) .
• В подзадании 5 вам также нужно будет позаботиться о
факторизации .
• Результаты, аналогичные простой факторизации ПоллардаРо, можно получить с помощью алгоритма простой
факторизации Полларда-Ро или с помощью пар gcd из .

80.

Оглавление
• Отдел 2: Решения от A до F
• Отдел 1: Решения от A до F
• Решения G, H

81.

G: Logic Stone
• Автор: 79brue
• Количество решенных задач: 2

82.

G: Logic Stone
• Тело
• Вы хотите отсортировать двоичную
последовательность, которая является
• Операция, которая может быть выполнена, имеет
вид , что означает, что значение AND битов и
подставляется в бит .
• Или, если , он вычисляется с инвертированным
битом (NOT).
• затем поместите инвертированный (NOT) бит
вычисленного значения в бит .

83.

G: Logic Stone
• Для вычислений доступно дополнительных битов.
• Дополнительные биты изначально не имеют
значения и должны быть использованы после
инициализации.
• Количество операций , количество использованных
дополнительных битов и количество
использованных дополнительных битов оценивается
следующим образом.

84.

G: Logic Stone
• Решение 1 (28,41 балла)
• Рассмотрите сорта пузырьков.
• Поменять местами оба бита нужно только в том
случае, если бит слева равен 1, а бит справа 0.
• Для удобства назовем эти два бита ( находится
дальше слева).

85.

G: Logic Stone
• на , и на .
• Для дополнительного бита установите значение .
• Это эквивалентно .
• тогда - это то же самое, что и исходный .
• Сделайте это , и сортировка будет завершена.
• Если бы это было реализовано, то результат
составил бы 28,41 балла.

86.

G: Logic Stone
• Решение 2 (около 77 баллов)
• Использование дополнительных бит должно быть
максимально сокращено.
• Сначала мы сохраняем значение бита 16 в
дополнительный бит, бит 17.
• Бит 16 используется как дополнительный бит для
выравнивания битов с 1 по 15.
• Наконец, если вы положите бит 17 на бит 16 и
засунете его в пузырьки, то получите около 77
очков.

87.

G: Logic Stone
• Решение 3 (около 96 баллов)
• Основное решение такое же, как и раньше.
• При пузырьковой сортировке бит 16 на последнем
шаге, перемещение бита 1 в бит 17 и
использование бита 1 в качестве дополнительного
бита для подсчета сортировок может значительно
сократить .
• Оценка, которую вы получаете, составляет около
96 баллов.

88.

G: Logic Stone
• Решение 4 (исправлено, 100 баллов)
• Юнг использует очень хитрый способ подсчета.
• Решение можно разбить на пять шагов.

89.

G: Logic Stone
• Шаг 1. Подсчитайте количество 1
• Подсчитайте количество 1, начиная с бита 16 и
двигаясь влево.
• Количество единиц хранится в битах с 12 по 16.
• Бит 12 - это бит из , который будет иметь
значение 1 тогда и только тогда, когда все
числа равны 1. Биты 13, 14, 15 и 16, в свою
очередь, являются битами из .

90.

G: Logic Stone
• Шаг 2. Заполните биты с 1 по 8
• Теперь, когда мы подсчитали количество 1,
давайте заполним 0 слева.
• Воспользуемся свойством, что (количество нулей)
+ (количество единиц) = .
• Мы использовали биты с 12 по 16 в качестве
счетчика количества 1, и теперь каждый раз,
когда мы добавляем 0 слева, мы добавляем 1 в
счетчик. По значению бита 12 мы можем
определить, что счетчик равен ровно 16, что
экономит много запросов.

91.

G: Logic Stone
• Шаг 3. Уменьшите счетчик тактов и заполните такты 9 и 10
• В настоящее время счетчик занимает пять битов.
• Число в счетчике находится в диапазоне от 8 до 16,
поэтому если мы вычтем из него 8, то сможем создать бит
12.
• Вычитание 8 выполняется простой заменой бита 13 на бит
12.
• Затем мы можем заполнить биты 9 и 10 таким же образом,
как и раньше. Поскольку в процессе добавления 1 к
счетчику нам нужны два временных бита, без
дополнительных битов мы можем заполнить только бит 10.

92.

G: Logic Stone
• Шаг 4. Замените форму счетчика и заполните биты 11 и 12
• Сортировка традиционным способом больше невозможна.
• Когда мы вычитаем 1 из счетчика, значение счетчика
находится между 1 и 7, поэтому мы используем только 3
бита, оставляя свободным бит 13.
• Биты 11 и 12 теперь определяются как противоположные
биты значения, полученного при объединении битов с 14
по 16. Как и раньше, каждый раз, когда мы добавляем
ноль слева, мы добавляем единицу в счетчик. Процесс
выравнивания бита 12 неизбежно будет использовать
дополнительный бит несколько раз.

93.

G: Logic Stone
• Шаг 5. Заполните биты с 13 по 16
• Биты 14-16 соответствуют одной из следующих ситуаций
• 111 / 110 / 101 / 100 / 011
• Мы можем выровнять биты с 13 по 16 с помощью 7
дополнительных безбитовых операций и 3
дополнительных битовых операций. Этот процесс может
быть получен с помощью casework.
• Вы можете воспользоваться сайтом , чтобы получить
отличную оценку.

94.

G: Logic Stone
• Один участник, получивший отличный результат,
использовал сортировку блинов.
• Кроме того, оказывается, что можно значительно
уменьшить с 375.
• Поскольку мы стремились решить задачу, которая
позволила бы человеку набрать 100 баллов за
время соревнования, решение было найдено менее
чем за три часа.

95.

H: Обрезка дерева
• Представлено: azberjibiou
• Количество решенных задач: 10

96.

H: Обрезка дерева
• Тело
• Вам дано дерево с N вершинами.
• Если , , соединены с , , для любой другой
вершины в одном прогоне, инвертируйте
магистраль между .
• Это означает отключение , и и подключение , и .
• Покажите, как сделать диаметр дерева меньше или
равным 4 за 1000 испытаний.

97.

H: Обрезка дерева
• Подзадача 1 (4 балла)
• Единственный случай, когда диаметр дерева
больше 4, - это если оно представляет собой
прямую линию, как показано ниже.

98.

H: Обрезка дерева
• Если вы выполните команду "1 2 3 4", диаметр
дерева будет равен 4, как показано ниже.

99.

H: Обрезка дерева
• Подзадачи 1, 2, 3, 4 (100 баллов)
• Прежде всего, необходимо сделать одно замечание
по поводу правоприменения.
• Если мы разъединим , и соединим , и , то
увеличим степень на единицу.
• Давайте захватим вершину и будем делать это до
тех пор, пока не перестанем выполнять .
• Количество стволов во всем дереве равно ,
поэтому вершина 1 имеет степень не более и может
быть выполнена не более раз.

100.

H: Обрезка дерева
(