In this task required to understand that the answer max( *a*[*i*] - *a*[*i* - 1] - *c*), *i* = 2..*n* and don't forget that the answer not negative as Bear can not borrow in the debt barrel of honey.

In this problem you could write a better solution than the naive. To do this, you can iterate through the first cycle of the left index *l* considered substring and the second cycle of the right index *r* considered substring (*l* ≤ *r*). If any position has been substring "bear", means all the strings *x*(*l*, *j*) (*i* ≤ *j*), also contain "bear" as a substring. So we can add to the answer |*s*| - *j* + 1 and exit from the second cycle. Also needed to understand, that if the string *x*(*l*, *j*) was not a substring "bear", then in row *x*(*l*, *j* + 1) substring "bear" could appear only in the last four characters.

In order to solve given problem, contestant should solve several subproblems :

1) First one is to compute amount of entries of each natural number between 2 and 10^{7} in given list. This subproblem can be solved by creating array *count* of 10^{7} elements and increasing corresponding element when scanning input.

2) Second one is to compute *f*(*n*).

First of all, we need to find all primes less than 10^{7} and then for each prime *n* compute *f*(*n*).

How to compute *f*(2)? We should sum *count*[2], *count*[4], *count*[6], *count*[8],...

How to compute *f*(5)? We should sum *count*[5], *count*[10], *count*[15], *count*[20],...

How to compute *f*(*n*)? We should sum *count*[*n*], *count*[2·*n*], *count*[3·*n*], *count*[4·*n*],...

It can be seen that given algo is very similar to Sieve of Eratosthenes. (Info here http://e-maxx.ru/algo/eratosthenes_sieve) So we can use this algo if we change it a little bit. Also, we will store results of calculation in array, e.g. *pre*. Namely, *pre*[*n*] = *f*(*n*).

3) Now we can calculate partial sums of *pre* array. It can be made in a single pass just adding *pre*[*i* - 1] to *pre*[*i*].

4) If we know partial sums of array then we can calculate sum of array elements between *l* and *r* in time proportional *O*(1), just calculate *pre*[*r*] - *pre*[*l* - 1].

5) Now we can read queries and immediately response to them. You shouldn't forget that right boundaries of intervals can be greater than 10^{7}, so you can always decrease it to 10^{7}, because all numbers in given list are less than 10^{7}.

In this task, it is crucial to understand that whether there is lighted part of road with length *dist* then next part should be lit in a such way that leftmost lighted point is touching with *dist*.

Let's suppose that road is lit from *l* to *d*. How we can find rightmost point on X axis that would be lit by next floodlight?

We can just use concepts of vector and rotation matrix.

Let's find vector (*dx*, *dy*) from floodlight to point on X axis (*d*, 0). (*dx*, *dy*) = (*d* - *x*, 0 - *y*).

Next point to rotate vector by *angle* degrees. We can use rotation matrix for this purpose.

(*dx*, *dy*) = (*dx*·*cos*(*angle*) - *dy*·*sin*(*angle*), *dx*·*sin*(*angle*) + *dy*·*cos*(*angle*))

Next, we should make second component *dy* of (*dx*, *dy*) equal to 1 by multiplying on coefficient *k*.

Now we can determine rightmost lighted point of X axis. It is *x* - *y*·*dx*.

You shouldn't forget that there is possibility for rightmost point to be infinitely far point.

From now on we can forget about geometry in this task.

Let's find fast way to determine optimal order of floodlights.

To achieve this goal, we can use dynamic programming approach. Namely, let's calculate answer for subsets of floodlights. Each subset would be represented as integer where *k* bit would be 1 if *k* floodlight is presented in subset and 0 if it is not, i.e. so named binary mask.

For example, *dp*[6] — (6 — 110_{2}) is optimal answer for subset from 2 and 3 floodlight.

Now, let's look through subsets *i* in *dp*[*i*]. In subset *i* let's go through absent floodlights *j* and update result for subset where *j* floodlight is present, i.e. dp[ *i* or 2^{ j} ] = max(dp[ *i* or 2^{ j} ], dp[ *i* ] + calc_rightmost_lighted_point() ). As we can calculate rightmost lighted point, so updating of answer shouldn't be a problem.

In this task there are several problems that should be concerned:

1) Simple modeling of bear movement would cause TLE due to *t* ≤ 10^{18}.

2) Task can't be solved by separating *x* and *y* axes because *x* and *y* depends on each other.

3) Also, we can't use standart method of cycle finding via modeling for a short time and checking on collisions because coordinates limitations are very large.

