С 20 октября по 10 января проходит заочный тур V Открытой олимпиады школьников по программированию. Предлагаю здесь после окончания олимпиады вести обсуждение контеста
Официальный сайт олимпиады: http://olympiads.ru/zaoch/
UPD: Соревнование окончено, можно обсуждать задачи
Официальный сайт олимпиады: http://olympiads.ru/zaoch/
UPD: Соревнование окончено, можно обсуждать задачи
Сам виноват, конечно, но лучше бы в будущем итоги большого соревнования не определялись результатами решения одной задачи.
Когда из 100 задач одна команда решает 70, а другая 69, причем и состав решенных задач различается, это нормально.
А когда из 8-ми задач лидеры достаточно легко решают по 7, а разница только в количестве баллов по 8-й задаче, то это, по-моему, не есть хорошо.
Zennon из-за того что не дописал красивую заглушку.
Но к самому содержанию контеста замечание высказать можно. С надеждой, что в этом году, например, не будет такого рапределения задач по сложности.
Отличная идея, хотя не терпится начать прямо сейчас
Вот к примеру странно, что на данный момент уже второй день проверяются видимо все посланные вчера вечером решение (мое по крайней мере как раз с того момента там и лежит). Остается надеяться скорой проверки и ждать вердикта.
Тем кто поздно начал, есть дополнительное время :)
Профиль - это последний столбец. Каждый элемент - либо нолик, либо номер компоненты связности. Т.к. высота небольшая и у каждой компоненты ровно два "выхода", плюс еще их можно перенумеровать без пропусков и по увеличению, получаем ~1000 профилей.
Далее считаем переходы. Переход - это на текущем столбце 2h способами расставить черточки. Они должны замыкать какие-то компоненты между собой. Могут появится новые. Главное - чтобы все старые не пропали (могут пропасть только все разом).
А потом динамика: профиль, текущий столбец, начинали ли уже фигурку (чтобы не получилось несколько связных фигур).
Тестировать можно тупым решением и визуализатором, а также заменой w на h на маленьких тестах (например, 6 7 и 7 6).
Вот.
class dss - СНМ
map<vi, int> ids - номера профилей
void repaint() - перекрашивает профиль так, чтобы не было неиспользуемых цветов и чтобы они шли по порядку
Вначале заполнял все W.
Пока не нашел ответ смотрел можно ли где-нибудь улучшить позицию на столбце или в строке. Если можно улучшал.
Онлайн группу прошло, не знаю как с оффлайн
Достроим граф до эйлерова путем соединения пар нечетных вершин (любым способом). Найдем эйлеров цикл. Покрасим эйлеров цикл путем чередования черного и белого цвета. Удалим добавленые ребра и очевидно что получится требуермая раскраска.
А всегда ли возможно по столбцам и строкам таблицы, и чтобы ещё и рёбра соответствовали местам студентов построить двудольный граф?
И почему по Вашему алгоритму получиться требуемая раскраска. Как это можно обосновать? Спасибо.
Лично мне больше понравилась задача F, хотя она до ужаса элементарная. Я знаю одну игру, которая мне в принципе и помогла ее решить.
Игра "Кант" (не от немецкого философа, а от слова "кантовать")
Для игры требуются:
Изначально на первой линии стоят кубики 1-ого игрока, на четвертой--кубики 2-ого игрока (в дальнейшем эти линии будут называться линиями 1-ого/2-ого игрока). Все кубики стоят ноликами вверх.
Одним ходом можно перекатить кубик на соседнюю клетку (как и в задаче). Игроки ходят по очереди.
Если какой-то из игроков (пусть первый) поставил один свой кубик ноликом вверх на линию соперника (в данном случае 2-ого), то последний должен за минимальное число ходов убрать все свои кубики со своей линии (если такой возможности вообще нет, то он имеет право ходить как ему вздумается) и в дальнейшем не имеет права перекатить их обратно.
Если какой-то из игроков поставил 2 своих кубика ноликом вверх на линию соперника, то последний должен за минимальное число ходов убрать все свои кубики со своих первых двух линийи в дальнейшем не имеет права перекатить их обратно.
Если какой-то из игроков (пусть первый) поставил 3 своих кубика ноликом вверх на линию соперника, то последний должен за минимальное число ходов "освободить" последний кубик первого игрока если у того было ограниченное поле для ходов этим кубиком.
Выигрывает тот, кто первым поставит все сваои кубики ноликом вверх на линию соперника или тот, чей соперник не сможет сходить.
Примечание 2-ому игроку. Желательно не ходить зеркально, чтобы игра была более менее интересной.
Согласитесь, умение играть в нее поможет при решении подобной задачи.
Двухмерное дерево отрезков. Отрезок - это точка (начало, конец). Отрезок вложен, если он лежит правее (начало больше) и ниже (конец меньше). Проверяем просто: запрос на прямоугольнике. Должно быть ровно две точки.
Для упрощения запросов можно было еще реверснуть координату X (начало).
Можно написать в пару раз короче.
Пусть лучше еще кто-нибудь выложит :)
Это решение его с успехом получает :)
Здесь http://codeforces.me/blog/entry/963 эта задача была засвечена :)
Думаю, следует обратить внимание на этот комментарий http://codeforces.me/blog/entry/963#comment-16189
Кажется догадываюсь, почему упала E. Извини если мои сомнения по твоему коду ложны, но там нужно было работать длинкой. Там же при самых больших тестах 2^1000 яблок, не меньше.
Интересно, собирается ли жюри что-нибудь делать с тестами по этим задачам..
По ходу все квадратичные решения L перепроверяются. Возможно с K та же история
интересно I ещё не проверили или провели и ни у кого нет полного решения?
Он очень медленно работает.