V Открытая олимпиада школьников по программированию(заочный тур)

14 лет назад, # ^ |

Можно было посмотреть здесь

→ Ответить

14 лет назад, # |

Да логичнее было написать, когда она начиналась либо когда уже кончится)

ну что можно сказать: проблемсет довольно интересный)

Странно, что Gennady Korotkevich еще не все решил, а оставил довольно легкую задачу)

→ Ответить

GlebsHP

14 лет назад, # ^ |

В прошлом году это была вроде бы единственная школьная олимпиада которую Гена не смог выиграть (имею ввиду очный тур).

→ Ответить

14 лет назад, # ^ |

Сказал один из двух обогнавших Гену людей :)

→ Ответить

k-va	14 лет назад, # ^ \| 0 Гену в прошлом году от победы отделяла пара неверных байтов. Сам виноват, конечно, но лучше бы в будущем итоги большого соревнования не определялись результатами решения одной задачи. → Ответить

14 лет назад, # ^ |

Петрозаводские сборы не раз отделяли победителя от второго места одной задачей

→ Ответить

k-va

14 лет назад, # ^ |

Здесь другая ситуация.
Когда из 100 задач одна команда решает 70, а другая 69, причем и состав решенных задач различается, это нормально.
А когда из 8-ми задач лидеры достаточно легко решают по 7, а разница только в количестве баллов по 8-й задаче, то это, по-моему, не есть хорошо.

→ Ответить

14 лет назад, # ^ |

-15

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

Zennon из-за того что не дописал красивую заглушку.

→ Ответить

k-va	14 лет назад, # ^ \| 0 И какое отношение эти факты из Вашей биографии имеют к обсуждаемому вопросу? → Ответить

14 лет назад, # ^ |

-15

Ну, проиграл, обидно:) Ну и что? Каждая система по-своему несправедлива. Справедлив ли ACM формат? Справедливее, чем школьная система, но несправедлив, и если ориентироваться на промышленное программирование, то даже и неправильный(потому что в промышленном программировании не обязательно, чтобы программа работала всегда-ее потом улучшат-а важно чтобы она была как можно быстрее написана и отдана заказчику, а потом ее уже дорабатывают)

→ Ответить

14 лет назад, # ^ |

-10

Справедлива ли система подсчета ИТМО? В основном-да, но в некоторых моментах-нет. Справедлив ли КФ или ТС? Опять же, не совсем, можете сами привести примеры.

→ Ответить

k-va

14 лет назад, # ^ |

Да я вообще не пытался как-то оправдать Генино не 1-е место, если это вообще надо оправдывать -). Все было совершенно справедливо.
Но к самому содержанию контеста замечание высказать можно. С надеждой, что в этом году, например, не будет такого рапределения задач по сложности.

→ Ответить

14 лет назад, # ^ |

А, вот вы о чем:) Да, я сам сталкивался с проблемой плохого распределения задач по уровню сложности на контесте(что уж говорить про вашего сына, который-сколько уже в спортивном программировании?), когда 10 задач из 11 уровня А+В, а 11-какая-нибудь задачка , ну не знаю, потоки на масочке с геометрией, где еще значение EPS приходится подбирать. В результате кто быстрее печатает-тот и выиграл:)

→ Ответить

14 лет назад, # |

Отличная идея, хотя не терпится начать прямо сейчас

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

→ Ответить

14 лет назад, # ^ |

оживает!!!

→ Ответить

ZumZoom

14 лет назад, # ^ |

Ура!)

→ Ответить

Dmitry_Egorov

14 лет назад, # |

А я-то думал, что организаторы решили приучить людей не дотягивать до последнего))).

→ Ответить

GlebsHP

14 лет назад, # ^ |

Этим организаторы точно не занимаются, уже стало доброй традицией продление заочного тура с 10 до 15 января. Вроде еще не было ни одного года, чтобы это не случилось.

→ Ответить

14 лет назад, # |

Кто-нибудь знает сколько человек будет приглашено на очный тур?

→ Ответить

14 лет назад, # ^ |

посмотри прошлые года...

→ Ответить

qwaker.00

14 лет назад, # ^ |

Много, но от этого начинать стараться меньше не стоит ;)

→ Ответить

ZumZoom

14 лет назад, # |

8 января. Оргкомитет Открытой олимпиады по программированию принял решение продлить заочный тур до 15 января. Тур закончится 15 января в 23.59 по московскому времени.

