Hacker News Digest

Сложные LeetCode-задачи — простые задачи на ограничения

Интервьюер спросил: «Минимальное количество монет для сдачи 37¢ при номиналах [10, 9, 1]».
Жадный алгоритм даёт 10 монет, оптимум — 4. Ручное ДП сложно, а в MiniZinc — три строки:

int: total; array[int] of int: values = [10,9,1];
array[index_set(values)] of var 0..: coins;
constraint sum(c in index_set(coins)) (coins[c]*values[c]) == total;
solve minimize sum(coins);

Запускаем онлайн, получаем ответы за секунды.

---

Другие «сложные» задачи

1. Максимальная прибыль на акциях
   Дано: цены за день.
   Решение: купить до продать, максимизировать prices[sell]-prices[buy].

   array[int] of int: prices;
   var int: buy; var int: sell;
   constraint sell > buy;
   solve maximize prices[sell]-prices[buy];
   

2. Три числа дают 0 в сумме
   Нужно ли среди списка выбрать 3 числа со знаками ±1, чтобы сумма была 0?

   array[int] of int: nums;
   array[index_set(nums)] of var {-1,0,1}: coef;
   constraint sum(i in index_set(nums)) (nums[i]*coef[i]) = 0;
   constraint sum(i in index_set(nums)) (abs(coef[i])) = 3;
   solve satisfy;
   

3. Самый большой прямоугольник в гистограмме
   Ширина столбцов = 1, высоты заданы.

   array[int] of int: h;
   var 1..length(h): x; var 1..length(h): dx; var 1..max(h): y;
   constraint x+dx <= length(h);
   constraint forall(i in x..x+dx) (y <= h[i]);
   solve maximize (dx+1)*y;
   

---

Плюсы и минусы солверов

• + Код в 3–5 строк, добавление новых ограничений бесплатно.
• – Сложность работы непредсказуема, медленнее «идеального» алгоритма.
• – На собеседовании спросят «а сложность?» — ответа нет.

Вывод: если нужен рабочий код быстро — бери солвер; если нужна гарантированная скорость — пиши алгоритм вручную.