I saw a similar problem at the IFMO’s Internet Olympiad (russian statements, problem G). Unfortunately, jury’s solution and tests are incorrect.

Уже, как минимум, троим интересен ответ.

нечестно — слитно.

1. It’s Russian interface.
2. Sometimes there’s some other event as important as rated round. And if round is unrated, I’d better to participate in the event.

C:

• O(n²). Научимся считать для каждого ножа, сколько он пролетит. Поймём, что пока никто ни с кем не столкнулся, ничего принципиально не меняется. Возможных столкновений — O(n²). Переберём все пары, посчитаем за O(1), столкнутся ли два ножа, если да, то когда, отсортируем события, пробежимся по ним. Берём все события в текущей момент, оба ножа из которых еще живы, убиваем их. Получили, сколько пролетел каждый нож. Теперь задача: есть куча отрезков, сколько они закрасили клеток? Это какой-то scanline с деревом отрезков. Т.е. .

• Поймём, что все события нам рассматривать не нужно. Сделаем так: цикл, пока живы все ножи. Первым действием будет получить самые ближайшие события. Вторым — их обработка. Заметим, что два ножа могут столкнуться, только если они лежат на одной вертикали/горизонтали/диагонали. Теперь, чтобы обработать только самое ближайшее событие, для каждого ножа нам не нужно рассматривать все остальные — только соседей по направлениям (но не просто ближайших, а ближайших, которые смотрят в нужную сторону). Таким образом, мы за умеем находить все ближайшие события. Выполним все события, которые произойдут раньше всех (например, в момент t). Заметим, что поменялось немного — исчезли какие-то ножи. Теперь на следующей итерации нам бессмысленно обновлять информацию для ножей, все соседи которых остались живы. Нам требуется обновить информацию только дя O(X) ножей. где X — количество обработанных событий. Таким образом, мы выполним предподсчёта, потом на каждой итерации еще . В сумме у нас не более O(n) событий (каждое событие убивает хотя бы один нож, но, например, четыре ножа могут столкнуться в одной точке и это будет 6 событий, но это максимум). Поэтому итоговое время работы . События можно хранить в priority_queue, удалять нам необязательно.

А загружать еще приятнее.

Я сильно не уверен в универсальности этого способа. Матроиды, увы, не панацея, иногда легче доказать жадник “в лоб”, чем доказывать, что что-то является матроидом. Думаю, часто бывает и жадник без матроидов.

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

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

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

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

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

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

Задача B:

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

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

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

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

Итоговое время работы — .

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

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

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

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

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

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

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

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

Может, просто двоичный gcd? Писать его бинпоиском я не умею.

Awesome and interesting problems, thank you very much!

If so, it looks strange, because such problems usually doesn’t require any skills except very basic school physics.

Could you tell about these tests? What is it like? Contests, yes/no tests or something else?

What is Physics problem? IOI’s olympiad in informatics, isn’t it?

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

Думаю, что можете, про планки по рейтингу я ничего не слышал. Напишите Gerald’у, а дальше видно будет.

Look: you have an array: 1 2 3 4 5. It has the following prefixes: "“, ”1“, ”1 2", and so on. You calculate sum of numbers in each such prefix and get 0, 1, 1+2=3, 1+2+3=6, 10 and 15 (let’s call it s[]). Then, to calculate, for example, sum from 2 to 4, you just calculate s[4] - s[1]=9. Elements before 2 were reduced.

This idea can help you solving this problem: you run down left border of a substring and then you can calc amount of required substrings in O(1) for each left border.

Try this idea: calculate sums in all prefixes (from empty to the whole sequence) and then sum of elements in a some substring is difference of two numbers. Hope this helps. If not, I can give you detailed solution.

Даже шести

Пример. Общий смысл — то, что не пересекаются отрезки, не обозначает то, что не пересекаются пути, по которым еда падает.

Just good brute-force.

А также возможность копирования и запуска на произвольном наборе тестов.

