Два года назад я вкидывал в сообщество идею о библиотеке, которая умеет генерировать разные клёвые тесты. Я долго крутил идею в голове и наконец попытался что-то написать. Реализовано пока далеко не всё из того, что хочется, но то, что уже есть, я активно использую в своих задачах.

Итак, встречайте: https://github.com/ifsmirnov/jngen. Саму библиотеку (точнее, единственный хедер jngen.h) можно скачать тут.

Jngen умеет работать с массивами, деревьями и графами, а также генерировать немного строк и геометрии. Есть парсер опций командной строки и клёвая SVG-рисовалка. Можно делать, например, так.

cout << Array::id(10).shuffled().add1() << endl; // permutation of elements from 1 to 10

cout << Tree::random(100000, 20) << endl; // "long" tree with elongation 20

pair<string, string> test = rnds.antiHash({{mod1, base1}, {mod2, base2}}, "a-z", 10000); // should be self-describing :)

cout << rndg.convexPolygon(1000, 1e9) << endl;

cout << Graph::random(100000, 200000).connected() << endl;

cout << rndm.randomPrime(1e18, 1e18 - 10000000) << endl;

Практически по всему коду есть документация, есть парочка примеров.

Начать работать очень просто: если от testlib.h вы используете в генераторах только registerGen и rnd.next, то можете заменить #include "testlib.h" на #include "jngen.h" и не заметить разницы. Компилируется чуть дольше, но это обходится, и в итоге получается даже быстрее, чем с testlib.

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

Пока что в библиотеке гораздо больше "базовых" вещей и примитивов, чем "контента" – собственно стандартных тестов к задачам. Мы работаем над этим: в ближайших планах – добавление "наборов тестов", чтобы к своей задаче на, допустим, LCA-like запросы, вы могли сделать разумный тестсет буквально за несколько строк.

Кстати, большое спасибо zemen, Endagorion и Errichto за советы и обсуждения, Endagorion, GlebsHP и CherryTree за возможность потырить код посмотреть на существующие библиотеки и MikeMirzayanov за testlib, из исходников которого на первых порах зачерпнулось немало вдохновения.

Several months ago I've seen a comment on Codeforces which explained a method of finding a tangent from a point to a polygon. This problem is rather hard and if you try the first implementation which comes to your mind, it probably will not work. That comment explained a tricky binary search where you should store not two endpoints of a segment, but three, and which was easy to implement.

However, now I cannot neither recall the idea nor find the comment itself. Could anyone help me with either?

После начала обсуждения здесь я решил вынести его в отдельный тред.

Есть много разных тестирующих систем, и во всех свои политики файлового ввода-вывода. Я встречал много разных: stdin+stdout, a.in/txt, input.txt, $problem.in/txt, где-то даже a.in+stdout. В последнее время, как мне показалось, хорошей практикой считается допускать стандартные потоки, и файловый ввод-вывод. Но предположим, что такого решения нет, и остановимся на первых двух: только файлы или только стандартный ввод-вывод. Что из этого, по-вашему, должна поддерживать тестирующая система?

Я приведу свои аргументы в пользу stdin/stdout.

1. Человек может написать минимальный работающий кусок кода, начав с пустого листа, проверить его работу из консоли и заслать в систему, потратив минимум времени. Есть разные кейсы. Топкодер, где код пишется в арене/на вебсайте; туда же сейчас присоденяются HackerRank, CSAcademy и т.д. Это и мой сегодняшний пример с засыланием предподсчёта, когда основное решение выводит инициализацию массива в отдельный файл, в который я потом в редакторе добавляю условные int main() и cout << a[n] << endl. Это задача А на Codeforces, которую хочется сдать до того, как ты написал шаблон, если шаблона по какой-то причине нет заранее.

2. В файлах есть много разных стилей наименования, в которых легко опечататься. Файлы можно забыть. Да, это проверка на внимательность. Конечно, участник высокого уровня должен уметь и файлы замечать, и приписки в Input Format'е о том, что количество запросов второго типа не превосходит 5, и многое другое подобное. Но сейчас считается хорошим тоном от этого уходить в сторону собственно решения задач. Десять лет назад контест от Андрея Лопатина, где в файлах можно было встретить подколки вида "kitten.in / k1tten.out", был уместен и свеж. Десять лет назад на финалах просили вывести число ровно с тремя знаками после запятой, ни больше ни меньше, и без ошибок перебить с печатных условий английскую фразу в десяток слов. Сейчас не десять лет назад.

3. Ответ на контраргумент "input.txt/output.txt строго удобнее": не надо за участника решать, как участнику удобнее тестировать локально! Я использую схему "a.in + stdout", например. Каждая задача в отдельной папке, название файла соответствует названию бинарника с задачей, вывод всегда консольный, потому что файловый бывает нужен крайне редко, а консольный удобнее смотреть. Открытие файла завёрнуто в ifdef, потому что я его сделал под свои нужды для удобства тестирования, и раз уж я хочу написать непортабельный код, то я сам должен позаботиться о том, чтобы он нигде больше не компилировался. Почему вместо этого я должен заворачивать в ifdef строки, нужные для взаимодействия с системой?

Да начнётся холивар!

It is known (well, as long as Tarjan's proof is correct, and it is believed to be) that DSU with path compression and rank heuristics works in O(α(n)), where α(n) is an inverse Ackermann function. However, there is a rumor in the community that if you do not use the rank heuristic than the DSU runs as fast, if not faster. For years it was a controversial topic. I remember some holywars on CF with ones arguing for a random heuristic and others claiming they have a counter-test where DSU runs in independently of rand() calls.

Recently I was looking through the proceedings of SODA (a conference on Computer Science) and found a paper by Tarjan et al. The abstract states:

Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

This paper is relatively old (2014), though I haven't yet heard of it and decided to share with you.

A whole paper can be found here.

Topcoder Google calendar available from here is awesome. It includes all SRMs, marathon matches and everything you'll possibly ever need.

But I don't need these long marathon matches which occupy my Google calendar and mark the whole week as busy. I'd like to have a calendar where only SRMs and TCO events are included. Maybe, the beginning of new marathon match would be helpful too.

Do you know any of such calendars? Maybe it is possible to tweak the standard one? Or should I make this thing myself?

I'm now participating in my first TC Marathon Match. I decided to run my solution in an infinite loop and stop when TL is almost reached. But it turned out that %%clock()%% function (C++) doesn't return correct time in the system. I printed total time elapsed after each iteration, On some testcases the last entry printed was 210 ms, however, the solution got a TLE verdict (with 10 seconds time limit!). On others it managed to finish on time, but the time printed by tester was significantly larger than what my program printed to the stderr.

Is it possible to do time-based pruning on TC marathons? Which functions should I use for it? I've heard about some clocks from std::chrono, but a limit of one test submission per hour isn't really convenient to test it all.

Oh. And as you're already here, I've got one more question. Where can I find information about how often I can make a judged submission? I googled a bit but found contradictory information (72 hours, 4 hours, some else...) In the ongoing match (TCO Marathon R3) I could make several submissions in about a half an hour, and the next day I had to wait for an hour until the next submission.

I use a web form for submitting, if it matters.

Thank you for helping me climbing the learning curve :)

Take a look at this snippet.

#include <bits/stdc++.h>
using namespace std;

void f(int x, int y) {
    if (x > y) swap(x, y);
    printf("%d %d\n", x, y);
}

void caller1(int i) {
    f(i-1, i);
}

void caller2(int i) {
    f(i+1, i);
}

int main() {
    caller1(1);
    caller2(1);
}

Have you noticed something strange? Or maybe redundant? Neither did I. But g++ did:

$ g++-4.8 -Wall -O2 a.cpp 
a.cpp: In function ‘void caller1(int)’:
a.cpp:5:5: warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false [-Wstrict-overflow]
     if (x > y) swap(x, y);
     ^

Wait, what the hell? This if is used not only in caller1 but also in caller2, and in both cases the flow continues to the different branch. It seems that the optimizer examines only caller1 and doesn't even think that there could be some other users of that "redundant" line of code.

What is more strange, this error does not reproduce if only caller2 is present (in that case if condition always evaluates to true).

Hopefully, optimizer doesn't completely cut out the body of the conditional and the code works as expected albeit the warning is shown.

The bug reproduces with all g++ versions I have up to 5.0 and doesn't reproduce with clang of any version.

Сегодня я зашёл в полигон и обнаружил, что в задачу, которую я давал на CF в 2013 году, кто-то внёс изменения. Изменения в целом ерундовые: заменить cout на printf, добавить using namespace std в генератор, какие-то мелочи в problem.xml. Все эти изменения были сделаны под логином administrator.

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