Тем кто поздно начал, есть дополнительное время :)

→ Ответить

14 лет назад, # ^ |

вот блин)

→ Ответить

14 лет назад, # |

Как решалась задача J?

→ Ответить

14 лет назад, # ^ |

Идею решения можешь найти на хабаре в алгоритмах

→ Ответить

14 лет назад, # ^ |

Можно ссылку

→ Ответить

14 лет назад, # ^ |

http://habrahabr.ru/blogs/algorithm/105705/

→ Ответить

14 лет назад, # ^ |

Спасибо

→ Ответить

14 лет назад, # |

Расскажите кто-нибудь задачу про Васю, если не сложно:)

→ Ответить

14 лет назад, # ^ |

Динамика по профилю.
Профиль - это последний столбец. Каждый элемент - либо нолик, либо номер компоненты связности. Т.к. высота небольшая и у каждой компоненты ровно два "выхода", плюс еще их можно перенумеровать без пропусков и по увеличению, получаем ~1000 профилей.
Далее считаем переходы. Переход - это на текущем столбце 2^h способами расставить черточки. Они должны замыкать какие-то компоненты между собой. Могут появится новые. Главное - чтобы все старые не пропали (могут пропасть только все разом).
А потом динамика: профиль, текущий столбец, начинали ли уже фигурку (чтобы не получилось несколько связных фигур).
Тестировать можно тупым решением и визуализатором, а также заменой w на h на маленьких тестах (например, 6 7 и 7 6).

→ Ответить

14 лет назад, # ^ |

Спасибо, думал о динамике по профилю и понимал, что вроде бы на нее, не зря же одна координата 8, но до конца довести не получилось идею, да и это - не факт что реализовал бы.

→ Ответить

vilcheuski

14 лет назад, # ^ |

Дайте пожалуйста глянуть на Ваш код задачи про Васю. Спасибо.

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

http://pastebin.com/v9pE4Pmf
Вот.
class dss - СНМ
map<vi, int> ids - номера профилей
void repaint() - перекрашивает профиль так, чтобы не было неиспользуемых цветов и чтобы они шли по порядку

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

→ Ответить

14 лет назад, # |

Расскажите задачу G, пожалуйста (раскраска студентов).

→ Ответить

14 лет назад, # ^ |

я искал циклы четной длины меняя направления - строка -столбец. При четной длине красим все вершины, при нечетной - все кроме первой... Далее красим дерево

→ Ответить

14 лет назад, # ^ |

-13

Я делал так:
Вначале заполнял все W.
Пока не нашел ответ смотрел можно ли где-нибудь улучшить позицию на столбце или в строке. Если можно улучшал.
Онлайн группу прошло, не знаю как с оффлайн

→ Ответить

J0r1k

14 лет назад, # ^ |

Ты написал идею решения,как будто сам её придумал!

→ Ответить

14 лет назад, # ^ |

Я решал похожую таску на spoj

→ Ответить

14 лет назад, # ^ |

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

Получим либо цикл, тогда в каждой горизонтали/вертикали будет поровну тех и других, либо некий путь, тогда мы "испортили четность" в двух местах.

Заметив это будем начинать ходить из тех столбиков/строчек, где нечетно было сначала, если таковые имеются, иначе пофиг и все равно получим цикл

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

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

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

→ Ответить

CherryTree

14 лет назад, # ^ |

Разве уже известны результаты оффлайн-тестов?

→ Ответить

14 лет назад, # ^ |

fixed

→ Ответить

MBabin

14 лет назад, # |

← Rev. 2 →

Построим двудольный граф - столбцы первая доля, строчки вторая доля, ребра соответствуют местам студентов. Нужно раскрасить ребра в 2 цвета так чтобы у каждой вершины разность числа черных ребер и белых была <= 1.
Достроим граф до эйлерова путем соединения пар нечетных вершин (любым способом). Найдем эйлеров цикл. Покрасим эйлеров цикл путем чередования черного и белого цвета. Удалим добавленые ребра и очевидно что получится требуермая раскраска.

→ Ответить

ZumZoom

14 лет назад, # ^ |

Лучшее решение.

→ Ответить

MBabin

14 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

vilcheuski

14 лет назад, # ^ |

А всегда ли возможно по столбцам и строкам таблицы, и чтобы ещё и рёбра соответствовали местам студентов построить двудольный граф?

