Тренировка #11 [Меньшиков]

[Условия задач]                   [Список тренировок]

11A. Последовательность
[seq]
Довольно любопытная задача на выявление закономерности в последовательностях. Первый раз всплывает принцип Дирихле.
11B. Провода
[cable]
Классический пример задач на “Бинарный поиск по ответу”. Эта тема хорошо описана в 3 лекции курса Михаила Густокашина
11C. Палиндромы
[palindr]
Двумерное ДП. Один из тех удачных примеров, доказывающий, что ДП много не бывает. Придется немножко подумать.

Тренировка #10 [Меньшиков]

[Условия задач]                    [Список тренировок]

10A. Анти-QuickSort
[antiqs]
Нетипичная задача, требующая глубокого понимания работы быстрой сортировки.
10B. Строки Фибоначчи
[fibostr]
Классная задача на ДП. В наличием определенного опыта в решении подобных задач не представляет больших сложностей. Но есть ряд нюасов, которые нужно учесть.
10C. Игра в зачеркивание
Задача, которая не давала спокойно жить 2 дня. На нее было получено 4 решения, а все описание изложено в отдельном посте
[crossgam] TLE
[crossgam] ДП с запоминанием + vector   [0.105 с.]
[crossgam] ДП с запоминанием + multiset [0.322 с.]
[crossgam] на основе функции Grundy
10D. Граница многоугольника
[border]
Задача скорее на знания, чем на умения. Используем тот факт, что у прямоугольного треугольника количество точек с целочисленными координатами на гипотенузе равно НОД’у(Наибольшему общему делителю) катетов + 1. Представив каждую сторону за гипотенузу, обходим все стороны и получаем результат.
10E. Путь спелеолога
[speleo]
Задача на пространственное воображение и на трехмерный BFS. Особых сложностей быть не должно. Главное не забыть что здесь будет 6 измерений, в отличии от двумерного случая.
10F. Дырявая ткань
[holey]
Предложенное решение сделано полностью по авторскому разбору. Стоит обратить внимание на “приемчик”, как избежать TLE на максимальном тесте.


[Все решения]

10С–Игра в зачеркивание [Меньшиков]

[Тренировка 10]                      [Список тренировок]

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

Итак мое первое решение было довольно тривиальным. Основывалось оно на опыте предыдущих задач. Суть заключалось в следующем:

1) Каждое состояние кодировалось числом. (X – единичка, O - нолик). В итоге получается 40 битное число, поэтому оно хранилось в типе long long.
2) Строилась матрица смежности, т.е. матрица переходов. Для каждого числа хранился список чисел, в которые можно попасть из текущего состояния.
3) Также отдельно хранился список всех возможных состояний(чисел) в игре.
4) После чего сортируем массив из п. 3) в порядке возрастания и начинаем его заполнять с конца.
5) Ответ будет находится в первом элементе массива из п. 3)

Чтож – неплохой план! Кодируем. Получаем нечто похожее на это. Каков же вердикт? На 9-и тестах из 31 получаем TLE.

И только после этого я начал ДУМАТЬ!

Тренировка #9 [Меньшиков]

[Условия задач]                   [Список тренировок]

9A. Диалог компьютеров
[dialogue]
Первая задача на моделирование процесса. Большое, немного непонятное условие(на первый взгляд), поэтому советую его читать несколько раз. Тщательно продумываем структуры данных перед тем, как начинать писать.
9B. Бросание кубика
[die]
Первая задача на теорию вероятностей. Для начала вспомним правило сложение вероятностей, и когда его нужно применять. Здесь изложена суть. Понятно, что если с двух бросков шестигранного кубика было набрано 8 очков, то это могло случиться, если выпала одна из комбинаций: 2-6, 3-5, 4-4, 5-3, 6-2. Находим вероятность каждой из этой комбинации и плюсуем в итоговую.

Алгоритм быстрой оболочки (Quick hull)

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

Вся представленная реализация основана на описании с wikipedia. Оттуда же можно узнать смысл таинственных переменных S1 и подобных. В качестве “подопытной задачи” была выбрана все та же 5D. Выпуклая оболочка из сборника задач Меньшикова.

Итак пошагово рассмотрим алгоритм.
На начальном этапе мы имеем множество точек на плоскости