Совсем недавно страницы CF у меня в браузере начали что-то подгружать в фоновом режиме каждые несколько секунд. Фавикон на долю секунды меняется на иконку загрузки, после этого всё приходит на свои места, страница не перезагружается, контент не меняется.

Дев-консоль показала безуспешные (404 Not Found) попытки постучаться по этим адресам:

http://pubsub2.codeforces.com/sub/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?_=1466418677884&streamid=0&tag=&time=&eventid=

ws://pubsub2.codeforces.com/ws/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?_=1466418679146&tag=&time=&eventid=

http://pubsub2.codeforces.com/ev/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?_=1466418683048&tag=&time=&eventid=

WTF? Дёргающиеся иконки в списке вкладок сильно отвлекают, пришлось временно избавиться от привычки держать окно CF открытым в фоне.

Несколько месяцев назад мы (я, Иван ifsmirnov Смирнов, Костя zemen Семенов и Артём Arterm Жук, а также Дима Skird Иващенко в качестве прошлого участника) решили, что если возьмём золото на финале ACM ICPC, то выкатим в продакшн проект, над которым в поте лица трудились уже больше года и продолжаем работать до сих пор. В те времена это казалось невероятным.

Финал 2016 года преподнёс нам приятный сюрприз. Хочешь не хочешь, а обещание надо выполнять. Встречайте, Moscow IPT Jinotega 3000 выплывает из стадии бета-тестирования!

Welcome!

Disclaimer: содержит нецензурную лексику, неуместные фотографии и шутки от Джинотеги. Просьба воздержаться от просмотра несовершеннолетним, а также всем остальным.

667A - Проливной дождь

Чтобы узнать, сколько воды вы потребляете за секунду, вы должны разделить выпитый в секунду объём v на площадь дна, равную . Далее следует сравнить эту величину с e. Если ваша скорость выше, то вы опустошите кружку через секунд. Иначе вы не сможете её опустошить.

667B - Герб антикубизму

Для того, чтобы из набора длин можно было сложить выпуклый многоугольник, должно выполняться обобщённое неравенство треугольника: длина наибольшей стороны должна быть меньше суммы длин оставшихся сторон. Раз из текущего набора длин сложить выпуклый многоугольник невозможно, есть сторона, длина которой не меньше суммы остальных. Пусть она больше этой суммы на k; тогда достаточно добавить стержень длины k + 1. Кроме того, ясно, что никакой меньшей длиной обойтись нельзя. Таким образом, ответ на задачу — .

666A - Ребляндская лингвистика / 667C - Ребляндская лингвистика

Решение — динамическое программирование. Мы можем взять любой достаточно большой корень. Поэтому разворачиваем строку и поддерживаем dp_2, 3[n] — можем ли мы разбить префикс длины n на строки длины 2 и 3 так, чтобы последней шла строка определённой длины. Пересчёт: . Аналогично . Если dp_k[n] = 1, добавляем соответствующую строку в множество ответов.

666B - Мировое турне / 667D - Мировое турне

Дан ориентированный граф, нужно найти такие 4 различные вершины a, b, c, d, что каждая последующая достижима из предыдущей и сумма кратчайших путей между соседними вершинами наибольшая. Для решения данной задачи для каждой вершины с помощью обхода в ширину посчитаем расстояния до всех остальных вершин по прямым и обратным рёбрам и сохраним три самые отдалённые вершины. После этого переберём вершины b, c, а a и d будем искать только среди трёх самых дальних по обратным рёбрам для b и трёх самых дальних по прямым рёбрам для c. Этого будет достаточно, потому что если мы зафиксировали вершины a и b, то если у нас d не из трёх самых дальних для c, мы точно сможем заменить её на одну из них и улучшить ответ.

666C - Кодовое слово

Первое полезное наблюдение: для нас не имеет никакого значения сама строка s, а лишь её длина. В любой последовательности длины n, которая содержит заранее заданную подпоследовательность s, можно выделить её лексикографически минимальное вхождение. Оно особенно тем, что между символами a_k и a_k + 1 не может встретиться символ a_k + 1, иначе вхождение не будет лексикографически минимальным. Обратно, если есть вхождение с таким свойством, оно будет лексикографически минимальным.