Let's say we have matrix (*x* _{ i}, *y* _{ i}, *dx* _{ i}, *dy* _{ i}, *t* _{ i}, 1).

If we multiply previous matrix by following matrix long long base[6][6] = {

{2,1,1,1,0,0},

{1,2,1,1,0,0},

{1,0,1,0,0,0},

{0,1,0,1,0,0},

{0,0,1,1,1,0},

{0,0,2,2,1,1} };

we will have get parameters on next step.

Where did the matrix? Let us write out how to change parameters with each step and see the similarity matrix.

*x* = 2·*x* + 1·*y* + 1·*dx* + 0·*dy* + 0·*t* + 0·1.

*y* = 1·*x* + 2·*y* + 0·*dx* + 1·*dy* + 0·*t* + 0·1.

*dx* = 1·*x* + 1·*y* + 1·*dx* + 0·*dy* + 1·*t* + 2·1.

*dy* = 1·*x* + 1·*y* + 0·*dx* + 1·*dy* + 1·*t* + 2·1.

*t* = 0·*x* + 0·*y* + 0·*dx* + 0·*dy* + 1·*t* + 1·1.

1 = 0·*x* + 0·*y* + 0·*dx* + 0·*dy* + 0·*t* + 1·1.

So if we calculate *t* - 1 power of *base* and then multiply (*sx*, *sy*, *dx*, *dy*, *t*, 1) by it we will calculate parameters at moment *t*.

Power of matrix can be calculated via binary power modulo algo due to associativity of matrix multiplication. More info at http://e-maxx.ru/algo/binary_pow

Using trivial matrix multiplication algo we will solve this task in time proportional 6^{3}·*log*(*t*).

Great Editorial!

I solved E (theoretically, I don't really want to implement it) by solving the system of equations:

x(t) = [x(t- 1) +v_{ x}(t) - 1]%N+ 1y(t) = [y(t- 1) +v_{ y}(t) - 1]%N+ 1v_{ x}(t) =v_{ x}(t- 1) +t- 1 +x(t- 1) +y(t- 1)v_{ y}(t) =v_{ y}(t- 1) +t- 1 +x(t- 1) +y(t- 1)for $t > 0$, where the values of (

x,y,v_{ x},v_{ y})(0) are given as input parameters, and the time is 0-based.Firstly, we want to get rid of the modulo function. We can't just compute all variables modulo

N, because there's the -1, so we'll shift the coordinates to (x',y')(t), wherex' =x- 1,y' =y- 1. Now the equations becomex'(t) =x'(t- 1) +v_{ x}(t)y'(t) =y'(t- 1) +v_{ y}(t)v_{ x}(t) =v_{ x}(t- 1) +t+ 1 +x'(t- 1) +y'(t- 1)v_{ y}(t) =v_{ y}(t- 1) +t+ 1 +x'(t- 1) +y'(t- 1)where all variables are computed modulo $N$ (we'll omit that from now on). We can compute (

x,y,v_{ x},v_{ y})(1) from this, and further substitute forv_{ x},v_{ y}, which gives fort> 1x'(t) -x'(t- 1) =x'(t- 1) -x'(t- 2) +t+ 1 +x'(t- 1) +y'(t- 1)y'(t) -y'(t- 1) =y'(t- 1) -y'(t- 2) +t+ 1 +x'(t- 1) +y'(t- 1)Let's now define

s(t) =x'(t) +y'(t)d(t) =x'(t) -y'(t)using which we can rewrite the sum and difference of the equations above to

d(t) -d(t- 1) =d(t- 1) -d(t- 2)s(t) -s(t- 1) =s(t- 1) -s(t- 2) + 2(t+ 1) + 2s(t- 1)Once again, we define $q(t)=s(t)+t+2$ (actually, it's

s(t) +t+c, and we compute the constantcby substituting and trying to get the constant term to 0), and rewrite our equations tod(t) = 2d(t- 1) -d(t- 2)q(t) = 4q(t- 1) -q(t- 2)which can be solved explicitly (I'm lazy, so I'm just using Wolfram Alpha, read more about linear recurrent equations on Wikipedia or something):

d(t) =C*t+Dwhere the parameters $A..D$ are given by the values for

t≤ 1.This is more of a theoretical solution (since as long as we get the recurrences for

d(t) andq(t), it's best to use matrix multiplication), but I just wanted to do it this way :Di think the matrix should be that: {2,1,1,1,0,0},

{1,2,1,1,0,0},

{1,0,1,0,0,0},

{0,1,0,1,0,0},

{0,0,1,1,1,0},

{0,0,0,0,1,1} };

i tried and solved it. with this matrix.

Rev. 23????! How could this happen?! :D

Maybe for the same reason as rev.7 of my comment above — I edit my comment, click "Save", nothing happens; I wait until my internet connection is stronger, click again, and nothing happens again, etc., until I lose patience and reload the page. And look what happened: the revisions were counted, but my comment wasn't edited. Some bug of CF, maybe.

Nice editorial. Anyways, I had a sense that explanation of problem E does not give you an idea of how you can come up with that solution. Let me clarify that: The state can be described by following variables: x — where is the bear currently (x-coordinate); y — where is the bear currently (y-coordinate); dx — the current speed towards X axis; dy — the current speed towards Y axis; t — time passed after the start;

This information is enough to describe a state. Now let's see how the state changes: (dx)' = dx + (x+y+t), (dy)' = dy+(x+y+t), (x)' = x + (dx)' = 2x+y+dx+t, (y)'=x+2y+dy+t, (t)'= t+1.

As we see, the new state is similar to linear combination of previous state components, except for t=t+1 (1 is not in a state). It is very similar to matrix multiplication, except for we don't have 1. So we can make a matrix this way: Let's say the state is (1x6) matrix : (x, y, dx, dy, t, 1) and the matrix (M) is 100001 021110 012110 010100 001010 011111 It's easy to see why the new state is the old state matrix multiplied by M. The rest is easy, our final state is going to be the initial state matrix multiplied by the T-th power of M. Of course we're gonna use the fast exponentiation. (The naive multiplication is fine here, because the sizes are too small)

thx a lot ~ during the exam i think the raspberry will be eaten all , then the number will change from x+y-->1 a silly misunderstanding T_T

I'm sorry :) but I don't see why (x)'= x+(dx)'? Could u explain that to me?

Ah

Ah now I see it. Thank you for your explanation :)

