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

TopCoder Single Round Match 513
Автор freopen, 13 лет назад, По-русски

Завтра, 26 июля в 15:00 по Москве (время в других регионах), состоится TopCoder Single Round Match 513.

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

13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Номер раунда намекает на задачи с потенциальным переполнением типа :).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится
    Казалось бы переполнение 9битного типа было бы еще при 512...
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
I am really disappointed cause I can't compete in the contest.
I have my class going on at that moment.
good luck for others who have time & willing  to compete in the contest.


→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В 1000 проходил аккуратно написанный meet in the middle? И вообще, кто как решал 1000?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Да, проходил.

    Я заводил отдельный сет для каждой пары <p,m> в каждой половине. Здесь p - количество нечётных отражений, а m - количество чётных отражений.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ммм. А что такое четные и нечетные отражения?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Начальная точка (0) переходит в точку:

        2xk - 2xk-1 + 2xk-2 - ... + 2x1

        где xi - координата i-ого применённого отражения.

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

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

        Возможно с чётностью это несколько не совпадает=)

        Короче p - это количество отражений, для которых 2xi входит в получаемую координату со знаком (p)lus, а m - количество отражений, для которых 2xi входит в выражение со знаком (m)inus.

        В сетах хранятся собственно значения половины выражения т.е. 2*(сумма прибавляемых координат отражений - сумма координат вычитаемых отражений).

        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    На финале gcj-2010 была похожая задача, где он заходил для 30, так что для 20 не зайти вообще нет шансов.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Ну это надо было финал gcj писать :)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Там вроде было 2^, а не 3^
      Так что сравнимо
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну я ту задачу умею решать только за 3n / 2. Жюри вроде бы тоже, если верить разбору. А вообще там ведь почти такие же объекты можно перебирать, с той лишь разницей, что там должно было вычитаться ровно столько же, сколько и прибавляться, и были дополнительные несущественные ограничения.
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я решал так же как Степан. Но я видел решение Winger-а, так он сделал всего 2^20 сумм, разделил их по количеству слагаемых, и потом за линию считал лучшие разности. Он допускал что можно каждое действие сделать одновременно и чётным и нечётным (просто толку от этого нет), решение пишется проще чем наше с 3^10.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Интересно, почему в первом дивизионе так мало решений по 500.

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

Аналогично интересно, почему с первой многие так тупили - видел и какие-то динамики, и непонятные ДФС, и еще много ереси.

Ну а за себя рад, что впервые попал в топ100:) :)

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    В первой челенжил по следующему багу. брали макс. правое положение платформа и макс. левое, соотв. max и min, ответ умножали на max-min+1 , не проверяя, вдруг оно отрицательное.

    Эй, что за минуса?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

В чате topcoder промелькнула ссылка на будущий editorial по этому матчу:

Editorial

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

Кто-нибуть может зачеленджить идею решения 1000?:

<- Эй ты, научись читать условия задачи!! :)


→ Ответить