Исходя из этого, можно посчитать число строк, содержащих данную как подпоследовательность. Сначала мы выберем позиции лекс. мин. вхождения способами. Далее в любом из |s| отрезков мы можем использовать только q - 1 символов, где q — размер алфавита, а в последнем отрезке можем взять любое слово. Иначе говоря, свободные символы слева от последнего вхождения мы выбираем из алфавита размера q - 1, а справа — размера q.

Перебирая позицию последнего символа в лекс. мин. вхождении, получаем, что таких строк . Таким образом, если у нас фиксировано |s|, мы легко можем посчитать ответ для всех нужных n. Более того, отсюда можно вывести более простую рекуррентную формулу: пусть нам известен ответ d_n для длины n. Тогда . Действительно, либо последний символ не совпадёт с последней позицией в лекс. мин. вхождении и мы пойдём по первому слагаемому, либо совпадёт, тогда мы сможем явно посчитать число таких надпоследовательностей, которое равно числу во втором слагаемом.

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

666D - Цепная реакция / 667E - Цепная реакция

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

Переберём длину стороны квадрата d, положение нижней левой точки (x, y) (среди чего перебирать, будет видно позже). Кроме того, переберём перестановку точек так, чтобы первая перешла в нижнюю левую точку квадрата, вторая — в нижнюю правую и т.д. После этого несложно проверить, действительно ли из такой перестановки точек можно получить такой квадрат, и если да, посчитать максимальное перемещение. Остаётся вопрос, где перебирать d, x и y.

Сначала определимся с d. Несложно заметить, что всегда найдутся две точки квадрата, двигающиеся по параллельным, но не совпадающим прямым. В таком случае строна квадрата — это расстояние между прямыми, то есть одно из чисел |x_i - x_j| или |y_i - y_j|. Это и есть множество, в котором будет перебираться d.

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

1. Есть две точки, которые двигаются по перпендикулярным прямым. Значит, в точке пересечения этих прямых есть вершина квадрата. Нижняя левая точка в каждой координате либо совпадает с ней, либо отличается на d. Точка пересечения прямых имеет координаты (x_i, y_j), значит, нижняя левая — (x_i ± d, y_j ± d) для некоторых i и j. Добавим все координаты x_i, x_i + d, x_i - d в перебираемое множество.
2. Все точки двигаются по параллельным прямым. Будем считать, что по горизонтальным; случай вертикальных рассматривается аналогично. Снова переберём перестановку и сдвинем каждую точку так, чтобы после своего движения она совпала с нижней левой вершиной квадрата. Вторую точку надо сдвинуть на вектор ( - d, 0), третью — на (0,  - d), четвёртую — на ( - d,  - d). После этого четыре точки должны оказаться на одной прямой. Теперь задачу можно переформулировать так: есть четыре точки на прямой, нужно сдвинуть их в одну точку так, чтобы минимизировать максимальный сдвиг. Несложно видеть, что сдвигать нужно в середину полученного отрезка, то есть точку (maxX - minX) / 2 (из-за требования целочисленности ответа можно округлять в любую сторону). Перебрав все перестановки, получим ещё один набор, в котором надо перебирать координату первой точки требуемого квадрата.

За сколько это работает? Обозначим размеры соответствующих множеств за D и X. Тогда D = C₄²·2 = 12. Теперь для каждого d в первом случае генерируется 4·3 = 12 координат, во втором — не более чем 4! = 24. Итого X ≤ 12·(12 + 24) = 432. Основная часть решения работает за ; однако невозможно построить тест, на котором реализуются всевозможные конфигурации с движением по параллельным прямым, поэтому на самом деле перебирать придётся гораздо меньше.

666E - Судебная экспертиза

Дана строка s, а также m строк t_i. Поступают запросы вида ``посчитать, в какой из строк с номерами из отрезка [l;r] подстрока s[a, b] встречается чаще всего''. Вообще говоря, предполагалось, что задача будет требовать online-решения, но в итоге от этой идеи было решено отказаться, поэтому её можно чисто технически комбинацией известных алгоритмов. Не будем разбирать подробно offline-решение, а сразу перейдём к online.

