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

SnarkNews summer series 2015 — Round 2
Автор abistrigova, история, 9 лет назад, По-русски

Закончился второй раунд. Интересно, как решать C, F?

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

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

Интересно я один пытался запихивать хеши на B ?

Расскажите пожалуйста нормальное решение)

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

    У меня зашло решение в лоб: для каждой клетки-центра креста расширяемся, пока можно, и обновляем ответ.

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

      Обидно)

      Я писал бинпоиск + хеши, думал еще как-то Манакера использовать)

      Спасибо)

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

        Я успел только прочитать эту задачу, но мне кажется, что можно использовать идею выше, только сравнивать за раз сразу по 32 клетки с помощью преобразований масок в инты. А при неравенстве уже влоб проходить. Итого должно получаться O(N^2 * (N / 32 + 32))

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

    А почему "запихивать"? Оно там вполне нормально заходит, без каких-либо проблем. Памяти на все хватает, по времени — у меня 0.684, запас х10.

    Антихештестов тоже нету :)

    Upd. Код.

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

      значит я криворукий)

      Все время ВА получал

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

      Спасибо:)

      Переписал и зашло)

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

      С обходом антихеш тестов у меня 2.9, при этом на случайном макстесте на сервере (в задаче Х) 5 с

      → Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

F: Для начала посчитаем, какое количество монет может быть перевернуто после выполнения всех действий. Заметим, что если после выполнения некоторых действий может быть перевернуто минимально min и максимально max монет, то может быть перевернуто и произвольное количество монет cnt, такое что min ≤ cnt ≤ max и cnt совпадает по четности с min и max (они всегда совпадают по четности между собой). Поэтому будем просто выполнять последовательно действия и считать эти min и max после каждого действия, зная каковы они были перед выполнением действия. Внутри перехода min и max я считал разбором нескольких случаев, примерно так:


		// здесь они названы from и to и показан код, считающий следующее значение для from
		// x - количество монет, которое надо перевернуть в данный момент
		if (from >= x) from2 = from - x;
		else if (x >= to) from2 = x - to;
		else if ((from & 1) == (x & 1)) from2 = 0;
		else from2 = 1;

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

Полный код (метод solve в самом конце)

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

    А код для to во избежание багов можно не писать, а вызвать код для from с (from, to) --> (m — to, m — from), и взяв m — результат.

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

      Да, вчера вечером я тоже это придумал, но на контесте ограничился "скопировать, просмотреть ошибку, получить WA вслепую" за минуту до конца раунда.

      → Ответить