APIO - Codeforces

13 лет назад, # |

← Rev. 4 →

+18

Продолжительность тура — 5 часов. Начало в семь по Москве. Есть условия на английском, на русском — ~~нет~~ см. условия для Казахстана. Оценка по подгруппам тестов. Есть ~~полный~~ фидбэк (без токенов, неограниченное количество попыток) вида "вердикт на каждом тесте" — время выполнения/память/информация о полученных баллах и группах тестов отсутствует.

Рекомендую поучаствовать — мне понравилось.

→ Ответить

imslavko

13 лет назад, # ^ |

У нас были условия на русском (для Казахстана). И разве там полный фидбек?

→ Ответить

13 лет назад, # ^ |

← Rev. 4 →

Действительно, для Казахстана условия на русском.

Мне почему-то казалось, что да. Сейчас посмотрел еще раз — тестов стало сильно больше, значит, нет. Что-то я всё-таки мало спал.

→ Ответить

imslavko

13 лет назад, # ^ |

и вроде тесты различаются от старых

→ Ответить

pva701

13 лет назад, # |

← Rev. 2 →

1) сколько задач?

2) можно ссылку на прошедший контест (на условия хотя бы)?

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

pva701

13 лет назад, # ^ |

вечером будет на тех же задачах?

→ Ответить

13 лет назад, # ^ |

Да, соревнование было в один день и во все предыдущие года было 3 задачи.

→ Ответить

Gerald

13 лет назад, # |

Я что-то не пойму куда там тыкать, чтобы поучаствовать?

→ Ответить

13 лет назад, # ^ |

+12

Слева Competition -> Open contest. Там есть ссылка: http://open.apio2012.ioi-jp.org/.

→ Ответить

Gerald

13 лет назад, # ^ |

Да, спасибо. А у меня одного на этом сайте иногда какие-то иероглифы высвечиваются и все жестоко тормозит?

→ Ответить

13 лет назад, # ^ |

Не знаю, у меня вроде все нормально.

→ Ответить

pva701

13 лет назад, # |

правильно я понимаю, что от времени сдачи и количества посылок не зависит?

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Да, правильно, это же IOI система.

UPD: упс, ошибся.

→ Ответить

13 лет назад, # |

Вот блин, так и не додебажил 3ю. Оказывается, там еще и группы тестов при проверке.

→ Ответить

13 лет назад, # ^ |

Да, даже в правилах написано. А как время считается, есть идеи? Похоже на ACM.

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Наверное стоило прочитать правила :) Тогда бы хоть частичное решение по последней написал, а то видел что какие-то АС есть и решил что они и будут в финальном скоре.

А время там берется последнего увеличения баллов, видимо.

UPD: Не, туплю, время явно не такое берется.

→ Ответить

13 лет назад, # ^ |

Крутые у них компы — по 3-й квадрат запихался. У меня помимо бага из-за которого ВА еще был прокол в идее из-за которого оно ТЛило. Исправлять уже было лень, так я немного соптимизировал константу и оно прошло. Локально на худшем тесте посчитал количество итераций — выходит квадрат деленный на небольшую константу.

→ Ответить

13 лет назад, # ^ |

А за сколько зашло? Может, тесты кривые?

→ Ответить

13 лет назад, # ^ |

Зашло за 2.3.

→ Ответить

Zlobober

13 лет назад, # ^ |

Сколько работает на таком тесте:

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

Он ломает только так мой лучший квадрат.

→ Ответить

13 лет назад, # ^ |

Ну я тестил на аналогичном тесте: в одной строке слева стрелочки вправо, а справа от них в этой же строке стрелочки влево, причем все расположено симметрично относительно центра строки. Локально работает 3980 и выполняет 2.5 миллиарда операций.

→ Ответить

13 лет назад, # |

А расскажите, пожалуйста, как решать B и С.

→ Ответить

agul

13 лет назад, # ^ |