Построим дерево отрезков над текстами. В каждой вершине дерева построим автомат для конкатенации через разделители текстов, которые имеют номер из соответствующего вершине подотрезка и для каждого состояния в таком автомате найдём номер текста из подотрезка, в котором оно встречается наибольшее число раз, а также количество вхождений в эту позицию. Кроме того, для каждого состояния найдём состояния в детях вершины дерева отрезков, которые содержат его (если такие вообще есть). Очевидно, что все подстроки из одного состояния окажутся в одном состоянии в левой половине. В правой же половине, вообще говоря, строки, которые пересекали середину отрезка текстов могут уйти в другое состояние или исчезнуть, но это не беда. Чтобы справиться с этой проблемой, достаточно просто искать не состояние для строк, которые находятся в этом же состоянии, а состояние для строк, в которых не встречается разделитель и которые лежат в этом состоянии, так как все строки, пересекающие середину имеют вид X#Y и не интересны нам. Таким образом, для ответа на запрос, мы можем найти в корневой вершине состояние, соответствующее требуемой подстроке, а дальше спускаться по дереву, переходя в уже посчитанные переходы для состояний.

Закончился очередной этап кубка.

Как решать I нормально? Сначала думали, что это просто сесть и написать, потом оказалось, что следить за текущими картами в колоде довольно нетривиально.

Consider a well-known problem: given a static array of size n, answer m queries of kind "how many numbers on [l, r] have value less than x". The standard solution is to build a segment tree where in every node we store a sorted vector. To answer a query we do a binary search in every corresponding node, achieving per query time complexity.

There is a method to reduce time complexity to per query, called fractional cascading. Instead of doing binary search in each node we do it only in the root, and then "push" its result to children in O(1).

For years I thought that the second approach is blazingly faster than the first one. And today I've made a test. I implemented both approaches in a pretty straightforward way and tested them on a random data. The results were quite surprising.

Fractional cascading: 760 ms

Top-down implementation: 670 ms

Bottom-up implementation: 520 ms

The first one is , others are ! Time is averaged over several consecutive runs. Test data is generated randomly with n = 100000, m = 200000.

Why doesn't fractional cascading give any improvements? Am I implementing it in an improper way? Anyway, this might be worth taking a look.

Многие ACM-щики успешно закончили универ по профильному направлению. И, естественно, защитили диплом. Наверняка некоторые занимались темой, которая может быть интересна сообществу, смежной со спортивным программированием. Широко известны работы Burunduk1 про Dynamic 2-connectivity и droptable про дерево палиндромов. Но это наверняка не всё. Поделитесь?

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

sscanf(argv[1], "%d", &maxn);
n = rnd.next(2, maxn);
printf("%d\n", n);
for (int i = 2; i <= n; ++i) {
    printf("%d %d\n", rnd.next(1, i-1), i);
}

Если я хочу пошаффлить рёбра, геморроя чуть больше, если хочу добавить веса, надо добавлять ещё параметр командной строки... С массивами, графами, строками и т.д. не сильно проще. Не сложно, но рутина. testlib, не считая генерации случайных чисел разных типов на интервале, может только генерировать строку по паттерну. А хочется уметь писать как-то так:

int maxn, maxc;
parseCmdParams(maxn, maxc);
cout << Tree().random(1, maxn).addWeight(1, maxc).shuffleEdges();

Соответственно, два вопроса к сообществу. Знаете ли вы что-нибудь подобное, работающее и удобное? И какие у вас самих были бы требования к такой системе? Я начал делать достаточно универсальную библиотеку для создания генераторов, и какие-то разумные советы (а через некоторое время и фидбек) сильно увеличат вероятность того, что штука будет закончена и ей можно будет адекватно и удобно пользоваться.

Вот чего хочется достичь в качестве proof-of-concept:

• возможность писать идентичный код на C++ (11) и Python, выдающий одинаковые тесты
• гибкая генерация чего бы то ни было через chaining (как в сниппете)
• генерация стандартных структур (простое дерево, простая матрица, простой граф) за минимум кода
• поддержка тесткейсов и файлов с тестами

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

До финала VK Cup остались считаные дни, а я как финалист всё ещё не знаю, чем и когда предполагается заниматься. Например, даже точную дату контеста я могу только попробовать угадать, не говоря уж о всяких активностях вроде экскурсий/игровых раундов/чего-нибудь ещё, что могли придумать организаторы. А хочется планировать своё время в городе.

Расписание правда ещё не выложили или я просто не могу его найти?

TL;DR: можно ли одновременно поддерживать эйлеровым обходом LCA, сумму в поддереве и переподвешивание?

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

