Задача про обнаружение молекул с Международной олимпиады по информатике 2016 года

В августе этого года в Казани прошла Международная олимпиада по программированию для школьников — IOI 2016. Российская команда стала второй в общем зачете.

Один из серебряных медалистов, Денис Солонков из г. Мытищи, сделал разбор задачи «Обнаружение молекул», которая предлагалась участникам олимпиады.

Денис Солонков — многократный победитель Всероссийских олимпиад по программированию и Moscow CTF School, выпускник Школы программистов.

Условие

Петр работает в компании, которая создала прибор для обнаружения молекул. Каждая молекула имеет целый положительный вес. Прибор характеризуется интервалом обнаружения [l, u], где l и u целые положительные числа. Прибор может обнаружить множество молекул тогда и только тогда, когда это множество содержит такое подмножество, что суммарный вес молекул в нем принадлежит интервалу обнаружения прибора.

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

Детали реализации

Вам следует реализовать одну функцию (метод):

			int[] solve(int l, int u, int[] w)
		

• l и u: границы интервала обнаружения,
• w: веса молекул.
• Если требуемое подмножество существует, то функция должна вернуть массив индексов молекул, которые формируют любое такое подмножество. Если существует несколько правильных ответов, верните любой из них.
• Если требуемого подмножества не существует, то функция должна вернуть пустой массив.

Для языка программирования Си сигнатура функции немного отличается:

			int solve(int l, int u, int[] w, int n, int[] result)
		

• n: количество элементов в w (то есть число молекул),
• остальные параметры такие же, как описано выше.
• Вместо того, чтобы возвращать массив состоящий из m индексов (как указано выше), функция должна записать индексы в первые m ячеек массива result и затем вернуть m.
• Если требуемого подмножества не существует, то функция должна вернуть 0, не записывая ничего в массив result.

Ваша программа может записывать индексы в возвращаемый массив (или в массив result для языка Си) в любом порядке.

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

Примеры

Пример 1

			solve(15, 17, [6, 8, 8, 7])
		

В этом примере есть четыре молекулы с весами 6, 8, 8 и 7. Прибор может обнаружить подмножества молекул с суммарным весом от 15 до 17 включительно. Обратите внимание, что 17 − 15 ≥ 8 − 6. Суммарный вес молекул 1 и 3 равен w1 + w3 = 8 + 7 = 15, таким образом функция может вернуть [1, 3]. Другие возможные правильные ответы: [1, 2] (w1 + w3 = 8 + 8 = 16) и [2, 3] (w1 + w3 = 8 + 7 = 15).

Пример 2

			solve(14, 15, [5, 5, 6, 6])
		

В этом примере есть четыре молекулы с весами 5, 5, 6 и 6. Требуется найти подмножество с суммарным весом от 14 до 15 включительно. Опять же, обратите внимание, что 15 − 14 ≥ 6 − 5. Для данного примера не существует подмножества молекул с суммарным весом от 14 до 15, соответственно функция должна вернуть пустой массив.

Пример 3

			solve(10, 20, [15, 17, 16, 18])
		

В этом примере есть четыре молекулы с весами 15, 17, 16 и 18. Требуется найти подмножество с суммарным весом от 10 до 20 включительно. Вновь, обратите внимание, что 20 − 10 ≥ 18 − 15. Любое подмножество, состоящее из одного элемента, имеет вес от 10 до 20, соответственно возможные правильные ответы это [0], [1], [2] и [3].

Система оценивания

1. (9 баллов): 1 ≤ n ≤ 100, 1 ≤ wi ≤ 100, 1 ≤ u, l ≤ 1000, все wi равны.
2. (10 баллов): 1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1000, и max(w0 ,…, wn−1) − min(w0,…, wn−1 ) ≤ 1.
3. (12 баллов): 1 ≤ n ≤ 100 и 1 ≤ wi,u , l ≤ 1000.
4. (15 баллов): 1 ≤ n ≤ 10 000 и 1 ≤ wi, u, l ≤ 10 000.
5. (23 балла): 1 ≤ n ≤ 10 000 и 1 ≤ wi, u, l ≤ 500 000.
6. (31 балл): 1 ≤ n ≤ 200000 и 1 ≤ wi, u, l < 231.

Пример проверяющего модуля

Проверяющий модуль получает данные в следующем формате:

• Строка 1: целые числа n, l, u.
• Строка 2: n целых чисел: w0,…, wn−1.

Решение от Дениса

Задача уже неплохо формализована. Нам нужно выбрать подпоследовательность чисел из массива w длины n, так, чтобы их сумма лежала в отрезке [l, u]. Также, присутствует странное условие:
u − l ≥ wmax − wmin (1)

