Анирин задатак
Аутор, текст, тест примери и анализа решења: Немања Мајски
Тестирање: Благој Рујаноски Стојановски (MKD)
Основна запажања
Ради прегледности, више тврђења је у овом решењу наведено без доказивања. Детаљан доказ можете наћи овде.
Прво запажање је да ће Анири увек на картицу записати већи од бројева a+b и a \cdot b, пошто ће у каснијим операцијама то да доведе то већих бројева.
Решење када је Q =1 и a_i \ge 2
У овом подзадатку ће сви бројеви који икад буду у ранцу бити \ge 2. А како за било која два броја a, b \ge 2 важи a \cdot b \ge a+b, значи да је одговор на упит производ свих бројева у ранцу, односно његов остатак при дељењу са M.
Решење када је N \le 8, Q=1 и a_i \le 100
У овом подзадатку је могуће рекурзивно пролазити кроз све могуће изборе бројева у сваком кораку. Како резултат не прелази 10^{16}, он стаје у 64-битни тип података.
Решење када је N \le 100, Q \le 1000 и a_i=1
Направићемо dp низ тако да је dp_i највећи број који може да се добије ако имамо i јединица. Почетни услови су dp_1 = 1, dp_2 = 2, dp_3 = 3.
Сада је проблем како наћи вредност dp_n за n > 3. Користимо чињеницу да је могуће прво извршити сва сабирања, па затим помножити све бројеве у ранцу. То значи да чиниоце можемо да правимо један по један, а онда на крају да их све помножимо. Рецимо да смо фиксирали да ће нам први чинилац бити x. Онда од преосталих n - x јединица треба да направимо што већи број, који ћемо помножити са x. Тај број смо претходно већ израчунали и он је dp_{n-x}.
Тако да је вредност dp_n максимум од x \cdot dp_{n-x} за свако 1 \le x < n.
Сложеност је O(N^2 + Q).
Решење када је N, Q \le 1000 и a_i=1
Сложеност претходног подзадатка је довољно брза да временски одради и овај. Али проблем настаје у томе што је dp_{1000} веома велики број и не стаје у 64-битни тип података. Тако да не можемо радити поређење да бисмо нашли максимум, морамо наћи формулу за тај број.
Ако математички запишемо наш резултат, он ће изгледати као производ више заграда, у којој се налази збир неколико јединица. Пример за dp_{10} = 36:
$$(1+1+1) \cdot (1+1+1) \cdot (1+1) \cdot (1+1) = 36$$
Приметимо да ће у свакој загради бити две или три јединице, пошто за n \ge 4 важи \lfloor \frac{n}{2} \rfloor \cdot \lceil \frac{n}{2} \rceil \ge n, а имати једну јединицу у загради нема смисла.
Како је (1+1) \cdot (1+1) \cdot (1+1) < (1+1+1) \cdot (1+1+1), то значи да ће највише две заграде ће имати две јединице. Број заграда са две јединице одређен остатком дељења n са три. Из тога следи формула dp_n = 3 \cdot dp_{n-3} за n \ge 5.
Решење када је N,Q \le 1000 и a_i \le 2
Нека је број јединица у ранцу a, а број двојки b. Уколико је a \ge b, онда је решење dp_{a+2\cdot b}, пошто је могуће све двојке претворити у тројке, па ће крајна конструкција бити иста као што би била да су двојке заправо две јединице. Сада посматрамо случај када је b > a.
Приметимо да никада нећемо да имамо чинилац већи од три у нашем производу. Тако да ћемо ми неке двојке повећати за један, а остале јединице ћемо комбиновати као у претходном подзадатку.
Претпоставимо да смо одлучили да неке две јединице групишемо у загради. Гарантује се да постоје барем две двојке којима нисмо додали јединицу (због b > a). Како је (1+1) \cdot 2 \cdot 2 < (2+1) \cdot (2+1), оптимално је да ми те две јединице ипак додамо на двојке, а не да их групишемо у заграду. Аналогно (1+1+1) \cdot 2 \cdot 2 \cdot 2 < (2+1) \cdot (2+1) \cdot (2+1).
Следи да је у овом случају оптимално додати све јединице на двојке, тако да је одговор 2^{b-a} \cdot 3^a.
Решење када је N,Q \le 1000
У овом подзадатку се појављују и бројеви већи од два. Само јединице ће се додавати на неке бројеве, или комбиновати. Остали бројеви се само множе. Да би се дошло до решења, требају редом да се примењују следећа правила.
Ако постоји само једна јединица у ранцу, она ће бити додата на други најмањи број у ранцу (најмањи сем ње).
Ако не постоје двојке у ранцу, све јединице ће бити груписане саме са собом, а резултат ће бити помножен са производом осталих бројева. Ово важи пошто dp_{n+1} \ge \frac{4}{3} \cdot dp_n за n \ge 2.
Ако постоје двојке у ранцу, оне се комбинују са јединицама као у претходном подзадатку. Одонсно, додају се на двојке све док има и јединица и двојки. За остатак јединица се примењују претходна два правила.
Главно решење
За рачунање одговора на упит у претходном подзадатку нам је било потребно да нађемо:
- Број јединица у ранцу;
- Број двојки у ранцу;
- Најмањи број у ранцу већи од два (ако постоји);
- Производ свих осталих бројева.
Све ово можемо да нађемо у сложености O(\log N) по упиту користећи сегментно стабло. Након тога само израчунавање вредности може да се одради у сложености O(1) уз прекалкулације.
Сложеност алгоритма је O(N + Q \log N).