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

Автор MikeMirzayanov, 13 лет назад, По-русски
Раз никто не написал такой пост, сделал я. Давайте здесь пообсуждаем раунд.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
прошу прощения, но не мог ли кто либо перевести мне 500 div1?  я надеюсь, это не противоречит правилам?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Противоречит.

    Collaborating in any way with anyone else (member or not) during a rated event is considered cheating. This includes discussing problem statements or solutions between the time that the coding phase begins and the time that the challenge phase ends.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да уж, ну и условия (
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто составлял условия???
В 500ку пол часа въезжал.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот странно. Когда на кодфорсес дают условия в разы длиннее этого и с кучей воды, все радуются, а тут формальное определение и ничего лишнего - так никто въехать не может. Мне оно показалось нормальным, понял с первого прочтения...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Во-вторых, там как раз нету длинных формальных определений) Как я уже сказал выше:)

      Ну и последнее, тоже довольно важный факт. Русский для меня не родной, но чтение условия на русском все же значительно меньше нагружает, чем на английском. Многие, как и я, читают вроде бы и без проблем, но "лучше бы не на англ..." :) Те, кто знает свой родной русский, но трудно читает на англ, явно сегодня возненавидели 500.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, я никогда не радуюсь длинным условиям, особенно когда в них много всяких определений, и самое важное, не на родном языке(но это, конечно, нужно исправлять...).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Идейно она мне понравилась, но вот все определения действительно запутаны. 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Может быть мне тоже она понравилась-бы, если-бы было побольше времени на написании и обдумывание, а не на понимание условия .
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ебу__е условия,  сказать, что они написаны через ж__у - не сказать ничего
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На чем 250 челленджили?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Некоторые добавляли в ответ все возможные ксоры, а некоторые с типом (в месте 1<<i, i>32)должно слетать, по идеи.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Некоторые просто кидали в сет попарный ксор строк, и выводили размер сета.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня в комнате 4 свалилось по тому, что вычисление c-'a', с-'A'+27 - это не верно, потому что нумерация с 1. Хотя сколько себя помню, всегда в таких условиях делали с 0. Ну вот нахіба такое делать?:(
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Нахiба - это то, о чём я думаю, только по-украински?))
    Горю желанием просветиться в нецензурной лексике, такому меня родня с Украины не учила))
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Неа, это не украинский язык, это киевский суржик.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нет, это выдуманное слово. Но с очевидным подтекстом. В общем, можно перевести как "Зачем":)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А я то уже обрадовался. Эх.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну переведи как "накакуя так делать?" если это удовлетворит страсть к поэзии... ;-)
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        я вот тоже задумался над корнями этого слова... с первого прочтения оно не вызвало ничего необычного. в голове пролетело лишь слово "навiщо". теперь буду знать, что ТО слово -  выдуманное =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      вообще, было бы немного странно, если бы maksay матерился в комменте, даже и на украинском - здесь же довольно много Ukrainian-speakers :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ужс, возникли проблемы с понимаем первых двух условий, особенно медиума. Первый раз такое на ТС.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Черт возьми, во время контеста не туда приписал +1 в медиуме. Въезжал в условие минут 10.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, вновь попал на тормознутости String в Java.В 250 честно написал перебор всех ключей и Куна. Но генерация графа происходила за O(50^3) - я не переводил строки в Long. В итоге O(50^5) дал TL. Я это заметил только к концу контеста, когда понял, что по 500 нет никаких идей. В итоге 75 вместо 212.
На челленжах от безысходности ломал всех, чье решение было подозрительно. В итоге +4 -3 = +125 очков, итого 200 в сумме. Но все равно обидно, могло бы быть гораздо больше.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Объясните, как нормально делать 500?

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

Но примерно за 10 минут до конца, когда я наконец-то доделал свое решение, возникли проблемы с дубликатами. Обломным был тест "а а в в", на который мое решение упорно давало ответ 5.

