на codeforces можно удачно найти команду

Ну это смотря для кого. Вряд ли первокурсник сможет такую же команду найти в каком бы то ни было ВУЗе Украины. У нас с ACM движением все довольно печально — ВУЗы, где команды ценелаправленно и регулярно тренируют, можно пересчитать на пальцах одной руки черепашки-ниндзя. Остальным приходится тренироваться самим, чтобы чего-то добиться. Да и выход в финал — отчасти лотерея. Хорошо еще, что в некоторых ВУЗах, вроде КНУ, оплачивают поездки на разные сборы по программированию (Петрозаводские, Харьковские, может еще какие-то).

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

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

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

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

1. A_i - A_i + 1 ≤ 0 для 0 ≤ i ≤ N - 1.
2. A_i + 1 - A_i ≤ 1 для 0 ≤ i ≤ N - 1.
3. A_N - A₀ ≤ k.
4. A₀ - A_N ≤  - k.
5. 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 случая:

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

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

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

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

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

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

Зашло за 2.3.

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

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

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

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

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

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

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

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

Ну может 1300 и 1212 в объединении дают что-то близкое к 2000? Некоторые (включая меня) не писали 2А в силу каких-то других дел, помимо олимпиад. Наверняка кто-то по той же причине не писал 2B. Но, думаю, людей которые ни в одном не поучаствуют будет мало.

http://www.codechef.com/problems/TMRATING

Да, у меня тоже декартово дерево в решении. Просто я не уточнял, потому что подойдет любое BST.

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

Да, действительно. Довольно просто.

А как доказать что дфс посетит O(N) вершин?

Даже если взломают, то уже ничего не изменят. Тесты после контеста не меняются. А то так и решения с хешами можно валить и пропихи рандомизированные разные.

Пусть мы стоим в светофоре с номером i в момент начала зеленого света и мы хотим найти первый светофор после него, который будет красным во время нашего приезда. Для этого будем поддерживать бинарное дерево поиска, в котором ключами будут времена нашего приезда к светофорам с номерами j > i, а значениями будут номера светофоров. Также будем хранить минимальный номер светофора в поддереве.

Тогда чтобы найти первый красный светофор, можно сделать сплит по g и из правого поддерева взять минимум. А чтобы обновить дерево для светофора i — 1 на величину len, мы просплитим дерево по mod - len, ко всем ключам правой части прибавим len - mod, а ко всем ключам левой прибавим len. Затем склеим поддеревья в обратном порядке. Легко видеть, что от этого структура дерева не нарушится.

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

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

Да, в общем так и надо было.

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

Ну в общем да.

Ну так из-за этого здесь DSU работает за O(logN), а не за O(alpha) на операцию.

Уровней-то логарифм, но на каждый уровень мы заходим 2^k раз. А так как мы копируем не O(размера уровня), а O(N), то в сумме выходит квадрат.

Похоже на правду.

Так мы же на уровне k сделаем 2^k копирований, т.е. в сумме квадрат, разве нет?

Можно было сразу считать между двумя строками. Если результат больше 10⁹, то обрезать его до 10⁹. Правда там еще надо аккуратно рассмотреть случай, когда у нас всего одна строка данной длины. У нас подсчет количества строк длины len делался за O(N) и из-за этого ловили ТЛ. Чтобы сильно не модифицировать, мы бинпоиском нашли количество длин для которых возможна всего одна строка, а дальше уже перебирали остальные длины.

Нужно для каждого запроса на добавление найти следующий после него запрос на удаление этого же ребра.

Да, первое деление во вторую половину ничего не переносит.

Ну как, если мы добавили туда ребро, т.е. объединили 2 множества, то при этом было сделано сколько-то изменений памяти. Запишем все эти изменения в стек. Теперь чтобы откатить объединение, достаточно откатить сделанные изменения в обратном порядке, т.е. в таком, в котором они лежат в стеке.

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

Сколько раз одно и то же ребро могло быть добавлено в структуру одним и тем же запросом? Нетрудно убедиться, что на одном уровне рекурсии один и тот же запрос не будет обработан более чем 2 раза. Отсюда получаем, что сложность работы O(RKlogK), где O(R) — время выполнения одного запроса с нашей структурой.