This opportunity was a present from admins in the first days of new year.

Палево

Тогда я про производные и логарифмы почти ничего не знал :)

May be no, because not so many people have solved E in Div2.

Probably it won’t be.

Кто? Я?

There are problems with Div1C/Div2E — jury’s solution is incorrect. This problem is under investigation and round can be unrated.

Иногда просят вывести с ровно 4-я знаками после запятой. Тогда можно сравнивать без EPS вообще и вся точность — внутренние проблемы решения.

Казалось бы, при += как раз происходит перевыделение, а не создание нового — примерно как с vector<>::push_back.

Неверна.

Если её не указано, то лучше считать, что она равна нулю — так не ошибёшься.

Мне кажется, ошибаетесь. Вы выводите какие-то конкретные точные числа и можете гарантировать, чтобы сумма была <= без всяких EPS, поскольку сложение тоже можно (в теории) выполнить абсолютно точно. Значит, чекер вправе требовать точного соответствия.

Если можешь построить тест — убивать автора :)

А он доказывается?

Кстати, действительно интересно. Но так как в условии ничего не написано на сравнение суммы с EPS, то поведение чекера оправдано — он не более строгий, чем полагается по условию.

У меня два вложенных зашли, если ты про задачу B.

Кстати, в английской версии кто-то все-таки спалил участие cerealguy в подготовке раунда.

Правильно понимаю, что модуль находится под суммой?

У меня версия 4.6.1 выводит верно, но выдаёт warning, что некорректный placeholder

But sometimes they are so sloooooow. std::sync_with_stdio(0); treats it.

Еще реквестирую кнопки для управления с тачскринов :)

Knapsack problem is NP and it’s not solvable using greedy algorithms. May be there are some special restrictions?

И тестить на рандомном инвокере?

Спецэффект с atan2 и std::atan2 проявляется и при -O0

Мне не приходилось сортировать числа, которые расположены в цепочку с шагом <EPS. Так что обычно ничего страшного, но помнить об этом, конечно, стоит.

Не знаю, но еще мораль: нефиг писать using namespace std;, а то можно-таки напороться. Ну или EPS использовать.

На самом деле, мораль, скорее, такова: всегда используйте сравнение с EPS (ну или MSVC), вещественные числа в MinGW — странная вещь.

Еще интересный факт: atan2 отличается от std::atan2. Код:

#include <cstring>
#include <cstdio>
#include <cmath>

const int a = 1;
const int b = 32;

int main () {
  #ifdef __MINGW32__
  printf("I'm running on MinGW 32\n");
  #endif

  printf("%d %d %d\n",
    atan2(a, 0) < atan2(b, 0),
    atan2(a, 0) == atan2(b, 0),
    atan2(a, 0) > atan2(b, 0));
  printf("%d %d %d\n",
    std::atan2(a, 0) < std::atan2(b, 0),
    std::atan2(a, 0) == std::atan2(b, 0),
    std::atan2(a, 0) > std::atan2(b, 0));
  return 0;
}

У меня выводит

0 1 0
1 0 0

Выше ответили полчаса назад. Снимите галочку “Показывать неоф.”

Спасибо за объяснение.

Надеюсь, это был не троллинг, потому что сейчас будет большой ответ

Я предлагаю Вам включить интуицию и построить несколько логичных предположений “по умолчанию”, которые облегчат жизнь (в ней тоже приходится строить догадки и математический формализм иногда сильно усложняет ситуацию, говорю сугубо по своему опыту, может, у Вас что-то по-другому). Первое предположение — если “Z-функция работает за O(n)”, то, скорее всего, подразумевается алгоритм, ибо, как правильно замечено, математическая функция просто есть. Второе — реализаций Z-функции за линию ровно одна (как мне кажется) с точностью до мелких деталей, не влияющих на асимптотику. Из этого легко предположить, что ТС интересно доказательство асимптотики работы одного конкретного алгоритма.

