Сегодня в 19:00 по московскому времени состоится TopCoder SRM 538.
Начало coding phase — в 19:10.
Желаю всем интересных задач и высокого рейтинга!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 01:12:03 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
У меня одного тормозит? Сперва задачу не открывало, теперь не авторизует
UPD: зашло
У меня стало притормаживать только к концу раунда
Ужасно тормозит Test.
Я загнал здоровый тест в 250 (50 элементов), он не отвечал около 20 секунд. А программа исполнилась быстро (0.004).
Весь срм арена глючила, выдавала operation timed out
это самый ГРебаный топкодер, который я когда-либо писал
Мат лучше убрать.
UPD. добавь "гр" перед тем словом :)
не могу
можно отредактировать свой комментарий.
Проблема может быть в другом.
угу
Можешь, я в тебя верю.
Как решать вторую по уму и третью?
Вторая — заметим, что сначала выгодно идти вперед. Потом как-то повернуть и идти назад. Как повернуть? Динамикой посчитаем повороты на все возможные углы (рюкзак). Для каждого угла посчитаем насколько при этом мы удалимся. Выберем максимум.
Вторую, есть подозрение, что надо сказать, что нужно сделать так: пойти пока можно вперед, повернуться на как можно ближе к 180 градусов, пойти назад пока можно и сделать остальные повороты. Как можно ближе к 180 — это какой-то рюкзак.
Доказывать строго не умею, но очень похоже на правду.
Доказывается легко — задонаправленные вектора внесут каждый cos(alpha_i) * L_i, где alpha_i — угол поворта i-ого вектора. Альфы принимаю фиксированный набор значений, значит все альфы выгодно сделать с максимальным косинусом угла проецировния, что мы и делаем.
Третью — я хотел написать динамику D[height][used][left][tower][black], которая равна количеству различных картинок, где мы не различаем цветные кубики, где самая высокая последняя башня высота height, мы использовали в изображении башни used цветных кубиков, осталось left цветных кубиков, последняя башня имеет номер tower и осталось black призм.
Дальше очевидные соображения вида "высоты башен должны возрастать", "одна черная клетка строится как башня высоты на один меньше из чего охота плюс чёрная призма", чуть-чуть попариться и вывести переход динамики. Ну и к ответу в каждой точке прибавить значение динамики, умноженное на количество способов покрасить used использованных кубиков в наши цвета — это динамика чуть-чуть попроще.
Получается сложность порядка (N+2B)*N*N*B*W с КУЧЕЙ недоступных состояний
UPD: Говно короче, а не динамика. Обсуждение см. ниже.
У меня было что-то похожее, но время кончилось на том, что я не умею красиво запрещать ровно один из переходов BB+B (полностью видимый блок плюс половина) и B+BB (половина блока, а на ней полностью видимый блок).
Это лечится жадным отсечением и еще одним состоянием размерности 2 — цветной последний кубик или черный. Очевидно, что невыгодно ставить блоки так, чтобы черная единичка была выше черной пары.
Хм, и вправду. Почему бы не добавить состояние на "чем был последний блок". И руками не разрешить ставить на полпризмы полпризмы, на призму полпризмы.
(ответ Диме и Максу)
Да, можно ввести такой флажок. Но если запретить BB+B, то запрещается, например, картинка BBB, так как она может начинаться только с блока, а кончаться только половиной блока. А если запретить B+BB, ... у меня что-то тоже не клеилось, только я сейчас уже не понимаю, что. Может, всё и хорошо.
Ой-ё. Типа мы не можем погрузить призму на 1 в пол, да?.. Интересно, у скольких людей зайдёт на полный балл. Беру свои слова обратно — отстой а не динамика)
Да если это место неправильное, решение же свалится, скорее всего, уже на втором сэмпле, там много блоков.
Шикарные задачи. Ещё бы чуть-чуть, чуть-чуть и я бы написал свою первую тысячу!
Нет, нет, нет. Если бы я написал свою первую тысячу, при этом у меня упали 250 и 450 — это был бы самый угарный раунд в моей истории.
Помню, после того раунда, когда я сдал свою первую в жизни 500, я где-то на полсотни упал в рейтинге. Был вполне себе разрыв шаблона. У меня тогда первая упала, а вторая была сдана чуть ли не на 200, правда, но это уже мелочи :)
Вообще с тобой не согласен. 1050-ка — это просто сложный с точки зрения требуемой аккуратности и внимательности, безыдейный разбор случаев (переходов в понятно какой динамике). 450-ка — опять же абсолютно безыдейна, но с подставой с переполнением инта. Зачем она там — абсолютно непонятно. А 250-ка — это чистой воды испытание удачи — если повезет с комнатой будет тебе 3-4 челленджа на (-1%2=-1), не повезет — будет тебе -20 мест за просто так. Имхо, один из худших раундов, которые я помню.
По поводу подставы в 450 — я не знал про неё, когда писал коммент. Согласен, очень мерзко :-(
Ну а давать ли очевидный взлом или нет — я к этому отношусь нейтрально. Повезёт, не повезёт — всегда есть фактор случайности.
А 1050 вполне себе аккуратно писабельная, по мне — действительно красивая комбинаторная динамика.
Разве вторая — это не конструктив вида "сначала все forward, потом набор углов, как можно более близкий к 180, потом все backward"? У меня это взломали.
Именно так.
Наверное, какая-нибудь стремная ошибка в нахождении как можно более близкого угла
Да. Например близкий к 180 это 900. Ты это вроде не учитываешь.
И правда. Были мысли написать рюкзак по модулю, но я не захотел возиться с двухмерной динамикой. Спасибо.
Рюкзак по модулю — такая же одномерная динамика, не?
Как учитывать, что каждый предмет можно взять только один раз? В обычном рюкзаке мы шли с конца, а здесь конца как такового нет.
А, дополнительный массив ты воспринимаешь как двумерную динамику после того как мы оставили два последних столбца? Мне проще это понимать как одномерную динамику с дополнительным массивом :-)
или просто можно сначала засовывать в вектор то, что получили на текущем шаге, а затем обновлять массив динамики
Я обычно пишу честную двумерную. А здесь мне не захотелось писать длинную строчку инициализации vector(n, vi(185,0)); Ну в общем да, лениться не нужно.
Ну можно сделать псевдоодномерную (а именно до 50*360 градусов, а поом все скинуть)
Или переполнение =/
Я такой идиот! Сдал 450 на ~370 очков, а под конец контеста обнаружил, что 50 000 ^ 2 не лезет в int... Ну, хоть почелленджил.
Черт побери.....
А я сначала засабмитил код с дебажной проверкой за факториал)
А если перемножается double и int — переполнение происходит?
нет
если что то типа int*int*double, то происходит
я не один такой, обнаружил это за 40 секунд до конца
но даже почеленьжить не удалось (потому что комната адская)
оффтоп: и вообще, как происходит раскидка по комнатам? почему в одних 5 синих и остальные все желтые и зеленые, а в других 1 желтый и остальные синие?
Твою мать...
В панике пошёл читать код.. пронесло — даблы перемножаю, но, блин, мог напороться.
И как всегда — забыл про оверфлоу((
меня одного во время челленж-фазы постоянно выкидывало с сообщение "connection is lost"? +50 я так и пролюбил... :(
на прошлом раунде люди жаловались, но ко мне это пришло именно сегодня и во время челленжа.
Правда, что когда код отсылается на проверку, то отсылается последняя версия, которая прошла компиляцию? А то у меня в зачет пошла попытка с отладочным выводом. Ничего страшного нет, конечно, но я помню, что я его убирал перед сабмитом, но заново не перекомпилировал.
Тестится, сабмтится только компиленный код
Да.
Стоп, только что увидел, что в моей комнате решение по 250:
почелленджили. В чем оно неправильное?
wantedParity = 1
x = -1, y = 0
тогда (x + y) % 2 == -1, а не 1
% вернет -1?
Блин, надо было ломать такие решения...
у меня в комнате очень быстро сломали такое
У меня в комнате еще как минимум два таких решения висят.
У нас таких было всего 3..
по-моему, такого как раз не было, оба моих челленджа были на другом)
У меня тоже были на другом. Причем на тупости.
Тест ~~~~~ x = {-5, 1} y = {-7, 0} ~~~~~
И в одном wantedParity было 0, в другом 1, в обоих случаях ответ должен быть CAN.
взятие по модулю отрицательных чисел :)
{-1} {0} 1
{-1}, {-1}, 1 ?
видимо, на этот тест ответ все равно CANNOT, не?
Это тот случай, когда писать
if ((x[i] + y[i]) & 1 == wantedParity) return "CAN";хоть и плохо, но спасает от ресабмита и челленджей :-)Что-то задачи получились не на алгоритмику, а на крайние случаи и поведение ЯП(
раунд попахивает гавнецом, чувствуете?
в 250 прошло такое: для каждого i стратуем сначала (0,0) -> (x[i],y[i]) -> дальше не важно в каком порядке остальные. На каждой такой итерации смотрим чётность шагов.
Достаточно даже для i=0. Несложно понять, что это эквивалентно.
Можно было даже дальше (x[i], y[i]) не ходить. Все равно бы прошло.
Стало лень что-то делать, отправил random_shuffle 50000 раз и пошёл спать — тоже прошло)
да сколько же человек это написали, атас
Главное, чтобы 450 ни у кого так не прошла
А я один писал динамику d[len][last][0/1] = true/false. Это можем ли мы построить путь какой-то четности длины len заканчивающийся в вершине last?
а как вы проверяете, что вы еще не взяли вершину?
Ой, странная динамика. http://paste.ubuntu.com/892560/ — вот код, я если честно не могу сообразить почему она работает.
А если есть точка A с четной суммой координат и B, C с нечетной, то в вашем решении ведь возможна ситуация, что каждый раз будем заканчивать в B или C, что неверно, если wantedParity = 0.
Впервые испытываю чувство разочарования, решив 2 задачи на TC.
А у меня такое уже не впервые.
Еще один вопрос по формату контеста. В Coder History при клике на тест, который пройден неправильно, покажется строчка вида [%test_value%]:"SOME_ANSWER". Так вот, SOME_ANSWER — это тот ответ, который выдала моя программа, или тот, который они ожидали увидеть?
Судя по тому, что у некоторых в прошлый раз я видел [%test_value%]:NULL, то это значение, возвращенное твоей программой.
я не понял, в этот раз 1050 div1 == 1050 div2?
Я сравнил раздел Constraints, они отличаются, причем сильно. Это разные задачи.
Какой задачей в div1 была задача с кубиками и призмой?
1050, но говорят же ограничения разные
Ок, спс. А какие ограничения были в div1?
Открыты же практис румы)
Открой таблицу div I, кликни на результат bmerry (1 место) по этой задаче, например, высветится его код и условие.
Спасибо. А задачи совсем разные оказались.
ВНЕЗАПНО
Было бы ВНЕЗАПНО, если бы они оказались абсолютно одинаковыми.
1050.