Идея похожа на решение простого Dynamic-Connectivity при помощи разделяй и властвуй. Только там мы добавляли ребра в DSU, а затем делали откаты, а здесь будем добавлять ребра в лес linking-cutting tree (LCT). Возможны 2 случая:

1) Ребро соединяет 2 компоненты связности. Тогда просто соединяем их и ставим в LCT на ребро метку 0.

2) Ребро соединяет 2 вершины из одной компоненты связности. Тогда увеличим на 1 метки на ребрах на пути между этими двумя вершинами.

Теперь, если заставить LCT хранить количество нулевых ребер в каждой компоненте, то это и будет равно количеству мостов.

Кто-то знает, как делать B без linking-cutting tree?

У нас решение за линию с помощью автомата. Выше уже описано как это сделать.

У меня было неправильно сведение, но Дима рассказал как надо правильно избавляться от квадратов в знаменателе. Идея следующая: пусть мы хотим проверить, превышает ли наш ответ X или нет. То есть, нам надо узнать, существует ли такой набор из k вершин с суммой весов ребер sum, что sum / (200k - k²) ≥ X.

это эквивалентно sum + k²X ≥ 200Xk

Всего суммарная степень в подграфе (k² - k) / 2. Назначим ребрам новые веса: newcost_ij = cost_ij + 2X. Тогда 2sum + k²X = newsum + 2kX. То есть, нам надо проверить newsum - 398Xk ≥ 0.

Получили задачу: проверить, существует ли в графе с новыми весами подграф, у которого средний вес ребра не меньше 199X. Это уже задача HardLife. Как ее решать, можно почитать здесь.

UPD: Дима сам меня опередил. Правда, у меня оно сдалось только после некоторых плясок с бубном вокруг эпсилона.

Видимо, не пройдет. У меня выдает то же что и у dzhulgakov на том тесте, на котором у него упало.

Сейчас, если пройдет в практис руме.

