Блог пользователя SkyHawk

Автор SkyHawk, 13 лет назад, По-русски

Сегодня в 19:00 по московскому времени состоится TopCoder SRM 538.

Начало coding phase — в 19:10.

Желаю всем интересных задач и высокого рейтинга!

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

У меня одного тормозит? Сперва задачу не открывало, теперь не авторизует

UPD: зашло

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня стало притормаживать только к концу раунда

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ужасно тормозит Test.

    Я загнал здоровый тест в 250 (50 элементов), он не отвечал около 20 секунд. А программа исполнилась быстро (0.004).

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Весь срм арена глючила, выдавала operation timed out

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

это самый ГРебаный топкодер, который я когда-либо писал

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать вторую по уму и третью?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вторая — заметим, что сначала выгодно идти вперед. Потом как-то повернуть и идти назад. Как повернуть? Динамикой посчитаем повороты на все возможные углы (рюкзак). Для каждого угла посчитаем насколько при этом мы удалимся. Выберем максимум.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Вторую, есть подозрение, что надо сказать, что нужно сделать так: пойти пока можно вперед, повернуться на как можно ближе к 180 градусов, пойти назад пока можно и сделать остальные повороты. Как можно ближе к 180 — это какой-то рюкзак.

    Доказывать строго не умею, но очень похоже на правду.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Доказывается легко — задонаправленные вектора внесут каждый cos(alpha_i) * L_i, где alpha_i — угол поворта i-ого вектора. Альфы принимаю фиксированный набор значений, значит все альфы выгодно сделать с максимальным косинусом угла проецировния, что мы и делаем.

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    Третью — я хотел написать динамику D[height][used][left][tower][black], которая равна количеству различных картинок, где мы не различаем цветные кубики, где самая высокая последняя башня высота height, мы использовали в изображении башни used цветных кубиков, осталось left цветных кубиков, последняя башня имеет номер tower и осталось black призм.

    Дальше очевидные соображения вида "высоты башен должны возрастать", "одна черная клетка строится как башня высоты на один меньше из чего охота плюс чёрная призма", чуть-чуть попариться и вывести переход динамики. Ну и к ответу в каждой точке прибавить значение динамики, умноженное на количество способов покрасить used использованных кубиков в наши цвета — это динамика чуть-чуть попроще.

    Получается сложность порядка (N+2B)*N*N*B*W с КУЧЕЙ недоступных состояний

    UPD: Говно короче, а не динамика. Обсуждение см. ниже.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня было что-то похожее, но время кончилось на том, что я не умею красиво запрещать ровно один из переходов BB+B (полностью видимый блок плюс половина) и B+BB (половина блока, а на ней полностью видимый блок).

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Хм, и вправду. Почему бы не добавить состояние на "чем был последний блок". И руками не разрешить ставить на полпризмы полпризмы, на призму полпризмы.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        (ответ Диме и Максу)

        Да, можно ввести такой флажок. Но если запретить BB+B, то запрещается, например, картинка BBB, так как она может начинаться только с блока, а кончаться только половиной блока. А если запретить B+BB, ... у меня что-то тоже не клеилось, только я сейчас уже не понимаю, что. Может, всё и хорошо.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ой-ё. Типа мы не можем погрузить призму на 1 в пол, да?.. Интересно, у скольких людей зайдёт на полный балл. Беру свои слова обратно — отстой а не динамика)

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Да если это место неправильное, решение же свалится, скорее всего, уже на втором сэмпле, там много блоков.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Шикарные задачи. Ещё бы чуть-чуть, чуть-чуть и я бы написал свою первую тысячу!

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Нет, нет, нет. Если бы я написал свою первую тысячу, при этом у меня упали 250 и 450 — это был бы самый угарный раунд в моей истории.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Помню, после того раунда, когда я сдал свою первую в жизни 500, я где-то на полсотни упал в рейтинге. Был вполне себе разрыв шаблона. У меня тогда первая упала, а вторая была сдана чуть ли не на 200, правда, но это уже мелочи :)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Вообще с тобой не согласен. 1050-ка — это просто сложный с точки зрения требуемой аккуратности и внимательности, безыдейный разбор случаев (переходов в понятно какой динамике). 450-ка — опять же абсолютно безыдейна, но с подставой с переполнением инта. Зачем она там — абсолютно непонятно. А 250-ка — это чистой воды испытание удачи — если повезет с комнатой будет тебе 3-4 челленджа на (-1%2=-1), не повезет — будет тебе -20 мест за просто так. Имхо, один из худших раундов, которые я помню.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      По поводу подставы в 450 — я не знал про неё, когда писал коммент. Согласен, очень мерзко :-(

      Ну а давать ли очевидный взлом или нет — я к этому отношусь нейтрально. Повезёт, не повезёт — всегда есть фактор случайности.

      А 1050 вполне себе аккуратно писабельная, по мне — действительно красивая комбинаторная динамика.

»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Разве вторая — это не конструктив вида "сначала все forward, потом набор углов, как можно более близкий к 180, потом все backward"? У меня это взломали.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Именно так.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Наверное, какая-нибудь стремная ошибка в нахождении как можно более близкого угла

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Да. Например близкий к 180 это 900. Ты это вроде не учитываешь.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      И правда. Были мысли написать рюкзак по модулю, но я не захотел возиться с двухмерной динамикой. Спасибо.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Рюкзак по модулю — такая же одномерная динамика, не?

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А, дополнительный массив ты воспринимаешь как двумерную динамику после того как мы оставили два последних столбца? Мне проще это понимать как одномерную динамику с дополнительным массивом :-)

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Я обычно пишу честную двумерную. А здесь мне не захотелось писать длинную строчку инициализации vector(n, vi(185,0)); Ну в общем да, лениться не нужно.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ну можно сделать псевдоодномерную (а именно до 50*360 градусов, а поом все скинуть)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Или переполнение =/

