fcspartakm's blog

By fcspartakm, history, 9 years ago, translation, In English

595A — Vitaly and Night

It was easy realization problem. Let's increase the variable i from 1 to n, and inside let's increase the variable j from 1 to m. On every iteration we will increase the variable j on 2. If on current iteration a[i][j] = '1' or a[i][j + 1] = '1' let's increase the answer on one.

Asymptotic behavior of this solution — O(nm).

595B — Pasha and Phone

Let's calculate the answer to every block separately from each other and multiply the answer to the previous blocks to the answer for current block.

For the block with length equals to k we can calculate the answer in the following way. Let for this block the number must be divided on x and must not starts with digit y. Then the answer for this block — the number of numbers containing exactly k digits and which divisible by x, subtract the number of numbers which have the first digit equals to y and containing exactly k digits and plus the number of numbers which have the first digit equals to y - 1 (only if y > 0) and containing exactly k digits.

Asymptotic behavior of this solution — O(n / k).

594A — Warrior and Archer

Let's sort the points by increasing x coordinate and work with sorted points array next.

Let's suppose that after optimal playing points numbered l and r (l < r) are left. It's true that the first player didn't ban any of the points numbered i l < i < r, otherwise he could change his corresponding move to point l or point r (one could prove it doesn't depend on second player optimal moves) and change the optimal answer. It turns out that all the points banned by the first player have numbers outside of [l, r] segment, therefore . We should notice that if the first player choosed any [l, r] for , he could always make the final points numbers located inside this segment.

The second player wants to make (he couldn't make less), what is equivalent if he always ban points inside final [l, r] segment (numbered l < i < r). As soon as the second player doesn't know what segment first player have chosen after every of his moves, he must detect a point which satisfies him in every first player choice. It's true number of this point is the median of set of point numbers left (the odd number) after the first player move. The number of moves of the first player left is lesser by one than moves of the second player, so the first player later could ban some points from the left and some points from the right, except three middle points. Two of it (leftmost and rightmost ones) shouldn't be banned by the second player as soon as it could increase the size of banned points from the left (or from the right), but third middle point satisfies the second player in every first player choice. This way the second player always bans the point inside final point segment.

Thus the answer is the minimum between every of values.

594B — Max and Bike

The main proposition to solve this problem — in the middle of every competition the sensor must be or in the top point of the wheel or in the bottom point of the wheel.

To calculate the answer we need to use binary search. If the center of the wheel moved on the distance c, then the sensor moved on the distance c + rsin(c / r), if the sensor was on the top point of the wheel in the middle, or on the distance c - rsin(c / r), if the sensor was on the bottom point of the wheel in the middle, where r — the radius of the wheel.

Asymptotic behavior of this solution — .

594С — Edo and Magnets

Let's find the centers of every rectangle and multiple them of 2 (to make all coordinates integers).Then we need to by the rectangle door, which contains all dots, but the lengths of the sides of this door must be rounded up to the nearest integers.

Now, let's delete the magnets from the door one by one, gradually the door will decrease. Obviously every time optimal to delete only dots, which owned to the sides of the rectangle. Let's brute 4k ways, how we will do delete the magnets. We will do it with helps of recursion, every time we will delete point with minimum or maximum value of the coordinates. If we will store 4 arrays (or 2 deques) we can do it with asymptotic O(1). Such a solution works O(4k).

It can be easily shown that this algorithm delete always some number of the leftmost, rightmost, uppermost and lowermost points. So we can brute how k will distributed between this values and we can model the deleting with helps of 4 arrays. This solution has asymptotic behavior O(k4).

594D — REQ

To calculate the answer on every query let's use the formula , where p1, p2, ..., pk — all prime numbers which divided n. We make all calculations by the module 109 + 7

Let's suppose that we solving problem for fix left end l of the range. Every query now is a query on the prefix of the array. Then in formula for every prime p we need to know only about the leftmost position of it. Let's convert the query in the query of the multiple on the prefix: at first init Fenwick tree with ones, then make the multiplication in points l, l + 1, ..., n with value of the elements al, al + 1, ..., an. For every leftmost positions of prime p make in position i the multiplication in point i on the . This prepare can be done with asymptotic , where C — the maximum value of the element (this logarithm — the number of prime divisors of some ai).

We interest in all leftmost ends, because of that let's know how to go from the one end to the other. Let we know all about the end l — how to update the end l + 1? Let's make the multiplication in the Fenwick tree in the point l on the value al - 1. Also we are not interesting in all prime numbers inside al, so let's make the multiplications in point l on the all values . But every of this prime numbers can have other entries which now becoming the leftmost. Add them with the multiplication which described above. With helps of sort the transition between leftmost ends can be done in .

To answer to the queries we need to sort them in correct order (or add them in the dynamic array), and to the get the answer to the query we will make iterations. So total asymptotic behavior of solution is iterations and additional memory.

594E — Cutting the Line

Let's describe the greedy algorithm, which allows to solve the problem for every k > 2 for every string S.

Let's think, that we always reverse some prefix of the string S (may be with length equals to one). Because we want to minimize lexicographically the string it is easy to confirm that we will reverse such a prefixes, which prefix (after reversing) is equals to the minimal lexicographically suffix of the reverse string S (let it be Sr) — this is prefix, which length equals to the length of the minimum suffix Sr (the reverse operation of the prefix S equals to change it with suffix Sr).

Let the lexicographically minimal suffix of the string Sr is s. It can be shown, that there are no 2 entries s in Sr which intersects, because of that the string s will be with period and minimal suffix will with less length. So, the string Sr looks like tpsaptp - 1sap - 1tp - 2... t1sa1, where sx means the concatenation of the string s x times, a1, a2, ..., ap — integers, and the strings t1, t2, ..., tp — some non-empty (exclude may be tp) strings, which do not contain the s inside.

If we reverse some needed prefix of the string s, we will go to the string S', and the minimal suffix s' of the reversing string S'r can't be lexicographically less than s, because of that we need to make s' equals to s. It will helps us to increase prefix which look like sb in the answer (and we will can minimize it too). it is easy to show, that maximum b, which we can get equals to a1 in case p = 1 и (in case if p \geq 2$). After such operations the prefix of the answer will looks like sa1saitisai - 1... sa2t2. Because t_{i} — non-empty strings we can not to increase the number of concatenations s in the prefix of the answer. The reversing of the second prefix (sai...) can be done because k > 2.

From the information described above we know that if k > 2 for lost string we need always reverse prefix, which after reversing is equals to the suffix of the string Sr which looks like sa1. To find this suffix every time, we need only once to build Lindon decomposition (with helps of Duval's algorithm) of the reverse string and carefully unite the equals strings. Only one case is lost — prefix of the lost string does not need to be reverse — we can make the concatenation of the consecutive reverse prefixes with length equals to 1.

Because for k = 1 the problem is very easy, we need to solve it for k = 2 — cut the string on the two pieces (prefix and suffix) and some way of their reverse. The case when nothing reverse is not interesting, let's look on other cases:

  1. Prefix do not reverse. In this case always reversing suffix. Two variants of the string with reverse suffix we can compare with O(1) with helps of z-function of the string Sr#S.

  2. Prefix reverse. To solve this case we can use approvals from the editorial of the problem F Yandex.Algorithm 2015 Round 2.2 which was written by GlebsHP and check only 2 ways of reversing prefix. We need for them to brute the reverse of suffixes.

It is only need in the end to choose from 2 cases better answer. Asymptotic behavior of the solution is O(|s|).

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is the solution for the third task correct ?

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

    From the other thread...

    Consider the case

    5
    1 2 3 4 5
    

    Their algorithm seems to give the wrong answer 2, while if player 1 banned a 1 or 5 at the beginning, it would be possible to get difference 1.

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

      Yes I think so, but I can not understand why the wrong solution is written? It looks like my solution on the contest maybe we miss some 'new' part.

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

        "n is always even". This statement was added to the new version of the problem. The greedy solution only works if n is even.

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

      In this problem ,n is even. So your case will not occur.

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I don't understand Div1 B. Please elaborate.

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

    Let's normalize d, r, v so that r = 1, d = dorig / rorig, v = vorig / rorig. This will not change the time taken. Observe that for every distance, the sensor rotates exactly 1 round so the sensor's position doesn't matter and time taken is 2π / v. We only need to consider the remainder of d / 2π, lets call this d.

    Since it takes (2π / v)s to rotate radians, rate of rotation is v radians/s. Then, if the sensor is at the topmost position at time t=0, at time t, it would have moved vt as a result of horizontal velocity from v, and sin(vt) as a result of rotation. (For 0 ≤ t ≤ π / v). So d = vt + sin(vt). Now, the speed of the sensor is fastest when it is at the top of the wheel and slowest at the bottom (you can check this by taking the 1st derivative of the equation), and speed vs time graph is symmetrical around t=0, therefore the sensor should be at the top of the wheel at the midpoint of the distance.

    Finally, to solve the problem, binary search the value of t to satisfy the equation x = vt + sin(vt), where x = d′ / 2, and multiply by 2 due to symmetry.

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

      "speed vs time graph is symmetrical around t=0, therefore the sensor should be at the top of the wheel at the midpoint of the distance."

      Why top at midpoint of distance?

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

        I want to explain it by using mathematical calculation. We start with the initial phase $$$\theta$$$. The equations of motion is: $$$s(t)=r\cos(\theta+\frac{v}{r}t)+vt$$$. We set $$$L=f-s$$$. Then we have:

        $$$vt+r(\cos(\theta+\frac{v}{r}t)-\cos\theta)-L=0\ ...(1)$$$.

        Consider the function $$$t=t(\theta)$$$. We want to minimize $$$t$$$, so we have $$$\frac{dt}{d\theta}=0$$$. Then we will get:

        $$$vt'+r(-\sin(\theta+\frac{v}{r}t)(1+\frac{v}{r}t')+\sin\theta)=0$$$.

        We have $$$t'=0$$$. So $$$\sin(\theta+\frac{v}{r}t)=\sin\theta\ ...(2)$$$.

        According to $$$(2)$$$, We will discussion two cases:

        Case 1. $$$\frac{v}{r}t=2k\pi$$$ with $$$k\in Z$$$. By considering $$$(1)$$$ we can get $$$L=vt$$$. So $$$L=2k\pi r$$$. Since $$$L$$$ and $$$r$$$ are positive integers, this case will never be happened.

        Case 2. $$$\theta+\frac{v}{r}t+\theta=(2k+1)\pi$$$ with $$$k\in Z$$$. By considering $$$(1)$$$ we have:

        $$$vt-2r\sin(k+\frac{1}{2})\pi \sin(\frac{v}{2r}t)-L=0$$$.

        Finally, we have: $$$vt\pm 2r\sin(\frac{vt}{2r})-L=0$$$.

        By analyzing the derivative we know that it is monotonic. So we can using binary to get the answer.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please explain Div2C. Grammar written is really really poor. How is it possible for player 2(archer) to always make n/2-1 consecutive bans? Also the answer of the question's test case doesn't satisfy max(arr[I+n/2]-arr[I]).

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

    As far as I understand, it must be minimum(arr[i+n/2] — arr[i]).

    And I'm not really sure about the explanation in the editorial, but it looks like the strategy of the second person is to remove the median. For example, if the second player had 7 places to choose from, he would pick 4th. If he keeps doing, he would get consecutive bans. (It will be obvious if you actually try this strategy) However, I'm not sure why this is an optimal solution.

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

      I think i figured it somehow. Let the final positions of warrior and archer be L and R. There cannot be more than n/2-1 bans between (L-R). Since that would include bans from warrior as well. But if warrior plays optimally he can always avoid a ban between L-R to reduce the distance L-R. So it shouldn't be hard to conclude that optimal strategy for warrior is if it bans all the corner-most positions from the array.

      Now the only case left is bans<=n/2-1 between L-R (Which are bans of archer only) Now we can prove that there cannot be less than n/2-1 bans between L-R. Since if archer plays optimally(i.e no matter what the warrior bans, if it bans the median) the archer can always make n/2-1 bans between L-R which is the best case for the archer.

      E.g :

      6 1 2 3 4 5 6 W: 6 A: 3 (Median of 1 2 3 4 5) W(Left 1 2 4 5): 1 A: 4 (Median of 2 4 5) Left 2 and 5, ALL the possible bans between 2 and 5 are of the Archer.

      So archer will always get the range L-R = n/2-1. Now best strategy for warrior is to chose such corner cases so that it minimizes this n/2-1 distance.

      Thus, the answer should be min(arr[i+n/2]-arr[i]). Tell me if i'm wrong. Thanks.