Problem D !?!

how u can calculate calc_rightmost_lighted_point() in ur Dp without keeping the last right_most_point u can get till before this state

By the way, in problem D you can use law of sines to find the distance that is lighted with some floodlight.

In problem C , i can't understand why we add pre[i-1] to pre[i]?

If you iterate i from 2 to n-1 adding pre[i-1] to pre[i], every new pre[i] will contain sum of all pre from 1 to i

Thank you! one more question how to prove that pre[r]-pre[l-1] is answer of query?

I think it is clearer if we denote Cnt[i] = f(i) and Sum[i] = Cnt[1] + Cnt[2] + ... + Cnt[i]. Now, the answer for a query on [l, r] is Sum[r]-Sum[l-1].

Sum[r]-Sum[l-1] = (Cnt[1] + Cnt[2] + ... + Cnt[r])-(Cnt[1] + Cnt[2] + ... + Cnt[l-1]) = [(Cnt[1] + ... + Cnt[l-1]) + (Cnt[l] + Cnt[l + 1] + ... + Cnt[r])] — (Cnt[1] + ... + Cnt[l-1]) = Cnt[l] + Cnt[l + 1] + ... + Cnt[r].

THANK YOU

emilbek ReekinAcer can u help me please. here my code for C and get WA at tc 4 !! 9731769

Nice editorial! But I suppose that a link to a solution implementing the idea outlined in the editorial for every question would help us understand them even better!

Well, you can use "Status filter"

Well, not all the accepted solutions use the idea mentioned in the editorials. It's a bit inconvenient browsing through all accepted solutions to find the one which does.

Hello! Faced with such problem … this code on my notebook running 58 s, when testing the codeforces — 1.2 s. Why so? Quick tester server?

can anyone give a more detailed explanation of bear and the strings?

it would be nice if someone can help..thank you :)

In problem C, I did made a cnt array (or say a hashmap) and did find all primes below the maximum x using Sieve of Erathosthenes, then for each prime I iterated over every number and and found f(p) and stored them in a Binary Index Tree, but that didn't help. I believe my complexity is O(n(logn)(loglogn)+m(logn+logP)+PlogP) where P(664,579~10^7) is the count of primes below maximum x so total operations are around 5e6+6e7+4e7 but it has a TLE?.This is my submission.

how to count the number of words from l to r using prefix sum O(1)

can anyone help me out? I have tried 385C and it gives me a runtime error on test case 4 link to my code — https://ideone.com/fork/GMagWh

I don't know if you are still looking for this :

That might be because x or y i.e the query ranges might be going out of limits. Also it may help the others who attempt it.

Edit : Also if anyone is getting TLE even after implementing same approach use: