Enchom I found on Petr's blog a more convenient way to take FFT mod an arbitrary number. View the comments in Russian mode. For short, the code.

Everyone whose a SPOJ account can practice the problem described in this link: VMLSEQ

I solved this problem. Here comes some main ideas:

We can split the given sequence into some arrays of indices (I will call them as chain): For example

10 2

2 1 -1 -2 5 1 -1 7 -7 5

can be splitted like this:

0 4

1 3

5 7 9

6

8

10

Property:

In each chain, for every two element x and y, a[x + 1..y] is a valid subsequence.

It's not hard to build these chains, I think you can do it yourself.

Now for each query l r, change it int to l-1 r you have to find two indices x and y which satisfy l <  = x <  = y <  = r and x, y are in the same chain.

My first approach is sort all queries (l-increase then r-increase). Iterate all queries then update result via a segment tree. Complexity is O(NlogN) for building chain, O(QlogQ) for sorting queries and O(Q * SQRT(Q) * logN) for solving queries. Unfortunately, this solution got TLE in some large tests.

The second approach is SQRT decomposition: sort queries and solve them in each SQRT(N) block, separately. This approach have complexity is O(Q * SQRT(Q)) for solving queries. It got 100 points and took about 2s in runtime. You may read the main idea of this approach HERE.

The third approach is heavy-light. Consider chains which have size smaller than BUBEN is light, otherwise heavy. For light chains, sort queries and iterate them, save local best of each queries. It takes O(Q + |sum.size.of.all.light.chains|) in worst case. For heavy chains, iterator all queries, with each pair of queries and heavy chain, use binary search and segment tree to find local best. It takes O(Q * |number.of.heavy.chains| * logN) in worst case. Combine local best of two phase, we have the answer for all queries. Chose BUBEN as SQRT(N), the complexity O(Q * SQRT(N) * logN) in worst case but indeed this solution is extremely fast (currently best time). I think it's hard to make a test to kill this solution.

My explaination seems confusing since I have no experience in explanning my ideas but I hope this is helpful.

The main idea of my algorithm is solve the chains queries offline, I found a problem which can be solved using this method: http://www.spoj.com/problems/ZQUERY/ . Time limit for this problem is relaxing, so you can take some implementations for benchmark.

All of algorithms I described have complexity SQRT(N) as a factor, I'm curious about the poly-log algorithm. Please share here if you have such that kind of algorithm.

UPD: There is an algorithm with complexity O(N^4 / 3). Let's separate given sequence into S blocks, we can create dp[i][j] = Length of longest valid subsequence from which starts at block i and ends at block j. Sort all queries then solve each of them with O(N / S) in worst case. So we have a solution with complexity O(S * S + Q * N / S). Set S equal to N^2 / 3, we have an O(N^4 / 3) solution (considering N = Q). However this approach took 1.8s in the problem, much slower than the third.

How do you cut the cake in case N = 11. I always think that there isn't any solution with number of cut needed < 6.

Sorry, I think you were misunderstood the problem. We can not move the cake while we are cutting so the equation: a_n = a_n / 2 + 1 is wrong.

Example:

N = 11 your program returned 5 but we need at least 6 cuts: 3 horizontal cuts divide the cake into 4 pieces: 4/11 4/11 2/11 and 1/11 then vertical cuts divide the cake into 16 pieces: 8 pieces 1/11, 4 pieces 1/22 and 4 pieces 1/44. There isn't any solution with less than 6 cuts.

In ORGANIZATOR we can use sieve eratosthenes and array f[2e6] mean that f[x] is the smallest prive factor of x so we can find all factor of x in O(log x). Next we generate all division of x, it is about log(x)*log(x) number. In contest I only find prive division of x so i fail all test. At the end of contest I see my wrong but too late. Here is my AC solution: http://ideone.com/kmrO5I

About the first B digits, the problem has something same to this problems in hackerrank. The solution is to calculate the first k digits of x, we calculate log10(round(x/10^k)). => Editoral of it. The function can be calculate easily if we can calculate log(n!) in O(1) or O(log(n)). About calculate log(n!) you can see here.

My first submission is 14 min after contest but it still in queue. In current standing I see Egor accepted C 30 min after contest. The system test work down, i think i should sleep and ignore this contest

When I run applet it always unable to launch. I go to topocder but the page can't be access. I can only launch applet at half of contest and in challenge phase I was kicked out of applet. Anyone tell me it topcoder's error or my network's error?

as his wiki today is his birthday. congratulation and happy birthday tourist

Can it be display in English? I don't know Russian, I copy problems from foxit reader to google translate but is not suitable to translate