Закончился очередной этап опенкапа, давайте обсуждать задачи.

Интересует, как решать D.

Дебагая хеш-таблицу, я вчера наткнулся на очередное забавное проявление оптимизатора g++. Вот минимальный код, на котором я смог его воспроизвести.

#include <iostream>

int main() {
    for (int i = 0; i < 4; ++i) {
        std::cout << i*1000000000 << std::endl;
    }   
}

Казалось бы, вывод предсказуем. Более того, без оптимизации это действительно так. Однако...

ifsmirnov@carbon:./tmp$ g++-4.8 a.cpp -O2 && ./a.out  | head -n 10
0
1000000000
2000000000
-1294967296
-294967296
705032704
1705032704
-1589934592
-589934592
410065408

И так бесконечно долго.

Логическая цепочка оптимизатора понятна: по стандарту переполнение инта при умножении -- это UB, значит, можно делать всё, что угодно. Но во что превратилось условие остановки цикла, я так и не понял.

У меня это воспроизводится на g++-4.8 c -O2 и выше. На 4.4, 4.6 и 4.7, clang-3.4 выводятся четыре числа даже с любыми уровнями оптимизации.

Интересно, что по этому поводу думает MinGW, а также почему все-таки происходит этот эффект.

UPD: если заменить cout на printf, «баг» не вылезает.

UPD2: продолжаем развлекаться. Если вместо вывода делать push_back в вектор, баг вылезает. Если же вместо этого написать свой «вектор», то можно поймать нетривиальный warning.

#include <cstdlib>

struct MyVector {
    int *a;
    int cap;
    int n;
    MyVector() {
        cap = 1;
        n = 0;
        a = (int*)malloc(sizeof(int) * cap);
    }   
    void push_back(int x) {
        if (n == cap) {
            cap *= 2;
            a = (int*)realloc((void*)a, sizeof(int) * cap);
        }   
        a[n++] = x;
    }   
};

int main() {
    MyVector a;
    for (int i = 0; i < 4; ++i) {
        a.push_back(i * 1000000000);
    }   
}

b.cpp: In function ‘int main()’:
b.cpp:24:35: warning: iteration 2u invokes undefined behavior [-Waggressive-loop-optimizations]
         a.push_back(i * 1000000000);
                                   ^
b.cpp:23:5: note: containing loop
     for (int i = 0; i < 4; ++i) {
     ^

Очередной, 580-тый, матч-из-одного-раунда пройдет в субботу в 20:00 MSK (12:00 EDT).

Здравствуй, сообщество Codeforces!

Очередной раунд Codeforces #121 для вас сделали студенты ФИВТ МФТИ Александр Тимин (AlTimin) и Иван Смирнов (ifsmirnov). В своем первом раунде мы предложим вам хорошо провести время в старой доброй Берляндии: провести митинг, разогнать митинг, разобраться с главными берляндскими проблемами (обеими!) и многое другое.

За неоценимую помощь в подготовке контеста хочется сказать огромное спасибо Gerald. Он же является автором одной из задач. Кроме того, мы выражаем благодарность Delinur за перевод условий на английский язык, Aksenov239 за вычитку условий и MikeMirzayanov за возможность провести контест на замечательной платформе Codeforces.

Традиционно, раунд пройдет в обоих дивизионах на частично пересекающемся наборе задач. Информация о разбалловке будет опубликована позже.

Мы желаем вам успехов и надеемся, что раунд вам понравится!

Разбор

UPD1: Разбалловка в обоих дивизионах стандартная, 500-1000-1500-2000-2500.

UPD2: Авторы контеста приносят участникам свои извинения за неточности в условии задачи B div 1 (D div 2). Так как проблема с условием была решена достаточно быстро, а неправильное понимание задачи не проходило претесты, раунд объявляется рейтинговым.

Навеяно 163B - Лемминги.

Предположим, загадано рациональное число, представленное в виде несократимой дроби 0 ≤ p / q ≤ 1. Пусть знаменатель не превосходит Q (в задаче, да и обычно на практике — 10⁹). Есть способ по данному рациональному числу узнавать, больше оно данного, меньше или равно (функция f (p, q) → {1, 0,  - 1}). Задача: с помощью вызовов этой функции отгадать загаданное число. При этом функции нельзя передавать числа со знаменателем  > Q. Вещественной арифметикой пользоваться нельзя.

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