Отдебажить не успел:( В процессе решения я не строил в явном виде перестановки для ответа, а обходного пути для удаления дубликатов не нашел.

Можно было как-то просто? 

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Заметим, что мы, по сути, складываем 50-ричные числа, только не определены порядок разрядов и значение каждого символа. Тогда сначала для каждого столбца подсчитаем встречаемость символов, упорядочим по убыванию и сопоставим каждому символу цифру от 0 до 49 - это даст минимальную сумму в разряде. Далее упорядочим разряды по возрастанию сумм.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Слив засчитан...

250ка упала (ещё не понял почему). В 500ке почему-то забыл что можно для каждого столбца свою перестановку чисел (из-за чего очень удивлялся как это её столько человек сдает). Итого 50 поинтов. Мдя.

C 250ой понятно... Перепутал i и j в 1 месте...

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

    У меня круче слив, -50.

    В 250 сабмит... Дальше еще раз прочел условие... И почему-то вместо possible прочел positive :)

    Сначала думал ресабмитить, потом как-то не удавалось тест придумать на 0... Нервы блин...

    Перед началом систестов меня успокоили, что там positive:) Но я уверенно заявил, что все равно на чем-то упадет.

    Угадал. 

    А в 500 обломали повторы строк в инпуте.

    P.S. Я, по ходу, ступил так же, как rng58. long вместо long long, спешил блин:( :( Зато теперь поднимать рейтинг будет намного проще:) :)

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня тоже самое 250 упала хз почему, а в 500 тоже почему-то забыл, что в разных столбцах можно разные перестановки делать и весь контест тупил как ее решать.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Очень классные примеры сегодня; в 500 все числа, которые нужно в конце умножать на 50^i были во всех примерах одинаковые, и поэтому много людей умножали не в том порядке =)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А мне матч понравился. Жёлтым стал)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Мои поздравления!

    А у меня почти -200 (еще бы нет, последнее место в дивизионе), и теперь самый низкий рейтинг за последние 2.5 месяцев.

    И на CF не идет что-то, и на ТопКодере...

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не переживай. Наверстаешь.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Предпоследнее же вроде))
      PS: сам за 3 контеста убил полугодовой прогресс, теперь вот вроде по-тихоньку возвращаю, так что не переживай))
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Однажды за те же -50 очков получил -425 =) До сих пор побить не могу.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        -425 мне не светит, у меня потолок ниже (контестов уже написал слишком много:) :) ). Хоть это утешает.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      -133 и самый низкий рейтинг за последние полгода (точнее 7 месяцев даже). ;)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как 1000-ка решается?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Верное утверждение: такой цикл в графе существует тогда и только тогда, когда:
    1) граф связный;
    2) степень каждой вершины чётна;
    3) для каждой вершины кроме стартовой #рёбер любого цвета не более половины;
    4) для стартовой вершины #рёбер любого цвета - 2 не более половины.
    Доказывается просто, при этих условиях есть полное паросочетание по рёбрам для каждой вершины, соединим рёбра по этому паросочетанию, получим набор маршрутов, которые надо склеить. Склеить всегда можно, т.к. граф ориентированный и цикл всегда можно развернуть, добившись  выполнения условия на цвета рёбер. Необходимость вообще очевидна.

    Далее, построим лексикографически наименьший маршрут. У нас будет функция check(from, to, previous_color), которая проверяет, есть ли в текущем графе маршрут из from в to при условии, что сейчас запрещён цвет previous_color. Она проверяет какие-то условия, похожие на 1-4, только более запутанные. Будем строить граф по одному ребру, пробуя на каждом шаге добавить все возможные рёбра и проверить, корректно ли это добавление. Шагов будет O(n2), на каждом шаге O(n) вызовов функции check, итого время работы O(n5). Большая часть ресабмитов была видимо из-за багов в разборе случаев в функции check (по крайней мере, у меня именно из-за этого).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решается 1000 в div2?Кто-нибудь будет может объяснить?