Хорошо, что вы еще не видели задач с, например, некоторых Японских или Американских контестов. Мультитест, ограничения только на один тест (n ≤ 10⁵) и количество тестов (T ≤ 10⁵). Или, например, вообще ограничений нет. Или важного условия. Или формата вводы/вывода (что, впрочем, частенько и в Российских проскакивает). И вот тогда умение догадываться помогает получить плюсик минут за пять из предположения “а вдруг прокатит”. Или, например, в Петрозаводске (или в Харькове, не помню) была задача PrequeL, авторское решение для которой полностью лобовое, но, вроде как, существуют тесты, которые валят его по TL просто в хлам. Но такие тесты никто проходить не умеет, так что “догадайтесь, что таких тестов нет”.

И еще раз спасибо за честный ответ.

Тогда уж логичнее отдельный рейтинг Эло вводить.

Для K=10^6 решение получается вообще лобовое и безидейное и никак не тянет на 550.

A was melted by B’s plasma gun

Не удаётся подключиться по FTP, например, в тренировку http://codeforces.ru/gym/100035 (ВКОШП ’03). Far Manager говорит "“Windows socket error”, WSAECONNREFUSED“. Также недавние ошибки тестирования в этой (и других) тренировоках с подстрокой ”Server returned HTTP response code: 502 for URL:" подсказывают, что это не только с моим компьютером/провайдером, но даже тестер не может загрузить задачу.

Я заходил только как playerXXX

Спасибо, 8 –> 7.

Codechef — вообще что-то с чем-то. Флойд на 450 за секунду заходит (что, кстати, больше 10^8 10^7), а решение, по асимптотике лучше, чем авторское, но с деревом отрезков вместо set<> TL’ится в хлам. Там либо лютый рандом, либо какой-то треш с кешем/памятью, других объяснений не знаю.

Почему же не станет? Например, площадь незаклееных клёток увеличивается. С другой стороны, понятно, что за 5x5 мы никогда не выйдем (иначе применим соображение о полуплоскостях), поэтому перебор всё равно можно сделать.

Понятно, что первому игроку ходить так, чтобы фишки “расходились” не выгодно

А можно вот это место доказать более-менее строго, пожалуйста?

Может быть, это поможет? Хотя там, вроде как, какое-то кэпство

Можно зайти в соревнование и снизу будут все глобальные оповещения.

Там компы совсем отстой. Приблизительно 2*10^8 простых операций за секунду. И память/кеш “офигеть какие быстрые”.

У меня 300 ms.

Оффтопик: что обозначают синие баллы за задачу?

+= ставить бомбы += убивать соперников

Пробел — возрождение.

Думаю, на неполном/неправильном наборе случаев

Это 10⁸ операций. На плюсах должно с лёгкостью зайти.

Поправил.

Разбор всех задач. Идея — одна вершина в поддереве другой, если start_a ≤ start_b ≤ end_a, где start_i, end_i — время входа/выхода DFS. А теперь есть два дерева, таким образом каждая вершина — точка на плоскости, а два поддерева — прямоугольник. Либо двумерное дерево отрезков/Фенвика, либо сортировка событий и одномерное дерево.

Возможно, поможет.

Возможно, длина строки делится на 80? Вроде был какой-то спецэффект с этим в дельфи. Возможно, в более старой версии

Approximate meaning: 1)I enter Codeforces 2)Here I need to get in Top-300 2)Here I need to get in Top-50 4)When will be the round which I can fail?

No. You not only edges corresponding to works, but also you need edges from t to t + 1.

Про Стенфорд ничего не знаю, а вот насчёт MIT скажу — по информации из первых рук (от приёмной комиссии) олимпиады в расчёт практически не берутся. Только при прочих равных. А вот грант получить после поступления в теории достаточно просто, потому что need-blind admission, т.е. при приёме не учитываются финансовые возможности, а после поступления они сами оплачивают, сколько не хватает всем без исключения, главное — предоставить документы о доходах/etc.