Оно явно играет роль в решении задачи, иначе его бы просто не было. Попытаемся понять, что оно нам дает.

Пусть мы выбрали подпоследовательность элементов с суммой = S и S < l. В таком случае, если мы заменим один из элементов подпоследовательности на какой-то другой, не выбранный нами, то новая сумма S’ ≤ u. Случай, увеличивающий сумму на максимально возможное число, это замена минимального на максимальный элемент, а согласно условию u − l wmax ≥ wmin.

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

1. Определить L — количество элементов в правильном ответе, или сказать, что его не существует.
2. Найти L элементов, сумма которых лежит в [l, u]

Сначала разберемся во вторым пунктом. Пусть мы знаем, что ответ существует и в нем содержится L элементов. Возьмем первые L элементов отсортированного w. Их сумма точно ≤ u, так как мы условились, что ответ существует. Теперь выполним следующий алгоритм.

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

Заметим, что благодаря (1) мы никогда не пересечем верхнюю границу. Почему этот алгоритм точно найдет ответ? Предположим обратное.

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

Подобный алгоритм можно быстро реализовать, используя встроенную в С++ реализацию сбалансированного дерева поиска: set. Количество итераций алгоритма в худшем случае: n, асимптотика подобного решения будет O(n log n).

Вернемся к первому этапу решения нашей задачи, а именно в поиске подходящего L. Мы можем просто проверить каждый из них и получить асимптотику O(n2 log n), но это будет слишком долго работать.

Давайте найдем такую длину i, что сумма первых i элементов больше u. Если такой длины не существует, то будем полагать, что i = n + 1 Из всех таких возьмем минимальную. Я утверждаю, что если правильный ответ существует, то он будет содержать i − 1 элемент. Конечно, могут существовать и другие варианты ответа, но один из них будет содержать в себе такое количество элементов. Докажем это утверждение.

Пусть L = i − 1, или L = n, если i не существует. Сумма первых L элементов ≤ u, так как L < i. Запустим описанный выше алгоритм поиска подпоследовательности. Если он найдет ответ, то наше утверждение верно. В ином случае, сумма последних L элементов < l. Тогда ответа также не существует для любой длины, меньшей чем L. Просто потому что было взято L максимальных, так что любое количество меньше тоже будет меньше l. Ответа также не существует для всех длин больше L, так как сумма первых i элементов больше, чем u. Значит, ответа вовсе не существует.

Итого, мы можем найти необходимую длину за O(n), и найти ответ по длине за O(n log n). Значит, время работы всего алгоритма будет O(n log n), что спокойно набирает 100 баллов.

Исходный код решения

			#include <algorithm>
#include <vector>
#include <set>

#include "molecules.h" //Including grader file

using ll = long long; //A little alias to save time.

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
	int n = w.size();
	vector<pair<int, int> > weight(n);
	for (int i = 0; i < n; i++) {
		weight[i] = { w[i], i }; //Storing initial index for the output.
	}
	sort(weight.begin(), weight.end());
	ll cur_sum = 0;
	int bad_i;
	for (bad_i = 0; bad_i < n; bad_i++) { //Locating first bad length
		cur_sum += weight[bad_i].first;
		if (cur_sum > u)
			break;
	}
	if (bad_i == 0) //no solution
	{
		return vector<int>();
	}
	set<pair<int, int> > picked, remain;
	ll curpicked = 0;
	for (int i = 0; i < bad_i; i++) { 
		picked.insert(weight[i]);
		curpicked += weight[i].first;
	}
	for (int i = bad_i; i < n; i++) {
		remain.insert(weight[i]);
	}
	while (curpicked < l && !remain.empty()) {
		if (picked.begin()->first >= remain.rbegin()->first) //Nothing left to swap
			break;
		//Swap the lowest and the highest elements.
		curpicked += remain.rbegin()->first - picked.begin()->first;
		auto el1 = *picked.begin();
		auto el2 = *remain.rbegin();
		picked.erase(el1);
		picked.insert(el2);
		remain.erase(el2);
	}
	if (curpicked < l){ //no solution 
		return vector<int>();
	}
	vector<int> answer;
	for (auto el : picked)
		answer.push_back(el.second);
	return answer;
}
		

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

В этом году ШП открывает отделение в Физтехпарке — новом IT-парке рядом с МФТИ. Программа обучения усложненная, такая же, как в отделении при Яндексе, включающая в себя изучение высокоуровневых и низкоуровневых языков, дискретную математику, алгоритмику, структуры данных, сети, ОС и прочее.

Набор на 2016/17 учебный год проводится для школьников 6–10 классов по результатам экзамена, который состоится 8 октября 2016 в 14:00.

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