И ещё расскажите, как А на полный балл делать.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Я делал немного по-извращенски: Посчитаем для всех вершин отрезки входа-выхода. Тогда задача свелась к следующей: на отрезке находить максимальное кол-во элементов, которое можно взять, чтобы сумма не превысила M. Для этого отсортируем все вершины по возрастанию c_i и будем в порядке сортировки добавлять в персистентное ДО, которое будет считать сумму на отрезке и кол-во не нулей. Теперь, чтобы решить исходную задачу можно сделать бинпоиск по версии ДО и найти самую позднюю (т.е. с максимальным кол-вом добавленных элементов) версию, такую, что в ней сумма на отрезке не превышает M. Получается nlog²n. К сожалению, без оптимизаций такое не заходило.

Еще можно за ту же асимптотику, но по-другому. Просто в dfs-е можно было поддерживать для вершины декартово дерево c_i ее потомков. Если сливать декартовы деревья детей, добавляя элементы меньшего в большее, несложно доказать, что в сумме мы сделаем nlog²n операций. Узнавать наибольшее кол-во с допустимой суммой можно простым спуском по дереву.

→ Ответить

kostya_by

13 лет назад, # ^ |

Вместо декартового дерева можно просто хранить priority queue из STL. Всего выходит около 50 строк кода

→ Ответить

13 лет назад, # ^ |

priority_queue же умеет только добавлять и извлекать максимум? Как быстро считать сумму?

→ Ответить

kostya_by

13 лет назад, # ^ |

Мы будем отдельно хранить для каждой кучи сумму элементов в ней. Тогда когда сливаем две кучи просто складываем эти значения. Когда мы будем обрабатывать текущую вершину, сольем все кучи ее детей в одну + Ci текущей вершины. Потом будем выкидывать наибольший элемент кучи, пока сумма всех ее элементов больше чем M. При это несложно поддерживать сумму кучи.

→ Ответить

13 лет назад, # ^ |

Точно, у нас же M одно на тест.

→ Ответить

13 лет назад, # ^ |

Я кодил за ту же асимптотику, но можно и за O(NlogN). Вместо каких-либо деревьев можно хранить отсортированные векторы и мерджить их при подъеме по дереву.

→ Ответить

13 лет назад, # ^ |

А почему будет O(NlogN)? Вроде каждая вершина может просматриваться много раз.

→ Ответить

13 лет назад, # ^ |

Да, это я глупость сказал. Но зато, если использовать какую-нибудь такую кучу вместо priority_queue, то сливать сможем за O(logN) и в сумме будет O(NlogN).

→ Ответить

13 лет назад, # ^ |

а за O(Nlog^2N) ты как делал?

→ Ответить

13 лет назад, # ^ |

Просто при подъеме по дереву сливал priority_queue. Если сумма всех элементов в куче больше M, то доставал максимальный до тех пор, пока она не станет меньше.

→ Ответить

13 лет назад, # ^ |

А опять — разве каждая вершина не будет рассматриваться много раз?

А как именно сливать очереди?

→ Ответить

13 лет назад, # ^ |

Чтобы слить 2 очереди, мы из меньшей перебросим по одному все элементы в большую. Нетрудно заметить, что каждый элемент будет перекочевывать O(logN) раз.

→ Ответить

13 лет назад, # ^ |

Да, понял, спасибо.

→ Ответить

13 лет назад, # ^ |

A вроде как можно сделать и за $\text{[math]}$ (я не писал). Идея такая же, как и тут (k-я порядковая статистика на отрезке за $\text{[math]}$ онлайн персистентным деревом), только в персистентном дереве мы еще будем дополнительно хранить сумму соответствующих элементов, тогда спускаться будем так, чтобы сумма была ≤ M.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+13

Задача B:

Квадратное решение. Переберём ответ — хотим узнать, обязательно ли должен быть нинзя в кусте x. Добавим наблюдающего xx0 и попробуем проверить, нет ли противоречий. Как проверять? Для начала избавимся (предподсчёт) от отрезков типа "0" — посчитаем для каждого куста, покрыт ли он хотя бы одним таким. Если да, то нинзя в нём не сидит. После этого для всех оставшихся отрезков сократим их так, чтобы в каждом из концов мог сидеть нинзя (для упрощения).