ЮграНефтеТранс ?

MinCostFlow. Vertex is a time, and work is a edge with capacity=1 and cost=-C. We need to find minimal cost flow not greater than K. V~1000, E~1000 and you even don’t need Dijkstra’s algorithm with potentials.

MinCostFlow. Только вершины графа — не работы, а сжатое время.

Все можно достать на том же сайте (neerc.ifmo.ru/school), начиная с какого-то довольно давнего года.

There is one unofficial participant above Petr

По умолчанию.

Поставьте галочку “неофиц.” в таблице

Упала, потому что в одном месте вместо <= написал <

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

А в чём проблема несвязного графа?

Чуть-чуть случаев. Разбили на две доли. Либо в обеих долях количество вершин делится на три (тогда очевидно), либо в одной остаток 1, в другой — два. Будем считать, что в первой — один.

Теперь если в первой доле есть вершина, не соединённая хотя бы с двумя из второй, убиваем этот треугольник, дальше — очевидно. Иначе в ответе, если он есть, бывают только тройки из одной доли или тройки (“2 из первой”, “1 из второй”). Очевидно, что вторых троек будет 2 по модулю три, иначе не сойдутся остатки. Также в ответе, если он есть, можно сделать так, чтобы вторых троек было ровно две. Отлично. Нашли все вершины из второй доли, несоединённые хотя бы с двумя из первой, взяли две любые, выкинули два треугольника, дальше — очевидно

Спираль размера k+2 — это квадратик минус спираль размера k минус еще одна клетка. Спиралей куб, каждую пересчитываем из спирали меньшего порядка за O(1). Перебрали все, сказали ответ.

Да, объявили, на третьей странице:

Since nobody was able to solve it, the round will be unrated in Div-1.

Предлагаете stackoverflow? :)

Я, конечно, вопрос не изучал, но где еще?

multimap<> не поддерживает operator []. А также код будет некорректно работать в случае, если несколько задач имеют одинаковую популярность.

Я думаю, язык — лишь инструмент для выполнения задач. Мне кажется, хороший программист должен уметь быстро освоить новую технологию/язык на поверхностном уровне, знать на среднем уровне языков 5-10 и глубоко знать один-два — свою специализацию. Программирование — это не знание синтаксиса языка, а умение видеть чёткую задачу, решать её алгоритмически, продумывать архитектуру и структуру отдельных кусков так, чтобы всё работало быстро, с минимальным количеством ошибок и красиво смотрелось. В частности, я могу понять и написать что-то на Delphi, C/C++, Java, Python, JavaScript, HTML/TeX (если считать их языками программирования), PHP, C#.

Что же до меня, то для олимпиад я выбрал C++. Тут выбор вообще узок (чтобы было на всех соревнованиях и не приходилось мириться с TL) — Java/C++/Pascal. В Pascal слишком перегружен синтаксис и он не быстрее, чем код на C (без плюсов!). Java мне не нравится, потому что кажется черезчур избыточным и перегруженным языком да и к тому же иногда медленным (но это, думаю, скорее надо знать подводные камни и как оптимальнее писать — приходит с желанием/опытом). Плюс еще Java нет, например, на IOI. А C++ мне нравится почти всем. Отсутствие range check’ов и прочие “сюрпризы” я уже научился избегать и быстро ловить. Плюс есть STL (это было изначальным поводом перейти с Pascal), но, если его активно юзать, можно получить TL. Стараюсь заставлять себя подумать еще минут пять и придумать линейное решение вместо очевидного в три строчки с set/map — бывает полезно.

А, например, генераторы тестов, мелкие утилиты/парсеры и сайты я пишу на Python — он достаточно лаконичен, много где есть (в отличие, например, от Ruby, который я толком даже не изучал) и позволяет быстро написать что-то небольшое, не отвлекаясь на “обёртку”.