385A - Bear and Raspberry

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.

385B - Bear and Strings

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.

385C - Bear and Prime Numbers

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⁷ in given list. This subproblem can be solved by creating array count of 10⁷ 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⁷ 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⁷, so you can always decrease it to 10⁷, because all numbers in given list are less than 10⁷.

385D - Bear and Floodlight

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₂) 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.

385E - Bear in the Field

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

1) Simple modeling of bear movement would cause TLE due to t  ≤  10¹⁸.

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³·log(t).