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

Автор PavelKunyavskiy, 13 лет назад, По-русски
Опять таки, удивившись что темы до сих пор нет решил создать.

Завтра(а скоро уже сегодня), 20 января 2012 года в 6:00 MSD пройдет SRM530.
  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо за напоминание!
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +97 Проголосовать: не нравится
    Реклама: раньше я очень часто пропускал олимпиады и потом сожалел об этом, но теперь у меня есть clist.x10.mx и теперь я пропускаю только то, что хочу.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      А когда будет правильно отображаться оставшееся до соревнования время?

      Или оно только у меня неправильно показывается?

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А какой у вас таймзон и какой вы выбираете?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Таймзон московский, выбираю его.

          Сейчас 1:50.

          SRM в 6:00 - это показывает правильно. Но говорит что до него осталось 3 часа, а не 4.

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

            а в настройках оси таймзон +4 указан?

            UPD. У мну под семеркой для Москвы +3 выбирается.

»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Ой, как внезапно. Спасибо.
»
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
У меня в арену не заходит, у всех так ?
»
13 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
Любопытно, а зачем так упорно минусуют пост?
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Если вы крепко спите, не ставьте будильник (звонящий 30 секунд с интервалом в 10 минут) на 5:44 - может быть очень обидно потом.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне кажется, что условие 250-ки настолько ужасное, что даже нецензурно выразиться можно с трудом, чтобы передать все эмоции.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не хочу больше вылетать во второй дивизион. Тут контест длится 30 минут =( И всё равно наверняка на какой-нибудь задаче слажал.

UPD. Зато challenge тут весёлый :) Пары секунд до первого места не хватило.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Судя по тому, что там много народу уже сдали все, сегодня задачи простые.
    Иногда бывают значительно сложнее.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Знаю, но всё же... Судя по некоторому беспорядку в таблице, в первом дивизионе интересные задачи.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Первая простая, а потом слишком резкий скачок до 500-ки.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    С div2 1000 что-то не так - сейчас ни одного прошедшего решения.

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

      ОЛОЛО. Я вот не могу понять почему в тесте

      {
      "NYYYY",
      "NNYYY",
      "NNNYY",
      "NNNNY",
      "NNNNN"}

      ответ 7, а не 8

      0-4
      0-1-4
      0-2-4
      0-3-4
      0-1-2-4
      0-1-3-4
      0-2-3-4
      0-1-2-3-4

      UDP: если я правильно понял условие, то надо найти число путей из вершины 0 в вершину N-1

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если речь про div1-500, то все ребра последнего пути содержатся в предыдущих.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну например если он будет идти в этом порядке, то все переходы в последнем пути он уже когда-то выбирал, поэтому он не будет корректным
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

"For each pair of different stages i, j the game contains at most one such choice."

Это значит, что ребро в каждой игре используется не более одного раза, но в первом сэмпле 2 раза встречается  0 -> 1. Поправьте меня.

UPD.

Почему нет челленжа?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как быстро вбивать тест, являющийся ветором?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Вбиваешь кучу строк через запятую, потом жмешь ++
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, пригодится! А то который раунд очевидный хак не успеваю сделать)
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Традиционный вопрос относительно DIV1-500.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    На Codeforces давно пора сделать кнопку "Как решать 500-ку?"
  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    nevermind, о чем-то не том подумал.

    UPD: Решение в 1 правке кривое, а то, что я написал на раунде, к моему удивлению прошло.

    Я делал так: поддерживаем множество in, означающее, что из этих вершин достижима n-1 и они достижимы из 0. Далее на каждом шаге бфсом находим кратчайший путь из множества in+{0} в множество in+{n-1}, удаляем ребра на этом пути и обновляем множество in.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    1) Удалим нафиг все вершины, из которых нельзя добраться до стока или в которые нельзя добраться до из истока.
    2) Утверждается что после этого ответ E - V + 2.
    3) Почему это так. В наборе есть поднабор покрывающий все вершины. Пусть он состоит из cnt путей. Тогда общее количество путей не не более E - (V - cnt - 2) + cnt = E - V + 2. Значит от параметра cnt ничего не зависит и ответ не более E-V+2. Ну очевидно, что какой-то набор покрывающий все вершины существует.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня решение такое: Флойдом проверил достижимость стока из каждой вершины, после этого запустил ДФС из истока (вершины, из которых сток недостижим, не ДФСил). Если пришел в сток или в уже посещенную вершину - answer++. Вот код.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня решение совсем простое: ищем, пока можем, путь с натуральным числом не использованых рёбер. Количество таких итерацый и будет ответом.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        с любым натуральным? я искал с наименьшим натуральным.
         интересно услышать доказательство, что можно любой такой путь брать)
»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

мда, я редкостный идиот

я думал, что в 500ке в каждом пути не должны повторяться ребра (семпл в обратном меня не убедил :) )
придумал решение, написал, сдал... и понял, что этого не учитываю.
огорчился, как пофиксить, не придумал, пошел делать тест. и... 2 неудачных челленджа! тогда я решил перечитать условие...
надеюсь, медиум пройдет :D

UPD мда, 250 упала, 500 прошла.ну ладно, чо, первый медиум есть)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    После того, как ты понял, что слажал 500-ку, ты надеешься, что она пройдет? Оо
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да!
      я думал, что повалится на в 500ке в каждом пути не должны повторяться ребра, а оказалось, что на самом деле могут
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ага, прошла.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          а на чем могла 250 упасть? О_о

          UPD мда, у меня баг на баге был

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вот мне тоже интересно. Два челенджа которые я сделал - на совсем лаже у людей.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вероятно, из-за того, что cutter не влезает в cake.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А на что это влияет? На тесте где у меня упало все вполне прилично. 
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Не, там по условию, что cutter всегда влезает в cake.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Там не обязательно есть дырка в левом верхнем углу вырезалки. У меня на этом упала.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              У меня это учитывается, или пытается по крайней мере - упало.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я троих почелленджил на том, что они не учитывали, что в cutter '.' может быть не в [0][0], а значит, ему надо некоторое смещение.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А с учетом этого есть идеи?
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Ну кроме этого больше ошибок, которые могут быть общими, я не придумал.

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              А зачем вообще нужно было обращать внимание есть ли в [0][0] у cutterа '.' или нет?
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Многие как и я искали верхнее левое вхождение '.', т.к. по ней можно однозначно определить где должен находиться cutter, если расстановка валидна и т.д.. Но много кто не учитывал, что сам cutter должен иметь смещение.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Подскажите, пожалуйста, вот если тест
                  cake="XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
                  а cutter = "." почему ответ YES?
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Потому что мы ничего не вырезали.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  дак ни одного наложения cutter-а делать не надо
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Гарантируется, что в cake есть ',' же
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                ну как я делал:

                Берем в первой строке самый левый, его совмещаем в первой строке с самым левым из куттера, продолжаем


                UPD: нашел багу, вместо y<0 - x<0
                и на этом -120 :(
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Отличная бага в 250. Оказывается -2 иногда больше 3. А кто знает как заставить арену компилировать с -Wall?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Насколько я помню в арене варнингов много каких-то пишется. Там точно -Wall нет?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А зачем именно в арене? Ты совсем не компилируешь локально?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вообще не привык. Та древняя версия Kawigi, которая у меня стояла при этом жутко тормозит. Поставил новую, в практисе скорость вполне терпимая. Посмотрим. И еще везде строку компиляции поставил на -Werror. Надо приучиваться сразу нормально писать.