C++: задача о коммерческом калькуляторе
Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса». В этот раз опишу, как решил задачу из группы «легких», которая называется «Коммерческий калькулятор».
Три предыдущих поста из пяти всего в этой серии постов:
Формулировка задачи
Некая фирма выпустила программу-калькулятор. Калькулятор берет с пользователя комиссию 5 % с результата операции за каждую арифметическую операцию. Определить, за какую минимальную сумму денег можно произвести сложение на этом калькуляторе N заданных натуральных чисел. (Число N находится в диапазоне от 2 до 100’000, включая границы. Каждое из натуральных чисел находится в диапазоне от 1 до 10’000, включая границы.) За одну операцию можно сложить два числа.
Задача имеет смысл, так как при разном порядке сложения заданных чисел может выйти разная общая стоимость. Например, предположим, что задано четыре числа:
10, 11, 12, 13
Суммировать эти числа можно множеством разных способов. Я продемонстрирую только два способа из существующих для демонстрации факта, что разные способы суммирования могут иметь разную стоимость при расчете на упомянутом выше коммерческом калькуляторе.
При первом способе буду складывать числа по порядку слева направо:
| Операция | Стоимость | Общая стоимость |
|---|---|---|
| 10 + 11 = 21 | 21 × 0,05 = 1,05 | |
| 21 + 12 = 33 | 33 × 0,05 = 1,65 | |
| 33 + 13 = 46 | 46 × 0,05 = 2,30 | 5,00 |
При втором способе сначала суммирую числа попарно, затем суммирую результаты этих вычислений:
| Операция | Стоимость | Общая стоимость |
|---|---|---|
| 10 + 11 = 21 | 21 × 0,05 = 1,05 | |
| 12 + 13 = 25 | 25 × 0,05 = 1,25 | |
| 21 + 25 = 46 | 46 × 0,05 = 2,30 | 4,60 |
Как видим, получилась разная общая стоимость при выборе разного порядка суммирования.
Пример ввода данных и вывода результата:
4
10 11 12 13
4.60
Здесь в первой строке программа получила число N (в данном случае — 4). Во второй строке получаем натуральные числа для суммирования. В третьей строке программа вывела результат своей работы — минимальную стоимость суммирования заданных чисел.
По условиям задачи результат должен быть выведен с двумя знаками после десятичной точки. Ограничение по времени работы программы: 2 секунды. Ограничение по объему используемой памяти: 64 Мб.
Неудачный первый подход
Сначала я решил перебирать в цикле все возможные способы сложения заданных чисел. При этом я подсчитывал стоимость каждого способа и запоминал способ с минимальной стоимостью. Я решил, что все возможные операции между числами — это промежутки между ними (это не так). Я пронумеровал эти операции от 0 включительно до N - 1 не включительно.
В стандартной библиотеке C++ (заголовочный файл <algorithm>) есть интересный шаблон функции std::next_permutation, с помощью которого можно в цикле получить все перестановки в заданном наборе элементов. С помощью этого шаблона функции я получал перестановки операций и делал вычисления. Например, для приведенного выше примера получились такие расчеты:
| Порядок операций | Промежуточные результаты | Стоимости |
|---|---|---|
| 0 1 2 | 21 33 46 | 5,00 |
| 0 2 1 | 21 25 46 | 4,60 |
| 1 0 2 | 23 33 46 | 5,10 |
| 2 0 1 | 25 21 46 | 4,60 |
| 1 2 0 | 23 36 46 | 5,25 |
| 2 1 0 | 25 36 46 | 5,35 |
Я написал реализацию этой идеи и отправил ее на автоматическую проверку на веб-сервисе «CodeRun» от «Яндекса». Это моё решение успешно прошло только 3 теста из 25 имеющихся. На четвертом тесте я получил ошибку «Неправильный ответ».
При автоматической проверке для этой задачи открыты подробные результаты только первых двух тестов из 25 имеющихся. Остальные тесты являются закрытыми и подробные результаты для них посмотреть нельзя. Поэтому я не смог получить входные данные, на которых моя задача давала неверный результат.
Какое-то время я придумывал тесты сам, но моя программа их успешно проходила. Я обратился за помощью в Telegram-чат данного веб-сервиса: https://t.me/coderun_yandex. К моему удивлению, мне ответили довольно быстро, примерно минут через пятнадцать, хотя был час ночи. Так что общение в этом чате могу рекомендовать.
В итоге я понял, что вышеописанная идея с перестановками не работает, так как в ней не учтены способы сложения заданных чисел через одно число или из разных концов набора заданных чисел. Например, для следующих входных данных:
3
1 3 1
Этот мой вариант решения просчитывал два следующих способа сложения заданных чисел (слева направо и справа налево):
| Порядок операций | Промежуточные результаты | Стоимости |
|---|---|---|
| 0 1 | 4 5 | 0,45 |
| 1 0 | 4 5 | 0,45 |
Неучтенный этим решением способ сложения:
| Операция | Стоимость | Общая стоимость |
|---|---|---|
| 1 + 1 = 2 | 2 × 0,05 = 0,10 | |
| 2 + 3 = 5 | 5 × 0,05 = 0,25 | 0,35 |
Видно, что неучтенный способ суммирования имеет меньшую стоимость, а значит, этот мой вариант решения задачи дает в данном случае неверный результат.
Применение жадного алгоритма
Конечно, саму идею перебора всех возможных способов суммирования заданных чисел и выбора из них самого экономичного, думаю, можно довести до ума. Однако, пока я тестировал первый вариант решения, я заметил, что эту задачу можно решить, не перебирая все возможные способы суммирования заданных чисел. Я сразу переключился на эту идею, так как она сулила выигрыш по времени.
Почему одни способы суммирования заданных чисел экономичнее других? Я заметил, что в более дорогих способах суммирования в промежуточные суммы рано попадают большие слагаемые, которые своим наличием повышают стоимость операций. То есть чем позже большие слагаемые попадут в промежуточные операции, тем меньше окажется общая стоимость суммирования заданных чисел.
Таким образом, для нахождения самого экономичного способа суммирования заданных чисел нужно каждый раз выбирать наименьшие два слагаемых из оставшихся слагаемых и появившихся промежуточных результатов. Посмотрим, как это работает, на примере из формулировки задачи:
| Вектор слагаемых | Операция | Стоимость | Общая стоимость |
|---|---|---|---|
| 10 11 12 13 | 10 + 11 = 21 | 21 × 0,05 = 1,05 | |
| 21 12 13 | 12 + 13 = 25 | 25 × 0,05 = 1,25 | |
| 21 25 | 21 + 25 = 46 | 46 × 0,05 = 2,30 | 4,60 |
Как видно из этого расчета, у нас должна быть структура данных для хранения слагаемых (я выбрал в качестве такой структуры данных вектор). На каждом шаге решения в векторе находим два наименьших слагаемых и суммируем их, подсчитывая как стоимость очередной операции, так и общую стоимость суммирования заданных чисел.
После использования двух слагаемых из вектора слагаемых удаляем их, а в вектор вместо них добавляем промежуточный результат — их сумму. Далее процесс повторяется. Я реализовал это в цикле, количество шагов в котором всегда равно N - 1.
Подобные алгоритмы называют «жадными». Для данной задачи такое название даже имеет смысл: мы экономим деньги. Понятие «жадный алгоритм» (greedy algorithm) нередко встречается в книгах и разговорах программистов. На самом деле, это не конкретный один алгоритм, а принцип, на котором строится целый ряд разных алгоритмов. Наверное, можно сказать, что это целый класс алгоритмов.
Принцип жадного алгоритма заключается в том, что на каждом шаге решения задачи мы стараемся принять оптимальное на этом шаге подрешение, надеясь, что сумма всех этих оптимальных подрешений в итоге составит оптимальное решение всей задачи в целом.
В метках рассматриваемой задачи авторы оставили метки «greedy» и «heap». Если с первой всё понятно, она означает «жадный алгоритм», то со второй я до конца не разобрался. Менее вероятно, что речь идет про «алгоритм Хипа», касающийся генерации перестановок объектов (именно из-за этой отсылки я придумал первый вариант решения, который оказался неверным). Более вероятно, что речь идет про использование кучи (heap) в качестве структуры данных для хранения слагаемых. Я в своем решении использовал для этого вектор.
Борьба за время
Я довольно быстро написал реализацию варианта решения задачи по жадному алгоритму. Я отправил эту версию на автоматическую проверку на веб-сервисе «CodeRun» от «Яндекса». Эта версия успешно прошла 23 теста из 25 имеющихся. В итоге я получил сообщение «Превышен лимит времени».
Как и в прошлые разы, когда я сталкивался с этим сообщением, я изменил программу под загрузку входных данных из файла и добавил в программу класс Timer для замера времени (тут подробнее).
Для заполнения файла входными данными написал простую вспомогательную программу. Файл состоит из двух строк: в первой строке — число N (количество натуральных чисел для суммирования), во второй строке — 100’000 натуральных чисел, каждое в диапазоне от 1 до 10’000, включая границы. Эти натуральные числа сгенерировал генератором псевдослучайных чисел.
Замер времени для второго варианта решения задачи дал следующие результаты:
| N | Общая стоимость | Время работы, сек |
|---|---|---|
| 10’000 | 30’245’215.40 | 0.769242 |
| 20’000 | 65’462’184.25 | 3.11112 |
| 50’000 | -35’460’845.75 | 19.6113 |
| 100’000 | -46’439’679.95 | 78.4971 |
Кроме того, что уже на 20 тысячах натуральных чисел программа выходит за лимит в 2 секунды, выяснилось, что происходит переполнение переменной, в которой я накапливал сумму промежуточных операций для расчета общей стоимости операций, произведенных на коммерческом калькуляторе. Это видно по тому, что общая стоимость стала отрицательной.
Ошибку с переполнением переменной я исправил, изменив ее тип с int на double. После этого я снова сделал замер времени и получилось следующее:
| N | Общая стоимость | Время работы, сек |
|---|---|---|
| 10’000 | 30’245’215.40 | 0.784618 |
| 20’000 | 65’462’184.25 | 3.1544 |
| 50’000 | 179’287’519.05 | 20.0118 |
| 100’000 | 383’057’049.65 | 79.1939 |
При работе с вектором слагаемых я не удалял использованные слагаемые из вектора, а просто обнулял их. Мне казалось, что на удаление элементов вектора будет затрачено больше времени, чем на пропуск элементов с нулем. Но это суждение оказалось неправильным, я изменил программу так, чтобы использованные слагаемые удалялись из вектора, и это увеличило скорость программы. Вот какие получились результаты замеров:
| N | Общая стоимость | Время работы, сек |
|---|---|---|
| 10’000 | 30’245’215.40 | 0.367251 |
| 20’000 | 65’462’184.25 | 1.47021 |
| 50’000 | 179’287’519.05 | 9.3257 |
| 100’000 | 383’057’049.65 | 36.6857 |
Время работы программы уменьшилось чуть больше, чем в два раза. Но этого всё еще было недостаточно.
В конце концов, я понял, что моя программа тратит слишком много времени на поиск двух самых маленьких элементов в векторе слагаемых на каждом шаге цикла. Сначала я попробовал заменить этот поиск сортировкой вектора слагаемых по возрастанию. При этом два самых маленьких элемента оказываются первым и вторым элементами в векторе. Это можно считать альтернативным способом поиска самых маленьких элементов в векторе.
Применение сортировки на каждом шаге цикла не уменьшило, а даже несколько увеличило время работы программы. Тогда я решил, что сортировку следует выполнять только один раз — в начале программы, после получения слагаемых от пользователя, но до начала цикла с расчетом.
В самом же цикле оказалось, что сортировку применять очень неэффективно. На каждом шаге цикла в вектор слагаемых добавляется только одно новое число (очередной результат промежуточного суммирования), нет необходимости сортировать вектор ради вставки на место лишь одного числа. Для нахождения нужного места для нового числа в уже отсортированном ранее векторе я применил шаблон функции std::upper_bound из стандартной библиотеки C++ (заголовочный файл <algorithm>).
После этих изменений я протестировал получившуюся программу и получил следующие результаты замеров времени:
| N | Общая стоимость | Время работы, сек |
|---|---|---|
| 10’000 | 30’245’215.40 | 0.0069326 |
| 20’000 | 65’462’184.25 | 0.0285548 |
| 50’000 | 179’287’519.05 | 0.167846 |
| 100’000 | 383’057’049.65 | 0.772259 |
Как видно из этой таблички, эта версия программы успешно уложилась в лимит 2 секунд, хотя запас и не очень большой.
Моя реализация решения на C++
#include <iostream>
#include <vector> // для std::vector
#include <algorithm> // для std::sort, std::upper_bound
#include <iomanip> // для std::setprecision
int main()
{
// получить количество суммируемых натуральных чисел
int N{};
std::cin >> N;
// получить суммируемые натуральные числа (слагаемые)
std::vector<int> addends(N);
for (int n{}; n < N; n++)
std::cin >> addends[n];
// отсортировать слагаемые в векторе по возрастанию
std::sort(addends.begin(), addends.end());
// цикл совершаемых арифметических операций, их количество равно N - 1
double min_cost{}; // общая сумма стоимостей операций
for (int n_oper{}; n_oper < N - 1; n_oper++)
{
// сложить самые маленькие слагаемые, прибавить стоимость этой
// операции к общей сумме стоимостей операций
int sum_2mins{ addends[0] + addends[1] }; // промежуточный результат
min_cost += sum_2mins * 0.05;
// оба использованных слагаемых стереть
addends.erase(addends.begin());
addends.erase(addends.begin());
// вставить вместо них промежуточный результат, не нарушив сортировки
auto it = std::upper_bound(addends.begin(), addends.end(), sum_2mins);
addends.insert(it, sum_2mins);
}
// вывести минимальную сумму комиссии за работу калькулятора
std::cout << std::fixed << std::setprecision(2) << min_cost << '\n';
return 0;
}
Финальная версия программы получилась сильно меньше первых версий. Программа получилась довольно маленькая, но чтобы ее написать, мне пришлось потратить много времени и усилий. Эта версия программы успешно прошла автоматическую проверку на веб-сервисе «CodeRun» от «Яндекса».