Sereja's blog

Codeforces Round #187 tutorial
By Sereja, 11 years ago, translation, In English

315A - Sereja and Bottles
Just check for each bottle, can I open it with another. In this task can pass absolutely any solutions.

315B - Sereja and Array
We will support all of the elements in the array, but also we will supprt additionally variable add: how much to add to all the elements. Then to add some value to every element we simply increase the add. In the derivation we deduce the value of the array element + add. When you update the item we put to a value, value that you need to put minus the current value of add.

314A - Sereja and Contest
Note that if we remove some of the participants, we never remove the participants with lower numbers as theirs amount will only increase. So just consider the sequence of all the participants, and if the participant does not fit we delete him.

314B - Sereja and Periods
It is clear that we can use greedy algorithm to look for the number of occurrences of the 2nd string in the first string, but it works too slow. To speed up the process, you can look at the first line of the string that specifies the second period. And the answer is divided into how many string you need to set the second string. Next, we consider our greedy algorithm. We are going by the first string, till we find the first character of the second string, then the second, third and so on until the last, then again find the first, second, and so the cycle. It is clear that if we stand in the same twice in a state in which the positions in the first string corresponds to one character string that determines the period and the position of the second string are the same, then we obtain the period. When we find this period, we can just repeat it as many times as possible.

To better understand, I advise you to read any accepted solution.

314C - Sereja and Subsequences
It is clear that we need to calculate the sum of the products of elements of all the different non-decreasing subsequences of given sequence. Let's go through the sequence from left to right and maintain the array q[i]: what means the sum of all relevant sub-sequences, such that their last element is equal to i. Clearly, if the next number is x, then you need to put q[x] = sum (q[1] + q[2] + ... + q[x]) * x + x. The answer to the problem is the sum of q[i]. To find all the amounts you can use Fenwick tree.

314D - Sereja and Straight Lines
Roll all at 45 degrees using the transformation: (x, y) -> (x ', y'): x '= x + y, y' = x-y. Next you need to place two lines parallel to the coordinate axes. Sort the points by the first coordinate. Next, we use a binary search for the answer. May we have fixed a number, you now need to check whether it is enough or not. Note that now we need to put two strips of width 2 * fixed amount that they would have to cover all the points. Suppose that some point should be close to the left side of the vertical strip, then for all points that do not belong to the strip we find the minimum and maximum second coordinate. If the difference between the found coordinates no more then 2 * fixed quantity, the strip can be placed, otherwise — no.

soon...

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

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

Excellent problem set. Kudos, Sereja

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Awesome problemset, In (314A — Sereja and Contest): How to avoid overflow of long long? (i-nDelete) * (n-i-1) * d[i]. This number can be really large, about 1e19. Thank you.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it -10 Vote: I do not like it

    You dont need to calculate this number. What you really need, is to calculate (i-nDelete) * (n-i) * a[i]. Just look at any solution.

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

      (i-nDelete) * (n-i) * a[i] seems to be 1e19 in worst case... Moreover, if rating was from 0, 1e19 would really appear in test like "0, 0, ..., 0, 1000000000, 0, ... 0" with 1000000000 in the middle of sequence. But rating is >= 1, and it doesn't work in test "1, 1, ..., 1, 1000000000, 1, 1, ... 1"...

      Could you (or anybody else) proof (or give a countertest) that honest solution with long long really works?

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

        (i-nDelete) * (n-i) = i * n — i * i + i * nDelete — n * nDelete = i * (n — i + nDelete) — n * nDelete

        If we want to reach the maximum, its better to minimize "n * nDelete", and maximize "i * (n — i + nDelete)". But, as we know, i <= n, so its better if nDelete == 0. (Because if we increase nDelete by one, we will increase all sum by i — n <= 0).

        It can be seen, that the maximum would be reached if (i = n/2) and (n * nDelete = 0). It meens that

        max = i * (n — i) — n * nDelete = (10^5)/2 * (10^5)/2 — 0 = (10^10)/4

        a[i] <= 10^9

        max * a[i] <= (10^19)/4 < MaxLL

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

          The problem is that maxn in this problem is 2*10^5, so in your argumentation we see max = (10^5) * (10^5) = 10^10 without any 2 or 4...

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

          n <= 2 * 10^5, and in your proof max = 10^5 * 10^5 — 0 = 10^10. Then max * a[i] <= 10^19 > MaxLL.

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

            Oh, yes...I thought that n doesnt exceed 10^5. Im sorry.

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

    It is very easy. You can calculate this number in double, becouse |K| is near 10^9.

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

      If we want to company a double number(indicated by D) with K, we can easily compare D and K with a little eps like 1e-10, right? If K is about 10^18, we can not do that directly. Anyway, Nice method to overcome the overflow of long long.

      → Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

