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

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

Всем привет!

В эту субботу (26 октября) в НИУ ИТМО пройдет четвертьфинал Северного региона ACM ICPC. Для участия в нем зарегистрировалось более 70 команд. Хотелось бы напомнить участникам, что необходимо удостоверится, что вся ваша команда прошла регистрацию, и каждый участник заполнил раздел "Extra information".

А в воскресенье (27 октября) состоится Двадцать первый командный чемпионат школьников Санкт-Петербурга по программированию, в котором примет участие более 70 команд.

Монитор и расписание четвертьфинала, как обычно, будут доступны здесь. Чемпионата школьников — здесь.
Так же за новостями соревнований теперь можно следить в твиттере.
Хештег четвертьфинала: #NSNEERC2013, чемпионата школьников: #СПбКОШП2013

Свои фотографии с четвертьфинала можно добавить сюда, со школьного чемпионата — сюда.

Желаем всем участникам удачи,
Пресс-служба соревнований.

UPD: Результаты прошедшего четвертьфинала.

Поздравляем команды, прошедшие в полуфинал:
SPb SU 4 (Kunyavskiy, Egorov, Suvorov)
SPb NRU ITMO 1 (Bardashevich, Minaev, Vasilyev)
SPb SU 1 (Pyshkin, Smykalov, Andreev)
SPb SU 2 (Simonov, Gordeev, Sayfutdinov)
SPb SU 6 (Krachun, Kuzmina, Voronetskiy)
SPb NRU ITMO 2 (Komarov, Krotkov, Demianiuk)
SPb NRU ITMO 5 (Peresadin, Belonogov, Voit)
SPb AU 1 (Sluzhaev, Krasko, Savinov)
Petrozavodsk SU 1 (Shapovalov, Filev, Ioffe)
SPb NRU ITMO 4 (Garder, Vedernikov, Kovsharov)
Northern FU 2 (Dodin, Chesnokov, Popovich)
SPb AU 2 (Kolganov, Velikiy, Ivanov)
Pskov SU 1 (Kovalenko, Barsuk, Petrova)
Petrozavodsk SU 4 (Ermishin, Krasnov, Starkov)
Pskov SU 2 (Dmitriev, Shalabod, Shantarin)
SPb SU of Telecom 1 (Yastrebov, Kiselev, Tarasov)
SPb SPU 2 (Egorov, Serov, Kapralov)
SPb SU of Telecom 3 (Orlov, Veselov, Sholokhov)

Напоминаем, что тут появились фотографии.

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

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

Четвертьфинал уже, наверное, прошел, где можно табличку увидеть? На сайте из поста я не нашел.

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

Правильно ли я понимаю, что информация в таблице Team Limits для полуфинала (на сайте NEERC) не совсем соответствует реальности?

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

    Если ты об этом, то у СПбГУ и ИТМО обычно дополнительная квота за проведение полуфинала.
    Ведь 'Universities can be allowed additional teams for hosting subregional contest, hosting global training camps, etc'.

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

      Ну вот и получается, что та информация не совсем точная. От MГУ отобрались 5 команд (хотя указано что, должно быть 3), от СГУ — 3 (хотя указано, что должно быть 2).

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

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

        AFAIK, квоты расширяет жюри ЧФ и NEERC уже по итогам олимпиады.
        При этом важно, что при появлении "лишних" команд квота всего четвертьфинала так же увеличивается. То есть не может получиться так, что добавление "лишних" команд выкинет последних выходящих.

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

