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

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

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

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

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

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

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

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

UPD: зашло

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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