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

Автор Sultan, 12 лет назад, По-русски

Контест сегодня проводиться в не стандартное время : в 12:00 по МСК

Предлагаю после контеста обсуждать здесь задачи.

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

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

Saratov SU #1: Agapov, Fefer, Chumachenko — True dream team

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

    Ребята просто предложили написать вместе с ними. Для меня это, безусловно, позитивный опыт, поэтому глупо было бы не согласиться.

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

Блин, я люблю питерские туры. Респект за крутые задачи, которые, даже выступая в составе из одного человека, приятно и интересно решать!

А расскажите, кто как B делал? Я в ней написал некоторый вариант квадродерева (масштабируемся, пока не найдём квадрат с 60% единичек), долго пытался пихать с разными константами, а потом обнаружил тупейшую багу, поправил и сдал.

За "Орден Коварных Бобров" отдельное спасибо :-)

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

    Зашло такое: Найдём самый заполненный квадрат 15х15 и будем его во все стороны поочередно расширять, пока в том, что мы добавляем 60% черного. Ну и на всякий пожарный после этого пытаемся его чуть чуть сжать, вдруг скор от этого улучшится

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

      У нас примерно то же самое: только мы улучшаем по формуле, данной в условии. Сначала находим квадрат 15x15 с наибольшим счётом, а потом расширяем границы пока расширяется, причём так, чтобы значение формулы для расширенного квадрата было наибольшим...

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

      Также, но выбираем для расширения стороны, в которой больше всего черного(отношения черного цвета ко всему). Перестаем расширяться, когда это отношение меньше 1/2 (или меньше или равно).

      Так что тут почти любая жадина заходит

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

    Мы для каждой клетки брали квадрат 15x15 с центром в ней и считали количество черных клеток в нем. Среди таких квадратов выбирали те, у которых черных > 2/3, строили bounding box для их центров. Потом отступали на небольшие dx, dy от границ и выбирали оптимальный вариант, считая по формуле.

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

    У нас бинарная морфология зашла — возьмём структурным элементом квадрат 3х3, сделаем подряд эрозию, два наращивания и эрозию. Найдём прямоугольник описывающий оставшиеся точки. Если его в качестве ответа посылать было ВА 107, поварьировали на единички все координаты и нашли лучшый, зашло.

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

Мы применили медианный фильтр, в итоге осталась почти одна связная область, которую оставалось аккуратно обработать)

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

А как нужно было решать задачу А про хеши? И означает ли это, что хеши на кодефорсе теперь совсем опасно использовать? :)

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

    На GCJ была задача дано множество чисел надо найти 2 подмножества одинаковой суммы. Здесь делаем также будем искать 2 строки из 0 и 1. Выпишем хеш это получится просто сумма некоторых степеней p. Теперь решаем задачу также как на GCJ сдал ее eatmore.

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

    Я сдал такое.

    Давайте посмотрим на два полинома. Будем для простоты считать, что они оба имеют длину N = 105. Тогда их разность, которая должна оказаться нулём по модулю q, имеет вид

    c0·pN - 1 + ... + cn - 2·p + cn - 1, где .

    Будем искать небольшие суммы из какого-то количества степеней p, которые дают ноль в результате. Во-первых, давайте возьмём, посчитаем все степени p до (N - 1)-ой, отсортируем, и возьмём разности соседних. Так как степени p по модулю q ведут себя достаточно случайно, эти разности будут более-менее равные числа около . Это самое имеет порядок .

    Отсортируем эти разности, возьмём снова разности соседних, получив тем самым какие-то выражения вида (pa - pb) - (pc - pd). Они будут ещё на несколько порядков меньше. И так далее. На k-ом шагу мы будем фактически оперировать суммами из 2k степеней p с коэффициентами  ± 1.

    Вот оказывается, что к третьему-четвёртому шагу гарантированно находится ноль среди таких разностей. А значит, что можно найти вот эти использованные 8 – 16 степеней p, и построить соответствующие строки, состоящие из множества букв a, перемежаемых чем-то другим в этих степенях.

    Как-то так. I like it :-)

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

    Я думаю, если выбирать основание и модуль случайные, то вполне безопасно.

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

      Так прикол же в том, что здесь есть взломы и можно придумать тест, глянув в код.
      Вроде как спасает большой модуль ~10^17.
      UPD. Ок, всё понял. Случайные == рандомные.

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

    Я сдал полнейший рандом. брал мапу, ключи — хеши, зачения — строки. генерил на каждой итерации рандомную строку рандомной длины, длиной не более 10 символом. смотрел, есть ли такой хеш в мапе. если есть — то профит!

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

      Ты играл второй дивизион, с модулями порядка 1018 так не прокатит

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

У кого-нибудь были проблемы с тестом 5 в задаче H (Snakes)?

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

    Нужно умножить координаты на 2. Иначе часть внешности, может быть недоступна скраю.

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

      Что ты имеешь ввиду?

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

        У нас было решение по H, которое получало WA 5. Его основная идея — dfs от краев. Его проблема была на тестах типа

        1111111111
        1222222221
        1222222221
        1221111221
        1221331221
        1221331221
        1221111221
        1222112221
        1222112221
        1111111111
        

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

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

          Это все хорошо, конечно. Но у меня настолько кривые руки, что программа умудряется валиться по WA на 5-ом тесте, а Ваши тесты (включая нижеприведенный) проходит. Если что, вот код (не стреляйте, пишу как умею): http://pastebin.com/4zUaz5jh

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

          Зачем там дфс? Мы отлично сдали вариант запоминая 1 координату каждой змейки, потом пускаем из нее линию например вверх до конца карты, если встречаем другую змейку -в стек ее, если на стеке 2 одинаковых -убираем, в итоге получаем в чем лежит каждая, теперь каждому проставляем кто внутри (очищаем стеки до размера 1, этому одному ставим в дети текущего, если до этого ребенок был — ставим -1). Далее печатаем если у змеи нет родителей или у родителя много сыновей (-1 в поле дети), прошло сразу, хотя были проблемы с лишними пробелами в выводе.

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

            Ну мы ещё масштабировали картинку чтобы небыло случаев дурацких.

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

              Например?

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

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

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

    У нас было ВА 5, когда не проходило такой тест: http://pastebin.com/GTurg3vZ

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

И расскажите G, пожалуйста.

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

    Построили ДНФ. Выразили через штрих отрицание,и, или

    Вариант 1. Выразили так, что A, B входят 2 раза в A^B,AvB . Тут чтобы посчитать A_1 v A_2 v ... v A_N нужно не по очереди, а деля на 2 равные половины
    Пример выражения

    Вариант 2. Выразили сперва истину и ложь, через них то же ^, v, теперь уже A, B входят по 1 разу и все получается линейно

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

      А еще можно выразить отрикание, как стрелку от числа и 1. 1 делается как угодно. Всем привет от Copymaster.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится
    1. Выразим все четыре функции от одной переменной через штрих.
    2. Заметим, что , так что можно решить для масок m1 и m2 рекурсивно, а потом добавить к ним бит a.

    Получается вот такое решение, которое укладывается в 600 символов (а не в 500000, как предлагалось).