In 314C — Sereja and Subsequences

There exists condition that some elements are same and the solution will probably make mistakes on it.Maybe we should use an extra array to deal with it.

example:

3

2 2 2

The right answer is 14,but it will print 26 with the solution See my codes for details

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

    I used the editorials idea and my solution prints 14 for your input. Maybe you thought three different indices will be updated for the input, yielding the array q[] with values 2, 6, 18 and final answer (of course wrong) 26. But in fact only q[2] will be updated thrice for the given input, 2, 6, 14 being its values and 14 being the last answer. Is it clear?

    → Reply
»
11 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I have checked some AC solutions for problem E. It seems that they all used an O(n^2) dp to walk through.

Is the model solution also this kind? I guess that it is not that suitable to put an O(n^2) solution with n = 10^5, though it runs faster than it might be expected.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    For my solution worst testcase is all '?'. So i just wrote it. Got 7 seconds local, TL on run. Some hacks -> 1.8 seconds local,2 on server. I think it's fair enough. Everybody can wrote this and check.

    If author solution is better, i can't understand why there was modulo 232. There was no chance using other modulo.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Could anyone explain DP approach in problem E?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it +10 Vote: I do not like it

    Let's assume that we have a brackets sequence(lowercase letter is an opening bracket, uppercase letter is a closing bracket).

    Let dp[i][j] = number of ways to reconstruct the string such way that first i characters are already processed and there're j opening brackets which are still not closed.

    Then dp[i][j] = dp[i — 1][j — 1] if s[i] is a lowercase letter, (it can just be a one more opening bracket)

    dp[i][j] = 25 * dp[i - 1][j - 1] + dp[i - 1][j + 1] otherwise. ('?' can be both: an opening and a closing bracket).

    Now it's clear how to calculate this dp in O(n^2) time. With some constant optimizations this solution gets AC.

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

Can you post the submission ID of your accepted solution for 314B — Sereja and Periods. Thanks in advance.

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

Roll all at 45 degrees using the transformation: (x, y) -> (x ', y'): x '= x + y, y' = x-y. can someone explain that to me please? i thought rotatating 45 degrees was something like multiply by (sina+cosa)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it 
    (x0, y0) --> (x1, y1)
x0 = r * cos(a), y0 = r * sin(a)
if a --> a + pi / 4
x1 = r * cos(a + pi/4) = r * (cos(a) * cos(pi / 4) - sin(a) * sin(pi / 4)) 
   = 1 / sqrt(2) * (r * cos(a) - r * sin(a)) = 1 / sqrt(2) * (x0 - y0).
y1 = r * sin(a + pi/4) = r * (sin(a) * cos(pi / 4) + cos(a) * sin(pi / 4)) 
   = 1 / sqrt(2) * (r * sin(a) + r * cos(a)) = 1 / sqrt(2) * (x0 + y0).

So, after rotating all the points 45 degrees and scale up all the coordinates with sqrt(2), (x0, y0) with be (x0 - y0, x0 + y0). 

After rotating, Manhattan distance ==> Chebyshev_distance. http://en.wikipedia.org/wiki/Chebyshev_distance
    → Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

For 314B, we don't need to find the "circle". I've read several AC codes and can hardly figure out their ways to find the circle. Finally I got the core that we can easily calculate how many letters of the String C can we get in [a,b].

Firstly we can nest two loops to find out: if we start with the ith character of String C and the first caracter of String A, how many following caracters of String C can match the caracters of String A one by one. It goes like this: for (int i=0; c[i]; i++) for (int j=0; a[j]; j++) if (a[j]==c[(i+f[i])%m]) f[i]++; //m is the length of String C

Secondly we simulate the process of [a,b]. Obviously, we start with the first caracter of String C. Then we add f[0] to ans. The second time we start with the (f[0]%m+1)th caracter of String C and we add f[(f[0]%m+1)%m] to ans that is f[ans%m]. Each time we plus a String A, we can easily know how many caracters can we match in String C by using array f. It goes like this: for (int i=0; i<b; i++) ans+=f[ans%m];

Finally we divide the ans by m and d and get what we want.

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

    Thanks for your explanation, It has confused me for a long time. Your explanation is quite understandable!

    → Reply