CleRIC's blog

By CleRIC, 11 years ago, translation, In English

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

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] — (61102) 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 2j ] = max(dp[ i or 2j], 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  ≤  1018.

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 (xi, yi, dxi, dyi, ti, 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 = x + y + dx + dy + t + 0·1.

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

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

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

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

1 = x + y + dx + dy + 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 63·log(t).

  • Vote: I like it
  • +85
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Great Editorial!

»
11 years ago, # |
Rev. 7   Vote: I like it +28 Vote: I do not like it

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

x(t) = [x(t - 1) + vx(t) - 1]%N + 1
y(t) = [y(t - 1) + vy(t) - 1]%N + 1
vx(t) = vx(t - 1) + t - 1 + x(t - 1) + y(t - 1)
vy(t) = vy(t - 1) + t - 1 + x(t - 1) + y(t - 1)

for $t > 0$, where the values of (x, y, vx, vy)(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), where x' = x - 1, y' = y - 1. Now the equations become

x'(t) = x'(t - 1) + vx(t)
y'(t) = y'(t - 1) + vy(t)
vx(t) = vx(t - 1) + t + 1 + x'(t - 1) + y'(t - 1)
vy(t) = vy(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, vx, vy)(1) from this, and further substitute for vx, vy, which gives for t > 1

x'(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 constant c by substituting and trying to get the constant term to 0), and rewrite our equations to

d(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 + D

where 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) and q(t), it's best to use matrix multiplication), but I just wanted to do it this way :D

»
11 years ago, # |
Rev. 23   Vote: I like it 0 Vote: I do not like it

i 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.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    11 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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].

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well, you can use "Status filter"

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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:

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reduce any l or r to 10^7 if it is greater than 10^7. Try this case 1 2000 1 1424767024 1629755604