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

Автор Omelianenko, 11 лет назад, По-русски
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

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

Андрей, кажется, у тебя анонсов больше, чем написанных раундов :(

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

It'll be at 6 am here in Mexico... I guess I'll need some coffee.

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

Очень странно видеть фразу "сегодня днём", написанную в 23:19)

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

У меня у одного недоступен сайт(и как следствие арена)?

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

    То же самое.

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

    Почему арена не грузится "как следствие"? Выкачайте jnlp-файлик, запускайте его, и на сайт вообще никогда не надо заходить...

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

      Как следствие — потому что не было Арены. Привык просто из идеи его открывать. Пожалуй, действительно, не прмешает сохранить

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

I have registered for contest but arena says 'Unable to launch application'.

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

I tried starting the Topcoder Arena since 5 minutes before the start of SRM 605 until now (7 minutes after the start of the SRM) without success. The Topcoder website is also very very slow and I cannot use their link for entering the arena (because sometimes that part of the website doesn't show up). However, all the other websites work just fine for me. Is anyone else having such problems?

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

Topcoder is down for the past 5-10 minutes...http://www.isitdownrightnow.com/topcoder.com.html

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

I bet CodeForces is behind this downtime. That conspiracy :)

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

Site is UP. Just logged in.

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

Как решать B,C?

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

    450: Первое, что можно заметить — это маленькое 1 ≤ k ≤ 10. Попробуем решить эту задачу с ограничениями k ≤ Bi - Ai, для всех i. Т.е. каждое число из первого множества стоит левее соответствующего числа во втором множестве. Эту задачу можно решить при помощи динамики dp[i][j][mask] количество способов раздать первые i - 1 чисел, так чтобы последние k - 1 чисел были розданы по маске mask (1 — если в первом множестве, 0 — если во втором), а в предыдущих числах остались j чисел из первого множества, которые не были "закрыты" числами из второго множества. Как можно заметить из динамики эти j чисел лежат на расстоянии более k от текущего числа. Поэтому можно сделать такие переходы:

    Дать число i первому множеству: dp[i + 1][j + (mask & 1)][mask >> 1] += dp[i][j][mask]

    Дать число i второму множеству, если j > 0: dp[i + 1][j - 1 + (mask & 1)][(mask >> 1) | (1 << (k - 2))] += dp[i][j][mask]

    Ответ будет лежать в dp[n][0][0].

    Теперь вернемся к исходной задаче когда k ≤ |Ai - Bi|

    Для этого можно заметить, что числа будут идти в определенном порядке первые левее соответствующих вторых, а после когда их количество будет равно, порядок может поменяться. Пример N = 4, K = 2, 1100|0011. К счастью такой переход можно добавить единственным переходом в динамике:

    Если j == 0 и mask == 0 Условие на возможность изменения порядка: dp[i + 1][j + 1][(mask >> 1) | (1 << (k - 2)] += dp[i][j][mask].

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

Как решать 1000 div2?

UPD2

Идея неверна

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

    Задача нахождения числа совершенных паросочетаний в двудольном графе принадлежит классу #P-complete

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

Наверное, я чего-то не понимаю, но как так получилось, что человек, занявший первое место в div2, сдал easy на 249 и medium на 499? Это же с какой скоростью кодить надо, чтобы так быстро сдавать задачи?

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

Как решается Div1 450?

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

    Состояние. Сколько чисел уже положили, сколько из них в первом, маска последних К-1 в первом.

    Ну теперь пытаемся положить очередное число в оба массива. В данный массив можно положить, если там уже больше или равно, чем в другом, или там сильно меньше (а именно, зависит от разницы и кол-ва элементов в маске другого массива)

    Код

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

      Why it is sufficient to know information about last K-1 numbers?

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

        When the position will be incorrect? When number you add at some moment is less then number which is "opposite" + K. What are "bad" opposites? last k — 1

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

          Другой вопрос: как к этому прийти?

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

            Ну не знаю, подумать, что требуется от состояния если в тупую перебирать за ответ. Можно еще догадаться, что раз K не до 50, то есть множитель 2^k. Ну и запилить запоминание.

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