Теперь необходимое условие: размер максимального подмножества попарно непересекающихся отрезков не превосходит k и у нас не менее k свободных мест. Очевидно, что если это не так, то мы не сможем выбрать k кустов и покрыть все отрезки. Докажем, это этого достаточно. Существует известный жадник для поиска такого подмножества — отсортировали отрезки по правому концу и набрали совсем жадно. Теперь выберем в качестве кустов правые концы этих отрезков. От противного несложно показать, что все отрезки покроются (иначе мы на каком-то шаге могли взять строго лучший отрезок). Если отрезков меньше k, то можно взять еще любые кусты.

Таким образом, умеем за O(n) проверять непротиворечивость, если запретить еще один куст (сортировка идёт прекалком).

Теперь оптимизируем до линии. Посмотрим на то, что делает проверка. Заметим, что построенное подмножество будет отличаться от изначального (когда ничего не запретили) только тогда, когда запретим один из выбранных правых концов. Если это так, то понятно, как изменится ответ жадника — мы уберём этот отрезок и продолжим построение с запрещённого элемента. Построение для хвоста можно предподсчитать линейной динамикой, изначальное разбиение также предподсчитывается, после чего либо бинпоиском, либо указателем мы находим номер отрезка в ответе, для которого мы удаляем правый конец и за O(1) пересчитываем размер множества. Если он стал > k, то в этом кусте точно сидит нинзя.

Итоговое время работы — $\text{[math]}$ .

→ Ответить

13 лет назад, # ^ |

+11

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

→ Ответить

13 лет назад, # ^ |

А к чему там кратчайшие пути в графе? Я правильно понимаю, что вершина — это промежуток между кустами, а ребро — сколько на заданном отрезке сидит ниндзя?

→ Ответить

13 лет назад, # ^ |

К системе разностных ограничений задачу можно свести так. Поставим в каждой ячейке 1, если там сидит ниндзя и 0, если не сидит. Перейдем к массиву частичных сумм (назовем его A) в который добавим еще фиктивную ячейку с номером 0, в которой никто не сидит. Тогда задача поиска расстановки ниндзя эквивалентна следующей системе линейных ограничений:

A_i - A_i + 1 ≤ 0 для 0 ≤ i ≤ N - 1.
A_i + 1 - A_i ≤ 1 для 0 ≤ i ≤ N - 1.
A_N - A₀ ≤ k.
A₀ - A_N ≤ - k.
A_i - A_j ≤ - 1 для всех интервалов [i, j] в которых сидит хоть 1 ниндзя.

Построим граф, в котором вершинам будут соответствовать A_i, а ребрам — ограничения. Для каждого ограничения вида A_i - A_j ≤ x проведем ориентированное ребро из j в i веса x.

Есть теорема, что система разностных ограничений имеет решение тогда и только тогда, когда в этом графе нет отрицательного цикла. По условию существует хотя бы одна расстановка ниндзя, так что изначально отрицательных циклов в нем нет.

Теперь мы хотим проверить, есть ли расстановка в которой никто не сидит в кусте i. Для этого мы заменим ограничение A_i - A_i - 1 ≤ 1 на A_i - A_i - 1 ≤ 0 и проверим, не образовался ли отрицательный цикл в графе. Рассмотрим 2 случая:

Цикл не проходит через ребро (0, N). Тогда можно показать, что если такой цикл есть, то он имеет длину 2, т.е. проходит через ребра (i, i + 1) и (i + 1, i). Это проверить очень просто.
Цикл проходит через ребро (0, N), которое имеет вес k. Тогда нам надо проверить, существует ли путь из N в 0 веса меньшего - k. Можно заметить, что в этом графе пользоваться ребрами веса 1 нам для этого не выгодно. Если их выбросить, а также вспомнить что мы выбросили ребро (0, N), то оставшийся граф будет ациклическим и кратчайшие пути в нем ищутся за O(N). Осталось проверить, что dist(N, i - 1) + dist(i, 0) < - k.

→ Ответить

13 лет назад, # ^ |

Да, это и имел ввиду. Про теорему не знал, спасибо. А там еще что-нибудь полезное есть?

→ Ответить

13 лет назад, # ^ |

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

Свойством найденного таким образом решения (без прибавления константы) является максимальность суммы x_i при условии, что x_i ≤ 0 для всех i.

Еще одним свойством этого же решения является минимальность разности между максимальным и минимальным значениями x_i.

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

Можно, но мне легче написать sort, благо ограничения позволяют.

→ Ответить