И почему по Вашему алгоритму получиться требуемая раскраска. Как это можно обосновать? Спасибо.

→ Ответить

d_i	14 лет назад, # \| 0 )Кто нибудь скажи плз, из опыта прошлых лет, когда примерно всё должны проверить?) → Ответить

14 лет назад, # |

← Rev. 3 →

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

Игра "Кант" (не от немецкого философа, а от слова "кантовать")

Для игры требуются:

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

На одной из граней нарисован нолик. Это единственная грань, использующаяся в игре

На грани, противоположной нолику нарисован крестик.

На оставшихся 4-х гранях нарисованы стрелки, указывающие на грань с ноликом. Это и есть их предназначение.

2. Доска 4*4

Изначально на первой линии стоят кубики 1-ого игрока, на четвертой--кубики 2-ого игрока (в дальнейшем эти линии будут называться линиями 1-ого/2-ого игрока). Все кубики стоят ноликами вверх.

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

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

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

Если какой-то из игроков (пусть первый) поставил 3 своих кубика ноликом вверх на линию соперника, то последний должен за минимальное число ходов "освободить" последний кубик первого игрока если у того было ограниченное поле для ходов этим кубиком.

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

Примечание 2-ому игроку. Желательно не ходить зеркально, чтобы игра была более менее интересной.

Согласитесь, умение играть в нее поможет при решении подобной задачи.

→ Ответить

14 лет назад, # ^ |

Возвращаясь к теме Короткевича. Очень странно, что эта задача выполнена у него всего на 88... Странно, странно...

→ Ответить

14 лет назад, # |

← Rev. 2 →

Еще расскажите, пожалуйста, нормальное решение последней задачи(отрезки на прямой возвращаются-2)

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

d_i	14 лет назад, # ^ \| 0 Егор, выложи пожалуйста исходник этой задачи, если не трудно где нибудь? → Ответить

14 лет назад, # ^ |

http://pastebin.com/pm9a3Zzr
Можно написать в пару раз короче.
Пусть лучше еще кто-нибудь выложит :)

→ Ответить

14 лет назад, # ^ |

Ну и понятно - я забыл потестировать на ML.
Это решение его с успехом получает :)

→ Ответить

14 лет назад, # ^ |

← Rev. 3 →

у меня за квадрат решение по L получило 100

и у многих так

похоже на бред составителей

или задача на тонкое оценивание ассимптотики )))

→ Ответить

14 лет назад, # ^ |

и по К соответственно тоже за квадрат в основном проходит

а у меня было быстрое решение

