Да, у меня то же самое :)

Не могу не согласиться. Лично у меня значительная часть футболок так и остаётся совсем неношенной, потому что остальных хватает на несколько месяцев :)

Для второго критерия ещё можно удалить каждое ребро по отдельности и проверить, что в графе не образуется мостов. Сложность получается M^2 * log(M), но есть подозрение, что и за M * log(M) можно сделать.

Да, 17 итераций дают AC за 590 мс, 15 ещё нет (WA), но при 16 и больше без условия TL.

С double 15, с long double 17 :)

И не просто в несколько раз быстрее. 15 итераций отрабатывают за 550 мс, а 16 итераций не проходят.

Да, действительно оказалось, что взятие 64-битных чисел по модулю в Delphi работает на порядок медленнее, чем в FPC.

Честно говоря, отсутствие возможности запустить код на сервере довольно сильно помешало (использовать то, что за WA1 баллы не снимаются, на контесте я не догадался :)). У меня локально работало примерно 7 секунд, а во всех задачах разница по сравнению с серверами CF была как минимум вдвое. Но не в этой...

Поток не нужен. Если для каждого подмножества из K окружностей суммарный покрытый периметр не меньше totalLength*K/C, где C -- общее количество окружностей, то всё хорошо :)

Did you mean pretests? It works fine for the examples.

No one solved it yet, it seems the test case is broken.

Да, согласен. Я потратил где-то полчаса, пытаясь понять, где ошибка в моём решении. Более того, перед отправкой я задал вопрос: "Может ли Вася использовать информацию, которую он получил при просмотре некого режима, для открытия нового режима?" -- и получил ответ "Да", так что даже не было сомнений, что я мог понять условие неправильно.
Но вариант голосования здесь вполне уместен, поскольку действительно повлияло это на очень немногих участников.

В профиле единичные биты всегда идут подряд, достаточно хранить диапазон уже встретившихся в числе цифр

Для каждой пары строк проверяем, можно ли их склеить так, чтобы получить палиндром, за O(1) через хеши. Потом нужно найти максимальное паросочетание в произвольном графе. Если раздвоить вершины и рёбра, найти максимальное паросочетание в получившемся двудольном графе и поделить его размер на 2 -- проходит, хоть это и неправильно :)

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

Спасибо за поздравления! :)

По поводу моего тренера -- хочу отметить, что в последние годы я уделяю достаточно мало внимания контестам на сайте dl.gsu.by.

Действительно отец. :)

Путь, например, 1 - 11 - 4 - 6 - 5 - 8, если объединить вершины 4, 10, 17, 3 и 13 в одну - всего 4 объединения.

It seems my solution didn't consider transporting m goats at once, now it outputs 5 for 2 2 and receives WA 10, so the 10th test case is probably wrong.

Is pretest 1 the same as sample test 1?

Как автор решения официально заявляю, что цели уронить тестирующую систему у меня не было :)

Да, код был один и тот же. Проблема в том, что почти при каждой отправке я получал "not found", но иногда решение на самом деле отправлялось, а иногда - нет. А для того, чтобы это узнать наверняка, нужно открыть протокол посылок, при попытках просмотра которого я тоже зачастую получал 404. Конечно, 10 отсылок подряд делать не стоило, но всё-таки...

Да, я имел в виду решение NTU GladiaToRs. По крайней мере, у меня на тесте с N = M = 10⁵ без единого попадания в мишень это решение работает больше минуты.

А основная идея моего решения такая. Для каждой точки будем искать битовую маску по прямоугольникам, в которой на соответствующей позиции стоит 0, если точка лежит внутри прямоугольника, и 1 иначе. Для этого найдём:
1) маску множества прямоугольников, у которых правая граница левее текущей точки;
2) ... у которых левая граница правее текущей точки;
3) ... верхняя ниже;
4) ... нижняя выше.
Объединив эти маски, получим искомую.
А найти, к примеру, маску 1) можно так (остальные аналогично). До обработки точек отсортируем все прямоугольники по возрастанию правой границы и занесём в какой-нибудь массив. Теперь, когда задаётся некоторая точка, нас интересует битовая маска какого-то количества первых прямоугольников из этого массива (какого именно - можно найти бинарным поиском). Чтобы быстро искать необходимую маску, хотелось бы сразу запомнить маски для каждого префикса этого массива, но это займёт слишком много памяти, поэтому запоминаем маску для каждого префикса с длиной, кратной 1000. А теперь уже несложно найти маску для любого префикса.
Имея объединение этих битовых масок, можно быстро найти первый 0 в ней - это и будет искомый прямоугольник (прямоугольники сразу отсортированы по z-координате). Для удаления прямоугольника нужно пройтись по всем запомненным битовым маскам и в соответствующих ему позициях поставить 1.

Интересно, что это решение должно работать даже в случае, если выстрелы - это тоже прямоугольники :)

Был ли хоть один большой тест, в котором почти ни в одну мишень выстрелы не попадают? Если да, то странно, что тривиальное решение за квадрат со списком проходит.

Прошу прощения, тогда правильнее будет вот так:
1 0 1 0
11 -10 1 1.999
Ответ тот же

По поводу "0% после округления" - неправда :) У меня решение прошло, и на тесте
0 0 0 0
10 -10 0 1.999
у меня ответ
0.00
0.9937 1.0063 1.0000

Да, у меня тоже WA 35 и нет идей, в чём может быть дело.

Да, 10114 для первого и 10124 для второго дивизиона

Да, у меня так же прошло.

Если взять модуль, равный 2^N, то можно корректно выполнить N делений пополам.

Yes, this is correct. It's almost the same as the second approach described in the analysis (using Euler's theorem directly).

If your solution is as you wrote, then I believe it's wrong, at least for the case a = 2, b = 4, c = 12. Your answer is 1 while the correct answer is 2^4 mod 12 = 4.

Да, исправил

Да, многовато копий получилось. А я-то думал, что если комментарий не хочет добавляться, а потом я обновляю страницу и на ней нет комментария, то там его действительно нет :)

Удалите, пожалуйста, лишние копии.

"и наоборот - если для каких-то строк A и B B' является подпоследовательностью A', то строку B можно получить из строки A через некоторые операции из условия"
По-моему, эта фраза это и обозначает, но всё же добавил пару слов.

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