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

TopCoder SRM 493
Автор Egor, 14 лет назад, По-русски
13 января в 5:00 по Москве состоится очередной TopCoder SRM
Так же в какое-то близкое время состоится тестовый раунд Facebook HackerCup - может быть, epic fail не продолжится
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотел поинтересоваться (на ТС пока ниразу не удалось поучаствовать онлайн), всегда ли время СРМа такое раннее? Бывает ли часов в 18-21.00 по Москве?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Лет 5 назад ответ был - да, почти всегда. Сейчас в месяц обычно проходит 1 СРМ в 5 утра на неделе, один в 8 вечера по субботам и один либо в 7 вечера, либо в 3 дня на неделе
    → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    http://www.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth

    Время указано не московское... для того чтобы узнать сколько это по москве нужно либо пройти по ссылке, либо сделать +8 часов
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Ты действительно надеешься что fail на facebook закончится?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Да. Именно для этого сделан этот раунд. В нем фейл вполне еще может иметь место быть
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По-моему первый раунд будет 15-го в 18:00 по Москве..
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это не первый раунд, это тестовый раунд. Он был анонсирован FB_David на форуме TopCoder
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      рофл... а на фэйсбуке его анонсировать не вар?

      Кстати, не знаешь, будут ли пересмотрены результаты ещё раз?

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не знаю. У меня есть информация только из открытых источников
        → Ответить
14 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
GL & HF
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, пожалуйста, как решать вторую задачу с див2, она же первая с див1?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    во первых, надо аккуратно написать функцию, которая говорит - можно ли из позиции x передвинуть белую фишку в позицию y.

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

    теперь, если для любого хода 1го игрока 2й игрок может сходить в конечную клетку - он выигрывает. иначе - 1й игрок может свести к ничьей: сходить в клетку, откуда 2й игрок не может добраться до конечной, а затем откатывать любой ход 2го игрока.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      2ой игрок побеждает только в том случае, когда белая фишка стоит в начале или в конце, то есть от его хода, когда он выбирает начальные или конечные подряд идущие фишки, второй может выиграть?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        я не до конца понял, что вы хотели сказать, но, возможно, это контрпример:

        N=10 M=9 K=7 L=7

        тут выигрывает 2й игрок.
        → Ответить
        • 14 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          Я поломал три решения таким тестом:

          N=6 M=4 K=3 L=1

          ничья

          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            а мне кажется, что там ничья...
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Уже исправил..
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                ну так тут все еще проще .. если k нечетное, то НЕничья может возникнуть только если четность m и l совпадает ...  Иначе одно вообще недостижимо из другого
                → Ответить
                • 14 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  Я придумал тест к другой трактовке условия в принципе. Я решал и челленджил задачу, что выбирается K подряд идущих ячеек содержащих ровно одну белую и делается реверс цвета каждой, а не реверс позиций массива. А это уже совсем другая и более сложная задача.


                  Так что мне повезло :)

                  → Ответить
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Я тоже решал задачу с цветами, а не порядком :) - решение точно такое же, реализация даже немного проще
                    → Ответить
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      А я так и не придумал решения.. по-моему оно много сложнее.
                      → Ответить
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Видимо сказывается утро. Уж не знаю почему я так перевел (сейчас я перечитал условие), но я тоже решал задачу про реверс цветов К подряд идущих шаров. И даже решил. Там закономерность несложная вырисовывается, если погенерить для небольших значений перебором. Поэтому на фазе челенджа удивился, когда меня зачеленджили :)
                    → Ответить
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  хотя нет ..что-то я натупил )
                  → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Спасибо этот тест мне помог.
          → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Блииииин... да я вообще не ту задачу решал :) невнимательно условия прочитал :(

      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так она вообще детская... странно что во втором диве за неё давали 600...
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        в том то и сложность - подумать как ребенок:D
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Ты ACRush'у скажи, что она детская) И ещё куче людей, которые вчера поднялись с нулём баллов)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Egor на последнем CFBR тоже не сдал задачу А. Это ж не значит, что она сложная.

          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            0 баллов на прошедшем SRM'е - это 220е место. По-моему, это о чём-то говорит. К тому же ACRush потратил на первую задачу почти полчаса.
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится +4 Проголосовать: не нравится
              ну она на самом деле не сложная, я думаю самое сложное в ней -- это 5 часов утра) 
              а вот у ACRush такой отмазы нет))
              → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
фейл-контест) у меня +1 рейтинга в 1 диве за ничего)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Можно считать, что не за ничего, а за то что проснулся в такую рань =).
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
как я хотел себя убить...
я забыл в 300 проверять, что тот блок, который мы переворачиваем - не вылезает на [1..N]

>_<

кстати, а 450 я запихал только в дорешивание... не знаю, как люди сдать могли - там нужно хачить и хачить, чтобы уложить в ТЛ и МЛ.

но в итоге оно у меня работает 18мс. на их сервере :-D
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    не нужно ничего хачить, простой перебор даже с  set<vector<int> > для мемоизации состояний проходит без проблем
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я написал решение на шарпе с отдельным классом под состояние, и хранение их в Dictionary. И у меня локально на макс тест работало секунд 5. Переписать на хранение состояния в числовой маске успел только через несколько минут после конца.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Локально это не интересно - может в арене проходило ?
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Навряд ли, у меня вроде и комп помощнее и фрэймворк поновее.
          → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Изначально K было до 9. Потом решили уменьшить до 7, а то там очень жестко оптимайзить надо чтобы прошло.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В 450 достаточно несложная динамика. Вначале перебор по ответу. А потом уже без особых проблем можно за 50 x 7^7 памяти решить, при помощи сохранения для каждого цвета расстояния до последней его встречи (если оно больше чем проверяемый ответ, то полагаем равным ответу). Пересчет - достатчно тривиален: если можем оказаться в позиции i с расстояними j (храним их в числе не превосходящем d^K), то перебираем цвета которые мы можем добавить и пересчитываем маску расстояний.

    На макс тесте работает около 0.7 сек.

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я не говорил, что она сложная =)
      вопрос в том, что там на грани ограничения. пришлось запихивать.

      хотя отмечу, что если бы ограничения были бы меньше... задача была бы уже не такой интересной =)
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что там за эпик фейл был расскажите? хотел поучаствовать, но совсем забыл про дату окончания. Там из-за этого epic fail-а не планируется еще один квал?)
→ Ответить