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

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

Закончился очередной этап опенкапа, давайте обсуждать задачи.

Интересует, как решать D.

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

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

Тут говорят, что так же, как и D с прошлого опенкапа

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

    Можно подробнее?

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

    Как вы умудрились не сдать ее?

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

      У нас не пересекаются составы на первые два этапа

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

    Хм, в задаче про "свертку" все очень мило решалось независимо по битам, так как требовалось вывести особую сумму. У нас решение задачи с всесиба выглядело как-то совсем по-другому.

    Для начала поймем "наивное" решение: мы можем для каждой маски перебрать ее подмаску, которую должен знать один человек из пары, а оставшуюся должен знать второй. Получилось 321. То же самое в немного другой интерпретации: для каждой книги мы можем перебрать, кто ее будет знать (0 — никто, 1 — первый, 2 — второй, а если знают оба, то мы можем выбрать кого-то одного).

    Теперь заметим, что возможных вариантов битовой маски для пяти книг (математически — монотонных функций от пяти переменных) всего лишь 7581. Поэтому для каждой пары монотонных функций от пяти аргументов мы можем предподсчитать их дизъюнкцию.

    После этого мы можем перебрать все возможные варианты для 16 книг (как бы выполнив подстановку 16 переменных в нашу булеву функцию), это 316. Раз мы 16 переменных фиксировали, значит каждый участник пары превратился в булеву функцию от 5 переменных, а дизъюнкции таких функций мы уже знаем.

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

Лично мне ещё интересно услышать про 3, 5 и 8.

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

    3) Переберем k. Пусть k' -- первая степень k, бОльшая n. Проверим за n / k', что соответствующие подстроки размера k' равны префиксу размера k'. После этого рекурсивно проверим это для префикса размера k'. Итого для одного k получается , что суммарно дает решение за .

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

      Подстроки можно сравнивать хешами, тогда вообще O(n) будет.

      UPD: На самом деле получается O(n log n) из-за суммирования по всем k.

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

        Мы z-функцией сравнивали. А как линию сделать? Там n log n из-за суммы по всем k.

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

      Воу-воу, откуда n·log2(n) то? Если я правильно понял, то для одного k ты делаешь n / k + n / k2 + n / k3... = C·n / k, то есть в итоге O(n·log(n)).

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

    В третьей задаче можно просчитать Z-функцию для строки, а далее надо заметить, что паттерны строк для фиксированного k (которые появляются при генерации Si(k)) имеют вид ki * m где m пробегает значения от 1 до k - 1, а значит, чтобы проверить всевозможные значения k, требуется достаточно мало действий.

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

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

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

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

    в 5 упихали такое: запустим дфс из первой вершины. будем хранить vis[vertex][width][height] — были ли мы в этой вершине с такими widht,height. После дфса тупо переберем все width и height у последней вершины, и выберем наилучший. Только нужно отсекать ветки dfs'a, когда мы зашли в вершину с более худшими параметрами, чем раньше.

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

    В 5-ой для каждого возможного значения ширина запустим Дейкстру и найдём максимальную высоту

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

    8, будем поддерживать для каждой колонии жива она или нет и очередь с приоритетами с расстояниями до других колоний, делаем n-1 итераций, каждый раз выбираем минимум (из очередей, выкидываем вершину если она относится к мертовй колонии), затем объединяем две колонии, пересчитывая соответствующи столбец и строку в таблице. Получается N*N*lgN

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

    В 5-ой, кстати, можно было для каждого значения ширины построить остов на переходах с максимальной возможной высотой — O(MAXW * N^2) с алгоритмом Прима.

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

кто ещё сдаёт на ejudge, уходите с него! один и тот же код (по 8ой) сначала получил тле 7 на ejudge, потом OK на yandex за 2.2 сек, а потом OK на ejudge.

upd. язык — c++

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

    Да, с 4-ой тоже самое.

    На Яндексе 5.5, на ejudge'е был TL.

    Это все очень печально, на самом деле. А нельзя никак на одних машинах тестировать?

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

      Насколько я знаю, там все тестируется на одной машине. Даже слишком на одной. На нескольких ядрах в параллель. Проблема скорее из-за этого может быть, если много памяти. Хотя возможно я давно не прав. snarknews знает лучше.

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

Как решалась сумма из второго дивизиона? Тринадцатая задача, вроде как.

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

а как 10 решать про бассейн?

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

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

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

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

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

Скажите, а у кого-нибудь получилось сдать в дорешивание D? Пытаемся это командой сделать, но всё, что угодно, даже полный перебор, в котором ну не может быть ошибки, или забитый в код вывод ответа на сэмпл, получает WA 1.

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

upd. Разобрались: оказывается файлы не нужны, а мы с ними отправляли. Спасибо всем, кто отозвался.

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

    У нас хоть и не сданное, но получает ровно тот же TL17, что и на контесте — т.е. первый тест проходит — как в дорешке на opentrains, так и на Яндексе.

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

    На яндекс контесте с файлами проблемы, попробуй без них

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

Кому-нибудь приходилось бороться с WA 15 по 10-й задаче?

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

а результаты собственно Всесиба где-то есть?

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

Any idea for 9?

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

The solution to D uses technique known as "fast zeta transformation".

Refer the solution of EvenPaths for more detail.

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

Поздравляю команду Saratov SU 1 с победой!!! Супер круто!!!

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

    Еще не до конца ясно, победили ли они — ранклисты с Яндекса и с ejudge еще не объединили. Или я ошибаюсь, и где-то есть уже объединенный ранклист?

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

    Результаты второй номинации Всесибирской олимпиады им. Поттосина ещё не разморожены.

    Более того, результатов нет ни у кого, кроме жюри Всесибирской олимпиады (это сделано во избежание возможной утечки), в частности, я не заносил полные результаты ни в одну из внешних систем (ejudge, Я.Контест), они там есть только в замороженном виде. Так что итоговые результаты Гран-При будут только утром 4 ноября, после закрытия основного мероприятия.

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

7ю задачу как решать? Там макс парсоч или что-то такое?

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

    без букв — стандартная задача, да, решается парсочем. одинаковые буквы нужно сжать в одну вершину, так как по условию чётность у них одинаковая.

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

      Перечитывал условие раз 10, а то что четность одинаковая у окрашенных пропустил... Спасибо)

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

hello,ftiasch,where can i find the problem of open cup GP of Siberia

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

Когда все-таки смержат ранклисты с Яндекса и ejudge? Очень хочется увидеть достоверную таблицу результатов!

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

Кто-нибудь может объяснить решение 9ой задачи про треугольники? У меня ничего толкового не получается.