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

Задачи, результаты.

Спасибо Улану Дегенбаеву и Андрею Мохову за интересный контест.

Problem A. Absolute Equation

Ключевая идея решения: весь интервал от -10^8 до 10^8 можно разбить на подинтервалы, внутри которых каждое из подвыражений уравнения (x, |x| + a, x + b) имеет постоянный знак и не равно нулю (x’ы, при которых какое-то из подвыражений равно 0 будут являться границами этих интервалов). Точки, являющихся границами интервалов это:

  1. -10^8, 0, 10^8;
  2. a, -a, при a < 0;
  3. -b.

Теперь, если взять интервал (l, r), то знак каждого из выражений строго определяется любым x’ом из этого интервала. Получив знак каждого выражения, избавляемся от модуля и решаем получившееся линейное уравнение, не забывая проверить, что ответ входит в нужный интервал.

Есть еще 2 частных случая:

  1. x’ы, равные границам интервалов надо проверить отдельно;
  2. при некоторых обстоятельствах интервал может целиком удовлетворять уравнению. Это легко проверить, подставив 2 разных x из этого интервала в уравнение. Если оба подошли, значит подойдет и весь интервал.

Problem B. Box packing

Очевидная интуитивная догадка:

  1. положим все коробки в приоритетную очередь (приоритет – время прибытия, чем оно более раннее, тем приоритет выше);
  2. возьмем две коробки с наиболее ранним временем прибытия, удалим их из очереди и упакуем, получив новую коробку с временем прибытия max(t1, t2) + k, которую положим обратно в очередь;
  3. повторяем пока в очереди не останется одна коробка, время ее прибытия и будет являтся ответом.

Problem C. Check Solution

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

Problem D. Deficient Memory

У нас мало памяти, но много времени. Посчитаем сначала количество чисел от 0 до 250000 – 1, затем от 250000 до 500000 – 1, от 500000 до 750000 – 1 и от 750000 до 1000000, встречающихся в обоих последовательностях. Это можно сделать, следующим образом:

  1. генерируем первую последовательность и каждое число (если оно лежит в нужном интервале) отмечаем в битовом массиве;
  2. генерируем вторую последовательность и если встречается число, отмеченное в битовом массиве, то увеличиваем результат на единицу, а из битового массива снимаем отметку, соответствующую этому числу.

Легко заметить, что для данного решения требуется не более 250000 / 8 ~32K памяти.

Problem E. Extreme point

Очевидно, что сумму расстояний можно минимизировать по каждой в отдельности. Таким образом задача распадается на 3 одинаковые задачи в одномерном пространстве. Для решения одномерного случая можно использовать, например, следующий алгоритм:

  1. посчитаем сумму расстояний (s) до самой левой точки;
  2. пойдем по всем координатам от самой левой до самой правой точки, поддерживая количество точек не правее текущей координаты (l). При этом, когда переходим от координаты x к x + 1, то пересчитываем s по следующей формуле: s = s – (n – l) + l. Таким образом для каждой координаты мы будем знать сумму расстояний от нее до всех точек, и попутно выбирая минимум получим ответ.