Я такое накодил, но допустил тупой баг и оно не проходило семплы :( Там задача сводится к hard life с NEERC 2006.

На чем челленджили 500?

На самом деле второе выражение разбирать незачем, достаточно посчитать сколько раз в нем встречается *, [] и (). Еще облегчает жизнь подробное описание алгоритма разбора объявления переменной. Нужно просто накодить то что там написано, параллельно затирая первые k операций над переменной, после чего убрать лишние пробелы и вывести.

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

Ну на самом деле, руководствуясь только здравым смыслом, условием и семплами можно было понять все задачи. Правда, некоторые моменты все же были очень расплывчатыми и нечеткими.

Например, в этой задаче было написано что оказываться на одной планете дважды рискованно и нужно стараться так не делать, но нигде четко не написано, что нельзя дважды в одно время попадать на одну и ту же планету. Было ощущение, что можно вывести любой ответ, а потом подать апелляцию с формулировкой “но я же старался не дать агенту встретиться с самим собой”. Хотя, ясно что просто так это бы не упоминали в условии, так что в решении это само собой соблюдалось.

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

The situation is somewhat similar to the one after the SRM 539 at TopCoder. Model solution for 500 points problem was wrong, although 112 submissions passed system test with wrong test data.

NEERC 2006, задача Hard Life.

Как это не об этом? У многих претесты не проходило из-за того что выводили с недостаточной точностью. У меня, например, с 9 знаками не проходило 7 претест, а с 15 прошло. Наверное в чекере стоит эпсилон 1e-10 для проверки суммы.

Да, добавил один иф и прошло за 2.3.

Вот блин, из-за тупого бага не сдал Е. Там предполагалось решение за O(NlogNlog(answer)) или такое не пройдет по времени?

Да нет, просто в посылках maxscore обновляется не часто. Отсюда и высчитывает баллы оно там неправильно, на основании устаревшего результата. А в монитор выводит реальное значение. По крайней мере, это то что я заметил за время написания контеста.

Судя по всему, берется максимум.

P.S. коммент написан в английской ветке.

Да я и после первого их срма не получил, не говоря уже о втором.

Если честно, вообще не понял юмора — чем всем это решение не нравится, за что минусы?

Ну как, у нас есть битовая маска 8 чисел, которые мы уже поставили. Значит нам нужно чтобы у оставшихся 8 элементов была противоположная маска. Просто в хеш помимо сумм запихнем еще и маску.

В задаче про квадрат можно было еще написать Meet-in-the-Middle. Для этого сгенерим в начале все неупорядоченные четверки чисел, у которых сумма равна той что нам надо. Теперь, переберем все пары таких четверок, у которых нет общих элементов и попробуем поставить эти 2 четверки в первые 2 строки. Затем переберем порядок элементов в каждой из четверок. Теперь осталось все захешировать и запихнуть в map (я для надежности использовал unordered_map). Каждый раз будем вычислять прямой хеш, а также хеш пары четверок, которая с ней может стоять в паре (обратный хеш). Если в какой-то момент обнаружится, что в map’е у нас уже лежит обратный хеш — просто выводим ответ. Без никаких оптимизаций с симметриями и без ручного хешмапа работает 0.39. Есть, конечно, решения и побыстрее, но если это пооптимизировать, то, думаю, будет около 0.1.

Понятно, сорри. Значит, не надо было писать не разобравшись. Я просто прочитал сразу последнюю строчку про dynamic-connectivity и решил, что решение основано полностью на нем. Сейчас, увы, не могу вникать в идею, поскольку у меня всего 4 часа чтобы закончить курсовую.

А точно ли СНМ с откатами работает за O(alpha) в среднем на операцию? Ведь возможно, что каждый раз при откате мы будем восстанавливать какой-то путь, а затем сразу же его опять сжимать.

Ну, это жадность уже, так как перебора там нет практически.

Так если состояние проигрышное, то придется все ходы из него перебирать. А здесь каждое второе такое.

Тест: 2 1 4 3 6 5.

Здесь возрастающая более длинная, но выигрывает второй.

А как там перебор делать, который быстро определяет выигрыш первого?

Я разве что за O(NsqrtNlogN) умею персистентным деревом отрезков. Судя по ТЛу, вряд ли что-то более быстрое ожидалось.

Рассмотрим следующую динамику: f(mask, pos) — сумма по всем g(s), для которых первые pos бит маски s являются подмаской первых pos бит маски mask, а оставшиеся биты совпадают с соответствующими битами маски mask. Тогда пересчитывать ее можно так:

f(mask, pos) = f(mask, pos - 1), если pos-й бит равен 0,

f(mask, pos) = f(mask, pos - 1) + f(mask \ {pos}, pos), если pos-й бит равен 1.

Легко заметить, что второй параметр нам не нужен. Можно это все хранить в одном одномерном массиве:

for (int i = 0; i < m; ++i)
   for (int mask = 0; mask < (1 << m); ++mask)
       if (mask & 1 << i) g[mask] += g[mask ^ 1 << i];

После выполнения этого куска кода в массиве g как раз и будут искомые суммы по всем подмаскам.

ФБ с оптимизацией Тарьяна прошел, причем с запасом почти в 2 раза. Крутой алгоритм :)

P.S.: а простой ФБ без итераций, но и без оптимизации Тарьяна не проходил ни в какую.

Правду говорят, утро вечера мудренее. Вчера за полтора часа на контесте не придумал нормальное решение последней, а с утра за 10 минут пришло в голову.

Идея следующая. В начале для каждой маски запишем величину g(mask) — сколько есть ящиков, в которых лежит такая маска игрушек. После этого, для всех масок посчитаем величину f(mask), которая равна сумме g(s) по всем s — подмаскам mask. Теперь ответ будем искать по формуле включений-исключений: всего есть 2^n наборов. Вычтем из этого количества те наборы, которые не покрывают каждый отдельный бит. Затем прибавим те, которые не покрывают все пары и т.д.. При нормальной реализации это все работает за O(nm + 2^m * m).

Вот код.

В четвертой можно было выводить отрезки (5000, i) — (i, -5000) для i начиная от 4999. Я, правда, вместо этого написал извращенную жадность, которая соединяла верхнюю и нижнюю стороны отрезками, а затем забил массив констант.

Ясно, я за квадрат делал оптимизированным Гауссом. Работает всего в 2 раза дольше :)

Там система за линию решается?

