Забавно, у нас то же самое, только у вас +, а у нас +16 :)

У нас быстро зашел перебор с отсечением по ответу и предварительной сортировкой массива.

Да, мы уже поняли, действительно очень просто. Мы что-то затупили и запихали что в этой задаче, что в A, решение за 3ⁿ с кучей разных хаков.

Can you give me the code of the solution?

Можно даже просто для маски минимизировать сколько всего набрано. Этим однозначно определяется сколько стопок и сколько осталось в последней стопке, и соответственно добавим ли мы новый в эту же стопку или уже перейдем в следующую.

Can you explain in detail, why "conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask] != 0"?

For the fixed a and b, I can calculate conv^-1(conv(clique)^a * conv(antilclique)^b) in O(n2^n) easily. But how to make it O(n2^n) overall?

Could you please give some more details or your code for F.

Подпрограмма сводится к листу булов (снимаем последний элемент со стека и добавляем или вычитаем из предпоследнего), delta (добавляется к последнему после выполнения листа булов) и листу интов (кладутся на стек)

I solved I using matrix multiplication. I took a 11x11 matrix (10 stack variables and 1 constant). Then, putting a digit on stack, +, — every thing can be represented as a 11x11 matrix.

Also each of the sub-routine is a matrix.

It made my solution simpler.

Давай для каждой каждой подпрограммы посчитаем, как она повлияет на стек. В общем случае, каждая подпрограмма берёт стек величины k и возвращает стек величины l, в котором элементы являются какими-то линейными комбинациями элементов исходного стека, возможно с некоторыми прибавленными константами. Будем для каждого k прямо хранить коэффициенты всех этих линейных комбинаций; тогда последовательное применение двух подпрограмм выражается в таком же виде с помощью чего-то сродни перемножению матриц (на самом деле, можно явно выписать матрицы, которые перемножаются).

Сделаем ветор-столбец, в котором будем хранить 6 вариантов стека для каждого размера (от 0 до 5), размер текущего стека и единичку (пригодится потом). Тогда операции можно выразить в матричном виде: при запихивании матрица будет из стека размера (i — 1) перекидывать элементы в размер (i), а последний элемент получить умножением нашей единички на добавляемый элемент, а ещё прибавляем единицу к размеру. Операции сложения и вычитания делаются аналогично. Тогда каждая программа будет матрицей и можно применять ее за 17^3. Итого асимптотика O(|s|*17^3).

Есть альтернативное решение. Обозначим за d числа на стэке, s – знаки.

Тогда d1 d2 s заменяется на d3 = (d1 s d2).

d1 s1 d2 s2 заменяются на d3 s3, которые легко считаются для разных s1 s2.

Будем просто раскрывать программу и делать замены. Если в какой-то момент длина стала больше > 20 (хватает с запасом), то говорим, что эта программа невалидная и все, кто ее используют тоже невалидные и больше их не анализируем.

В результате итоговая программа будет содержать просто d1 .. dn

Наивное решение делается в два этапа. На первом этапе вычисляем простой текст всех подпрограмм во всех контекстах и просто сохраняем как строки. На втором этапе выполняем простой текст полученной программы. Действительно, это решение построит экспоненциально длинный простой текст для программы вида [9+]a[aaaa]a[aaaa]a...[aaaa]a9a. При длине строки до 160 ответ ещё помещается в int64, но такое решение не выполняет ограничения по времени и памяти.

Для быстрого решения заметим, что все операции со стеком можно представить в виде матриц 6 × 6:

   (t0)     (a00 a01 a02 a03 a04 a05)     (s0)
   (t1)     (a10 a11 a12 a13 a14 a15)     (s1)
   (t2)  =  (a20 a21 a22 a23 a24 a25)  *  (s2)
   (t3)     (a30 a31 a32 a33 a34 a35)     (s3)
   (t4)     (a40 a41 a42 a43 a44 a45)     (s4)
   ( 1)     ( 0   0   0   0   0   1 )     ( 1)

Здесь (s0, s1, s2, s3, s4) — исходный стек, начиная с верха, (t0, t1, t2, t3, t4) — результирующий стек, начиная с верха, а шестая строка служит для прибавления и вычитания константы. Примеры:

         (0 0 0 0 0 9)              (1 1 0 0 0 0)
         (1 0 0 0 0 0)              (0 0 1 0 0 0)
   9  =  (0 1 0 0 0 0)        +  =  (0 0 0 1 0 0)
         (0 0 1 0 0 0)              (0 0 0 0 1 0)
         (0 0 0 1 0 0)              (0 0 0 0 0 0)
         (0 0 0 0 0 1)              (0 0 0 0 0 1)

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

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

It's [1]b[b[2]bb]ccc. The resulting stack is (from top) 2 1 2 1. Here, the subprogram is c = "12", as per the rules in the statement.

при помощи теоремы Виета расписать и получить, что

(x1-1)*(x2-1) = n + 1

где x1,x2 — корни. После этого нужно найти все делители числа n + 1 (и отрицательные тоже) и взять их как x1-1, восстановить коэффициенты p,q и положить их в сет. И не забыть, что для -1 ответ infinity