»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

In your A's tutorial, "Thus the answer is the maximum between every of …… values." It should be minimum, isin't it?

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

.

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

Div 1, C! Tried a lot but gives runtime error. Maybe stack space exhausts! Can anyone help me out ? Code

»
5 years ago, # |
Rev. 8   Vote: I like it +3 Vote: I do not like it

Step-by-step guide to solving 594D - REQ:

  1. Read input, including queries to solve them offline. Sort the queries by $$$l$$$, making sure to keep their original indices.

  2. Use Sieve of Erastosthenes to precalculate primes up to $$$1000$$$ $$$(\geq \lfloor \sqrt {\max a_i} \rfloor)$$$

  3. Use those primes to factorize all the values of $$$a$$$ (this step takes $$$O(168n)$$$). We want to store the results in two data structures:

    • An array of lists, indicating the distinct prime factors of each $$$a_i$$$. We'll call this $$$P$$$.
    • A map associating each prime factor to a queue of indices where the factor divides $$$a_i$$$. We'll call this $$$M$$$.
  4. Initialize a BIT or segment tree ($$$B$$$), that can calculate range products modulo $$$10^9 + 7$$$, with the values from $$$a_i$$$.

  5. Use $$$M$$$ to find the leftmost index for each prime factor. Multiply those positions in $$$B$$$ by $$$\frac {p-1} p$$$.

  6. We can now answer queries with $$$l = 1$$$ using $$$B$$$. To "advance" $$$l$$$ by $$$1$$$ to eventually answer the rest of the queries:

    • If using a BIT, clear / "one-out" the current index by multiplying $$$B_l^{-1}$$$ into $$$B_l$$$. (if using segment tree, you can just ignore past indices)
    • For each prime in $$$P_l$$$, advance their queues in $$$M$$$, multiplying the new leftmost indices in $$$B$$$ by $$$\frac {p-1} p$$$ if they exist. (There are at most $$$8$$$ primes per index.)

Sample: 65793661