А можно и без итераций. Мне, правда, один символ надо было в решении поменять, чтобы прошло. Но у меня сложность O(HP1 * HP2 * 30 * 2 * 30 * 2).

I think its time to make a decision.

А оно без никаких дополнительных эвристик успевает? Можно код глянуть?

А что за ограничение имеется в виду?

А чем обычные частичные суммы плохи?

20 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 На ideone на таком тесте работает 3.7 секунд.

Ну у меня решение за O(3^k * 2^(N-k) + 3^(n-k)). Для N = 20 выбирал k = 7. Решение следующее: разделим всех коров на 2 группы, в первой группе k коров, во второй N-k. Для обеих групп переберем все пары (маска, подмаска) и найдем суммарный баланс между коровами, попавшими в подмаску и коровами, попавшими в маску, но не попавшими в подмаску. После этого запомним пары (маска, баланс). Затем отсортируем и сделаем unique, т.е. уберем повторы. Переберем все пары (маска, баланс) из меньшей группы. Для каждой пары переберем все пары из второй группы, для которых баланс в сумме с нашим дает 0. Ясно, что таких пар не более 2^(N — k).

Как по мне, эта задача самая необычная. Я даже представить не смог, как оно должно распутываться. Немного порисовал на бумажке, на тесте из условия проверил свое решение, сдал и даже не тестил.

У меня вообще шаманство, которое я не доказывал. Я для каждой фиксированной маски проверял, можно ли убежать, следующим образом. Рассмотрим все тройки последовательных точек. Если в треугольнике с вершинами в этих точках не лежит ни одного столба из маски, то удаляем центральную точку из трех. Повторяем это упрощение до тех пор, пока можем. Если осталось 2 точки, то убежать можно, иначе — нет. Если аккуратно писать, то можно за O(2^N * M) реализовать.

Я так понимаю, контест уже закончен. Кто как решал задачу про веревку (Gold)?

Так это же решение, которое все писали. Не вижу я там поиска минкост циркуляции, да и ребра идут от левого конца к правому, а не наоборот.

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

У меня не влезло даже когда я уменьшил количество итераций Форда-Беллмана до min(400, M), где M — кол-во вершин в графе.

Это разве что в турбо паскале каком-то массив на 100000 нельзя создать. Пишите во Free Pascal.

У меня такое чувство, что если матч будет рейтинговым, то в мире станет одним миллионером больше.

Ага, у нас тоже много 250-к с виду правильных упало. Я даже не подозревал, что там есть какие-то частные случаи.

Вот ссылка. Я не сильно заморачивался и не удалял из кода лишние функции и переменные. Там много всего лишнего, но если не пытаться разобраться, то использовать можно :)

Я написал перебор, который хранит линию границы уже поставленной области. Каждый раз беру левую нижнюю точку и ставлю туда самый выгодный прямоугольник. Либо не ставлю ничего и сдвигаю эту точку. Для выбора прямоугольника используются всякие шаманства, а также перебор отсекается по времени. Чтобы лучше работало, я перебираю внешним циклом магическую константу и затем уже для нее запускаю перебор на 0.05 секунд либо 1000 итераций (что раньше наступит). В самом конце жадно улучшаю ответ. Набирает 5602 на претестах.

А я как раз тот раунд пропустил.

Классный контест! С INTERCAL вышло жестоко — по ошибке компиляции гуглится сразу, а вот вывести “INTERCAL” — задача совсем нетривиальная. 40 минут думал, что уже почти ее решил и остался только вывод :)

G — фибоначчи-подобная последовательность, H — просто рекурсивно фрактал порядка a строится и ищется координата точки с номером b, C — это это сумма частичных сумм в суффиксах.

Seems some of the AC solutions are getting “Internal Error” now.

А отсортировать?

Here is a link to the contest page in case if someone is still looking for it.

Is it possible to view the problems at least now?

Ответ на правку: я говорил про внутренний цикл. Возводить в степень M-K нужно всего N раз.

Ну так деление же на числа <=200, обратные к которым можно предпосчитать. Причем в разборе они так и написали, что “если предпосчитать обратные к этим числам, то сложность будет N^2*logM”.

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

Ну почему. Проходит и бинпоиском с динамикой за O(2^n * n^2).