contribution of a₀[i] in a_r[n] is
Using this and binary search on answer , you can solve this in NlogK

Is there a name for the type of function in G? It's some combination of Sigmoid and ReLU, but I couldn't find it's name...

В задаче G можно обойтись без персистетности написав, например, sqrt-декомпозицию.

В каждом блоке мы можем хранить для каждого x_i два значения: a_i и b_i. Чтобы их посчитать, мы можем использовать технику сканирующей прямой. Чтобы получить ответ для блока, мы для x бинарным поиском найдем наибольший i такой, что x_i  ≤  x, тогда ответ для блока будет равен a_i · x  +  b_i. Чтобы получить ответ на запрос, нам нужно просуммировать ответы для блоков, которые целиком входят в [l, r], а для оставшихся f_i пройдемся в тупую и прибавим к ответу.

Асимптотика:

Can anyone help me in understanding the rationale behind choosing the way the dp is being done? Why the 3D approach? How was the logic arrived at? Is there another, more intuitive way? Thanks!

Could somebody explain the way we store all possible summary powers of 5 in dp array? There can be i * log₅(10¹⁸) variants, and if we will iterate through them all n² times (including non-existing), it will waste too much memory ..

I tried to use map to exclude non-existing variants, but n³ * log(n * log₅(10¹⁸)) got TL: http://mirror.codeforces.com/contest/837/submission/29189656

Thanks in advance :)

UPD. Finally got it. We do not need to store current position, only 2 last lays needed (dp[2][200][200 * log₅(10¹⁸)])

My lame F solution that passes:

n > 3 is sufficient to pass the naive approach (after zero prefix deletion). So we should handle n==2 and n==3. For n==2 we can write linear O(1) equation on k, and for n==3 there is quadratic equation on k which can be solved in O(1) or O(log 10^18) using binsearch.

On Problem G, I set up four President Tree and the Time Limit seems too tight for me 29192449, maybe I will be hacked sooner or later :)

Почему в задаче D, круглость числа — это минимум из степеней 2 и 5 в числе.

Simpler solution to Problem E. Without prime factorization. Let d = gcd(a, b); It can be proved that f(a,b) = f(a/d, b/d); if a is prime, then answer is (b % a + b/a); Then the result can be recursively computed. My solution

. can any1 prove it ; If we denote old value of gcd(x, y) by g, the new value of gcd(x, y) will be divisible by some k·g, where k is a prime divisor of x.

For Problem F - In fact, you can brute force the prefix sums if the array is of size at least 4. In case of size 2 it's super simple. And lastly, in case of size 3 it can be solved mathematically.

Regarding problem D, does this sentence: "the first dimension should be stored in two layers and recalced on the fly" mean that :

for every position i you only need the result of i-1 so no need to store the results corresponding to positions earlier than i-1 ?

Anyone can help me to find what's wrong with my solution for problem D? http://mirror.codeforces.com/contest/837/submission/29282743

can anyone elaborate this line?

Let dp[i][j][l] be the maximum amount of twos we can collect by checking first i numbers, taking j of them with total power of five equal to l. It is usually called "the knapsack problem".

Task E

Can anybody proove that k in new gcd will be PRIME (that there is no better non-prime k)?

F has a much simpler solution using contribution technique i believe.

How to solve problem D using top-down approach?

How to solve D using recursive dp? Is it possible? I wrote the recursive function to compute the number of twos but it is very confusing how to extract the solution out of it.