»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Я такой идиот! Сдал 450 на ~370 очков, а под конец контеста обнаружил, что 50 000 ^ 2 не лезет в int... Ну, хоть почелленджил.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Черт побери.....

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А я сначала засабмитил код с дебажной проверкой за факториал)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А если перемножается double и int — переполнение происходит?

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    я не один такой, обнаружил это за 40 секунд до конца

    но даже почеленьжить не удалось (потому что комната адская)

    оффтоп: и вообще, как происходит раскидка по комнатам? почему в одних 5 синих и остальные все желтые и зеленые, а в других 1 желтый и остальные синие?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Твою мать...

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В панике пошёл читать код.. пронесло — даблы перемножаю, но, блин, мог напороться.

»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

И как всегда — забыл про оверфлоу((

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

меня одного во время челленж-фазы постоянно выкидывало с сообщение "connection is lost"? +50 я так и пролюбил... :(

на прошлом раунде люди жаловались, но ко мне это пришло именно сегодня и во время челленжа.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Правда, что когда код отсылается на проверку, то отсылается последняя версия, которая прошла компиляцию? А то у меня в зачет пошла попытка с отладочным выводом. Ничего страшного нет, конечно, но я помню, что я его убирал перед сабмитом, но заново не перекомпилировал.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Стоп, только что увидел, что в моей комнате решение по 250:

for (int i = 0; i < x.size(); i++)
   if ((x[i] + y[i]) % 2 == wantedParity) return "CAN";
return "CANNOT";

почелленджили. В чем оно неправильное?

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    wantedParity = 1

    x = -1, y = 0

    тогда (x + y) % 2 == -1, а не 1

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      % вернет -1?

      Блин, надо было ломать такие решения...

      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        у меня в комнате очень быстро сломали такое

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У меня в комнате еще как минимум два таких решения висят.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          по-моему, такого как раз не было, оба моих челленджа были на другом)

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            У меня тоже были на другом. Причем на тупости.

            Тест ~~~~~ x = {-5, 1} y = {-7, 0} ~~~~~

            И в одном wantedParity было 0, в другом 1, в обоих случаях ответ должен быть CAN.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    взятие по модулю отрицательных чисел :)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    {-1} {0} 1

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    {-1}, {-1}, 1 ?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      видимо, на этот тест ответ все равно CANNOT, не?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Это тот случай, когда писать if ((x[i] + y[i]) & 1 == wantedParity) return "CAN"; хоть и плохо, но спасает от ресабмита и челленджей :-)

»
13 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Что-то задачи получились не на алгоритмику, а на крайние случаи и поведение ЯП(

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

в 250 прошло такое: для каждого i стратуем сначала (0,0) -> (x[i],y[i]) -> дальше не важно в каком порядке остальные. На каждой такой итерации смотрим чётность шагов.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Достаточно даже для i=0. Несложно понять, что это эквивалентно.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно было даже дальше (x[i], y[i]) не ходить. Все равно бы прошло.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Стало лень что-то делать, отправил random_shuffle 50000 раз и пошёл спать — тоже прошло)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А я один писал динамику d[len][last][0/1] = true/false. Это можем ли мы построить путь какой-то четности длины len заканчивающийся в вершине last?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А если есть точка A с четной суммой координат и B, C с нечетной, то в вашем решении ведь возможна ситуация, что каждый раз будем заканчивать в B или C, что неверно, если wantedParity = 0.

»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Впервые испытываю чувство разочарования, решив 2 задачи на TC.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Еще один вопрос по формату контеста. В Coder History при клике на тест, который пройден неправильно, покажется строчка вида [%test_value%]:"SOME_ANSWER". Так вот, SOME_ANSWER — это тот ответ, который выдала моя программа, или тот, который они ожидали увидеть?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Судя по тому, что у некоторых в прошлый раз я видел [%test_value%]:NULL, то это значение, возвращенное твоей программой.

»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

я не понял, в этот раз 1050 div1 == 1050 div2?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я сравнил раздел Constraints, они отличаются, причем сильно. Это разные задачи.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Какой задачей в div1 была задача с кубиками и призмой?

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        1050, но говорят же ограничения разные

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ок, спс. А какие ограничения были в div1?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Открыты же практис румы)

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Открой таблицу div I, кликни на результат bmerry (1 место) по этой задаче, например, высветится его код и условие.

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Спасибо. А задачи совсем разные оказались.

              ВНЕЗАПНО

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Было бы ВНЕЗАПНО, если бы они оказались абсолютно одинаковыми.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        1050.