обидно:(

→ Ответить

14 лет назад, # ^ |

У меня слегка проще по-моему. Упорядочиваем номера отрезков по началу, а при равенстве - по большему концу. Таким образом все отрезки в которые может попасть K-й распологаютя до него. Далее сжимаем координаты концов (начала нам больше не нужны). И при обработке отрезка будем класть в его конец номер по-порядку обработки (в любую структуру типа максимизатора и тд...) Для K ищем максимум от конца отрезка до максимальной границы. И от полученного номера имеем ответ. Для L от конца отрезка до данного ответа. Если максимум соответствует ответу - ок. При получения в качестве максимума 0 смотрим жюри.

→ Ответить

Vasya.V

14 лет назад, # ^ |

Здесь http://codeforces.net/blog/entry/963 эта задача была засвечена :)

Думаю, следует обратить внимание на этот комментарий http://codeforces.net/blog/entry/963#comment-16189

→ Ответить

ostroumov

14 лет назад, # |

Офлайн-проверка началась. Всем удачи!

→ Ответить

14 лет назад, # |

← Rev. 2 →

Блин E непонятно почему упала:(

UPD: Кто-нибудь в курсе, они потом сорсы и тесты дают?

→ Ответить

14 лет назад, # ^ |

Ну у прошлой олимпиады было: 1 и 2

→ Ответить

14 лет назад, # ^ |

Кажется догадываюсь, почему упала E. Извини если мои сомнения по твоему коду ложны, но там нужно было работать длинкой. Там же при самых больших тестах 2^1000 яблок, не меньше.

→ Ответить

14 лет назад, # ^ |

длинка была написана)

ошибся, вместо %=

написал

как итог, когда вылезла за 10в4(основание длинки) вылез треш. на первых тестах не вылезло. как итог -40

→ Ответить

14 лет назад, # |

Прошло квадратичное решение по L, у знакомого по K тоже квадратичное прошло..

Странно

→ Ответить

CherryTree

14 лет назад, # ^ |

Печально
Интересно, собирается ли жюри что-нибудь делать с тестами по этим задачам..

→ Ответить

ostroumov

14 лет назад, # ^ |

Да, как-то нечестно даже получается...

→ Ответить

ostroumov

14 лет назад, # ^ |

А у меня L за квадрат не прошла.

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

Квадратные решения дико затянули время тестирования K и L

→ Ответить

14 лет назад, # ^ |

по I тоже не слишком быстро тестирование идет

→ Ответить

14 лет назад, # ^ |

По ходу все квадратичные решения L перепроверяются. Возможно с K та же история

→ Ответить

14 лет назад, # ^ |

Идет перетест всех решений по L... Некоторые падают

→ Ответить

14 лет назад, # ^ |

кажется К не собираются перезапускать, мое L как раз тоже упало..(100->80)

Кстати, кое у кого и 60->80 есть

→ Ответить

14 лет назад, # ^ |

Пошла перепроверка К

→ Ответить

antonkov

14 лет назад, # |

интересно I ещё не проверили или провели и ни у кого нет полного решения?

→ Ответить

14 лет назад, # ^ |

Не проверили

→ Ответить

14 лет назад, # |

Поздравляю победителей, пусть и промежуточных!

Проверка завершена.

→ Ответить

14 лет назад, # |

у кого-нибудь из здесь присутствующих есть ТЛ по I?

у меня 80, 2 последних теста ТЛ, да и другие последние тоже на грани

как такое может быть? О_о

→ Ответить

14 лет назад, # ^ |

Думаю, что это cin.
Он очень медленно работает.

→ Ответить

14 лет назад, # ^ |

По-моему пора вводить политику коротких входных файлов. Чтоб за время TL можно было считать данные любым способом. Вот на CF, последнее время, так и есть.

→ Ответить

14 лет назад, # ^ |

А еще можно как на TC - параметры

→ Ответить

14 лет назад, # ^ |

Ага, а еще как на TC - 4 языка программирования.

→ Ответить

14 лет назад, # ^ |

Я думаю, что многие(в том числе-один из лидеров, о ком же я?) будет против, если уберут паскаль(хотя этот лидер достаточно хорошо сдает задачки на С++, что подтверждает его 5 позиция на ТС)

→ Ответить

14 лет назад, # ^ |

Я думаю лидерам (и не только Этому Самому) не проблема писать на другом языке. Разве что узнать стандартные средства языков - время.

А так-то важнее иметь умение придумать алгоритм.

→ Ответить

14 лет назад, # ^ |

Тому Кого Нельзя Называть? :))

→ Ответить

14 лет назад, # ^ |

Он Самый:)

→ Ответить

14 лет назад, # ^ |

Ну я имел в виду чуть более широкую позицию: здесь найдутся люди и за ruby и за python. Просто позиция наиболее свободного выбора компилятора на этом сайте для многих - ключевая. Очень хочется ее сохранить.

→ Ответить

14 лет назад, # ^ |

А в чем проблема в этих языках передавать в виде параметров?

Вроде и у Паскаля есть диалекты с ООП

→ Ответить

14 лет назад, # ^ |

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

Честно говоря я думал, что основная мысль моего комментария: "дело ведь не только в паскале".

→ Ответить

14 лет назад, # ^ |

Ну и в руби и в питоне и в php судя по результатам гугла ооп поддерживается)

Впрочем, небольшие входные данные - я думаю более хороший вариант решения данной проблемы

→ Ответить

14 лет назад, # ^ |

В хаскеле не поддерживается.

→ Ответить

14 лет назад, # ^ |

ОК

→ Ответить

Dmitry_Egorov

14 лет назад, # ^ |

Где тут проблема? Пишите scanf, а не cin, это одна из особенностей языка. Ругаться на нее столь же глупо, как и например на то, что в паскале нет STL. А большие входные данные во многих задачах нужны, например, чтобы дерево отрезков нельзя было заменить корневой оптимизацией.

→ Ответить

14 лет назад, # ^ |

scanf долго писать - лень))

просто надо сделать себе еще одну пометку в мозгу - перед считыванием думать, как считать :)

→ Ответить