Добро пожаловать на 2013-2014 CT S01E06: 2002-2003 ACM-ICPC Northwestern European Regional Contest (NWERC 2002) + Some Problems from COCI and POI. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.
Удачи!
Условия в одной pdf http://contest.bsuir.by/problems/2013-2014_CT_S01E06_Codeforces_Trainings_Season_1_Episode_6.pdf
Спасибо, заменил этим файлом условия в контесте.
А откуда взялись тесты к задачам? А то я скачал тест по задаче Е вроде с официального сайта и на нем решения летают. Видимо тесты кто-то перегенивал?
Why my solution for A giving wa ? http://ideone.com/UbCRwy
good solution, but check test: 1 1 95 96 97 98 99
Why the solutions aren't public ?
No public solutions in the gym until you solve the problem.
Why not include it in the announcement. This question is asked every time.
Тренировки не влияют на рейтинг?
Не влияют.
Как решать K?
Какие идеи по E?)
Первое что приходит в голову — тупая дп за N^3 c пересчетом за линию(суммарно N^4). Если подумать, то можно прооптимизировать до N^3 с помощью метода двух указателей. Авторское решение также за N^3, там та же динамика, но написанная назад очень аккуратно.
Также заходит четвертая степень с хитрыми бряками =)
Обычно боюсь спрашивать дальше после ответа "тупая дп", но эта задача меня зацепила. Можно подробнее?
Зафиксируем левую точку ответа. Отсортируем все точки, которые правее по полярному углу. Затем считаем dp[i][j] — максимальную площадь, которую можно достичь, если последним ребром в многоугольнике будет ребро p[i]-p[j]. Как пересчитывать: переберем какое ребро будет следующим, проверим, что в новом треугольнике нет точек(можно заранее предподсчитать) и что ребра идут в правильном порядке(чтобы сохранялась выпуклость). Ну вот собственно и все.
Как решать J?
salam
Analysis?
How to solve E ?
Во-первых, с какой целью наборы тестов были увеличены по размеру на несколько порядков? На оригинальном контесте были уж совсем деревянные машины? Мне трудно поверить, что решение, которое в запуске на СF работает 0.03, на оригинальном контесте таймило бы. Это уже не NWERC 2002, это "мы взяли идеи из NWERC 2002 и на основании этого составили новые задачи". Актуальность сравнения с оригинальным монитором полностью теряется.
Во-вторых, отдельные лучи радости по поводу задачи С. Уже из указанных в условии ограничений на точность может показаться, что авторы не особо переживали по поводу возможных неаналитических решений. Тем не менее, для тренировки набор тестов был ощутимо увеличен, чтобы перебор так просто не проходил. И что самое интересное, в наборе остался оригинальный тест 28 39 90 39 11 180. Весьма коварный тест для любого перебора, с неожиданным ответом 39.0000 39.0000. Авторское аналитическое решение его успешно проходит. Я могу это понять, у меня тоже есть трудности с тем, чтобы отличить "влево" от "вправо", но я хотя бы никогда не составлял задачи, и вряд ли когда-либо буду. А авторское решение не улавливает разницу между этими двумя понятиями, да и зачем — найдем какой-нибудь ответ, ну и ладно.