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

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

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

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

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

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

    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, я никогда не радуюсь длинным условиям, особенно когда в них много всяких определений, и самое важное, не на родном языке(но это, конечно, нужно исправлять...).
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Идейно она мне понравилась, но вот все определения действительно запутаны. 
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Может быть мне тоже она понравилась-бы, если-бы было побольше времени на написании и обдумывание, а не на понимание условия .
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
ебу__е условия,  сказать, что они написаны через ж__у - не сказать ничего
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
На чем 250 челленджили?
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
У меня в комнате 4 свалилось по тому, что вычисление c-'a', с-'A'+27 - это не верно, потому что нумерация с 1. Хотя сколько себя помню, всегда в таких условиях делали с 0. Ну вот нахіба такое делать?:(
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Ужс, возникли проблемы с понимаем первых двух условий, особенно медиума. Первый раз такое на ТС.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Черт возьми, во время контеста не туда приписал +1 в медиуме. Въезжал в условие минут 10.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Блин, вновь попал на тормознутости String в Java.В 250 честно написал перебор всех ключей и Куна. Но генерация графа происходила за O(50^3) - я не переводил строки в Long. В итоге O(50^5) дал TL. Я это заметил только к концу контеста, когда понял, что по 500 нет никаких идей. В итоге 75 вместо 212.
На челленжах от безысходности ломал всех, чье решение было подозрительно. В итоге +4 -3 = +125 очков, итого 200 в сумме. Но все равно обидно, могло бы быть гораздо больше.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Угадал. 

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

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

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

Очень классные примеры сегодня; в 500 все числа, которые нужно в конце умножать на 50^i были во всех примерах одинаковые, и поэтому много людей умножали не в том порядке =)
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А мне матч понравился. Жёлтым стал)
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А как 1000-ка решается?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 (по крайней мере, у меня именно из-за этого).
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А как решается 1000 в div2?Кто-нибудь будет может объяснить?