Another n-dimensional chocolate bar
Contest: Codeforces Round 857 (Div. 1)
Difficulty rating: 2700
Tags: dp, math, meet-in-the-middle, number theory

Vasya and his friends want to cut a chocolate bar to get at least $$$k$$$ pieces, while Vasya wants to maximize the volume of the smallest of them. It is possible to cut the chocolate bar only at the junction of the lobules, and each incision must pass through the entire chocolate bar along some hyperplane involved in the formation of lobules. Only after making all the cuts, Vasya disassembles the chocolate into pieces.

More formally, Vasya wants to choose the numbers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le a_i$$$) — the number of parts into which Vasya will cut the chocolate bar along each dimension. The condition $$$b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k$$$ must be met to get at least $$$k$$$ pieces after all cuts. It can be noted that with optimal cutting with such parameters, the minimum piece will contain $$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor$$$ slices, and its volume will be equal to $$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}$$$.

Vasya wants to get the maximum possible value of the volume of the minimum piece multiplied by $$$k$$$, that is, he wants to maximize the number of $$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k$$$. Help him with this.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 100$$$, $$$1 \le k \le 10^7)$$$ — the dimension of the chocolate bar, and how many parts it needs to be divided into.

The second line contains $$$n$$$ integers $$$a_1,\ a_2,\ \dots,\ a_n$$$ $$$(1 \le a_i \le 10^7)$$$ — the number of pieces on which the chocolate is placed along each of the dimensions.

Output format:
Print one number  — the maximum possible volume of the smallest of the obtained pieces, multiplied by $$$k$$$, with an absolute or relative error of no more than $$$10^{-9}$$$.

If it is impossible to cut a chocolate bar into at least $$$k$$$ pieces under the given restrictions, output $$$0$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, a one – dimensional chocolate bar can be divided as follows:

Then the answer will be $$$\frac{2}{5} \cdot 2 = 0.8$$$

In the second example, the chocolate bar can be cut as follows:

Then the answer will be $$$\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72$$$

In the third example, the chocolate bar can be cut as follows:

Then the answer will be $$$\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875$$$

Example input:
1 2
5

Example output:
0.8

Example input:
2 6
5 10

Example output:
0.72

Editorial:
За $$$A$$$ обозначим максимальное значение $$$a_i$$$
Для начала решим задачу за $$$O(n \cdot k \cdot f(k, A))$$$ с помощью динамического программирования.
Положим $$$dp[i][j]$$$ - максимальный возможный объем наименьшего кусочка, если по первым $$$i$$$ измерениям мы разделили шоколадку на $$$j$$$ частей. Если мы разделили более чем на $$$k$$$ частей, так же положим результат в $$$dp[i][k]$$$. В пересчете нам нужно решить на сколько часей делить шоколадку вдоль очередного измерения. Рассмотрим несколько способов это сделать.
- Можно за $$$O(k)$$$ перебрать состояние, в которое переходим, и из этого посчитать на сколько частей нужно разделить шоколадку вдоль очередного измерения. - Получим $$$O(n \cdot k^2)$$$
- Можно за $$$O(A)$$$ перебрать на сколько частей мы делим шоколадку вдоль очередного измерения.
- Находясь в состоянии $$$dp[i][j]$$$, можно перебирать $$$b_i$$$ - на сколько частей делить шоколадку, пока $$$j \cdot b_i \le k$$$. Можно показать, что такое решение будет работать за $$$O(n \cdot k \cdot \ln{k})$$$
Ключевая идея
- предположим нам нужно разделить шоколадку на $$$10$$$ частей, и вдоль первых измерений мы уже разделили её на $$$5$$$ частей, или на $$$6$$$ частей, или на $$$7, 8$$$ или $$$9$$$ частей. Все эти состояния не различимы для нас, потому что во всех этих случаях нам нужно разделить шоколадку ещё хотя бы на $$$2$$$ части. Осталось понять сколько всего таких «интересных» состояний и научиться их хранить. Для этого есть несколько подходов, разберем один из них:
- нам интересны все значения $$$\lceil \frac{k}{i} \rceil$$$ для $$$i = 1, 2, \ldots k$$$ - это то, на сколько частей ещё может быть нужно разделить шоколадку. Среди них всего $$$O(\sqrt{k})$$$ различных, так как либо $$$i \le \sqrt{k}$$$, либо само значение $$$\lceil \frac{k}{i} \rceil \le \sqrt{k}$$$. Если сделать все эти числа состояниями, и пересчитываться, перебирая состояние, в которое переходить, получим $$$O(n \cdot \sqrt{k} \cdot \sqrt{k}) = O(n \cdot k)$$$ - этого всё ещё не достаточно, чтобы решить полую задачу.
Последнее наблюдение
Если мы находимся в состоянии $$$dp[i][remain]$$$ где $$$remain = \lceil \frac{k}{i} \rceil$$$ для какого-то $$$i$$$ - применим к нему ту же идею. Из него нам интересны переходы в состояния $$$\lceil \frac{remain}{j} \rceil$$$ для $$$j = 1, 2, \ldots remain$$$. Какая асимптотика получится, если перебирать только интересные переходы?
$$$n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$$$
- можно показать, что это $$$O(n \cdot k^{3/4})$$$ - что решает задачу