Добавьте пожалуйста Питерский четвертьфинал в тренировки.

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

    Было бы неплохо, если бы организаторы просто выложили архив. Очень хочется протестировать свое решение на C с питерскими ограничениями.

    Кстати, кто знает на нее решение лучше, чем за ? За указанную асимптотику — это перебор всех O(n2) шаблонов для замены, поиск их с помощью Z-функции и СНМ и дальнейшая проверка с помощью Z-функции.

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

      У нас решение было за O(n^2) с хешами. Переберем подстроку из первой строки. Найдем все ее вхождения (непересекающиеся). Одинаковые подстроки будем обрабатывать один раз за O(количество таких подстрок). Для этого каждый раз будем считать хеш строки, которая получится, если заменить все непересекающиеся вхождения этой подстроки. Исходя из длин строк и количества вхождений, можно определить длину строки, на которую необходимо заменять текущую подстроку. Саму строку, на которую будем заменять, тоже можно определить однозначно — это подстрока второй строки, которая начинается с символа, который соответствует первому вхождению подстроки в первую строку.

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

        Я Вашу идею понял. Значит, мы изначально перебираем длину заменяемой подстроки, потом для всех подстрок данной длины запихиваем их хеши и позиции во что-либо вроде map<hash, list> (очевидно, для достижения нужной асимптотики, нам нужно использовать HashMap, unordered_map или свою хеш-таблицу). Далее для каждой группы равных подстрок оставляем только непересекающиеся. Как уже было сказано, то, на что мы выполняем замену, определить очень просто. Мы берем и выполняем эту замену, попутно пересчитывая хэш итоговой строки, после этого сравниваем его с тем, что нам нужно получить.

        Большое спасибо за объяснение.

        Кстати, теперь я додумался, как оптимизировать до похожей (все-таки чуть худшей — O(n2 * α(n)) ) асимптотики свое решение с Z-функцией — не нужно несколько раз искать вхождения одинаковых подстрок.

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

      У нас решение за честный чистый квадрат без хэшей.

      Основные идеи:

      1. За квадрат можно сделать несколько предподсчётов вида "lcp s[i..n] и t[j..m]" (это очевидная динамика с двумя переходами — два цикла),
      2. Пусть мы зафиксировали первое вхождение строки X, которую меняем в строке A (A была изначально, надо получить B). Надо, во-первых, проверить, что это действительно первое вхождение (надо просто при движении левой границы поддерживать минимальную длину при помощи предподсчёто). Во-вторых, давайте как-нибудь найдём все последующие вхождения этой строки в A, которые будут заменены. Пока за линию (уже куб).
      3. Пусть получилось K вхождений. Тогда за O(K) мы можем проверить, верно ли, что такая замена нам подходит. В самом деле, мы знаем, сколько символов останутся нетронутыми, а значит знаем длину строки Y, на которую заменим X. Также очевидно знаем, какие куски останутся нетронутыми (их K+1). Теперь надо проверить, что эти куски действительно не изменились по сравнению с A, а оставшиеся K одинаковы. Это действие выполняется за O(K).
      4. Теперь заметим, что пункт три работает за квадрат. В самом деле, каждая подстрочка (а их квадрат) обрабатывается как "кандидат на замену (не обязательно первый)" только один раз.
      5. Оптимизация второго пункта: при фиксированной левой границе и увеличивающейся правой будем поддерживать список позиций, из которых может начаться новое вхождение (LCP >= текущей длины). Если на какой-то позиции LCP стал слишком мал — выкинули из списка. Таким образом у нас в каждый момент бесплатно есть все вхождения данной подстроки в A. Из них можно жадно выбрать нужные по условию. При этом данная оптимизация также работает за квадрат по тем же соображениям из пункта 4.
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        А СНМ-то был и не нужен...

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

        Спасибо за очередной урок.

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

      Все материалы четвертьфинала доступны здесь.

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

        Если бы они были там доступны, я бы это сюда не писал.

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

          Вроде бы же все есть. Рядом с "Standings" есть ссылки на тесты, условие, решения жюри...

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

            Сдуреть... Захожу на страницу — никаких материалов не вижу. Пару раз обновляю — опа, появились. Firefox 24.

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

Где можно найти презентацию с разбором задач этого контеста?

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

Можете объяснить задачу Problem D. Dwarf Tower?

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

    Чуть выше появился разбор задач, можете посмотреть.

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

      Спасибо — но разбор короткий :)

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

        Чуть более развёрнуто:

        1. Инвариант: у нас в каждый момент времени для каждого предмета есть некий способ его получить (купить сразу или через размены), для всех предметов со стоимостью  ≤ X мы точно знаем, что это окончательные данные. При этом все комбинации этих предметов также учтены. То есть если есть точные предметы A, B, а их комбинация даёт C (про который еще точно не известно), то стоимость получить C не выше суммы стоимостей A и B.
        2. Теперь выбираем самый дешёвый предмет, про который мы еще точно не знаем. Утверждение: уже знаем, потому что из более дешёвых его уже поскладывали, а более дорогие смысла брать нет: взять всего один такой предмет будет дороже, чем собрать по текущей схеме (даже если в будущем этот предмет подешевеет, то это будет лишь потому, что в его схему добавится либо наш предмет, либо более дорогой).
        3. Теперь нужно посмотреть, какие комбинации стали необработанными. Это те, и только те, которые не были обработаны до текущего момента и в которых присутствует наш предмет. Пройдёмся по ним по всем и попробуем улучшить ответ для всех предметов, которые получились.
        4. Итого на каждой итерации у нас исчезает один предмет, за линию мы ищем минимальный — квадрат. Релаксаций в сумме O(m), поскольку каждая происходит только при добавлении одного из двух предметов, которые участвуют в обмене.