witua's blog

Codeforces Round #157 — Editorial
By witua, 12 years ago, translation, In English

259A - Little Elephant and Chess

Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.

259B - Little Elephant and Magic Square

Since each number is less than or equal to 105, you can loop all possible a1, 1 values, the rest of cells can be calculated from this.

258A - Little Elephant and Bits

It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.

258B - Little Elephant and Elections

First of all, lets think about the problem of finding array ci — the number of integers from 1 to m such, that the number of lucky digits is equal to i. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].

It can be solved directly using DP, but to simplify a bit you can use brute force (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 109 + 7.

Consider that you have group of size t, each number of which should contain l lucky digits. That it's pretty easy to understand that the number of assignment is equal to (cl) * (cl - 1) * (cl - 2) * ... * (cl - t + 1).

258C - Little Elephant and LCM

The complexity of the possible solution is O(n * sqrt(n) * log(n)). You can see that statement lcm(b1, b2, ..., bn) = max(b1, b2, ..., bn) is equal to statement "All the numbers b1, b2, ..., bn must divide max(b1, b2, ..., bn)". You can iterate that max(b1, b2, ..., bn), let it be equal to m. Find all divisors of m and sort them — p1, p2, ..., pk. For each i between 1 and k you can find (using simple DP) the number of numbers aj that pi ≤ aj < pi + 1 (if i = k than pi + 1 = max(a1, a2, ..., an) + 1), denote it as qi. Then the reuslt is equal to 1q1 * 2q2 * 3q3 * ... * pqp, because for each of the q1 numbers there is 1 way to assign, for each of q2 numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some i such bi = m. Hance you need from the last multiplier (pqp) subtract (p - 1)qp — all the ways that there is no number equal to m.

258D - Little Elephant and Broken Sorting

258E - Little Elephant and Tree

Very useful thing in this problem is ordering all vertices in DFS order (preorped). After that any subtree can be represented as a some sequence of continuous vertices. Consider that we have some fixed vertex v. Which vertices should be included in cv? Obviously, if in the path from the root to v is some non-empty vertex (i. e. such that has at least one integer in its list) than each vertex from substree v should be included in ci, but since we now working with preorder traversal of the tree, we consider that every vertex from some segment [lv, rv] must be included to ci. More generally, let for each vertex keep some set of segments (lk;rk). If on the i-th operation we have two vertices a and b, we add segment (lb;rb) to vertex a, and (la;ra) to vertex b. Also for each vertex i (i = 1..n) we add segment (li;ri), where (li;ri) is a segment in our preored traversal for subtree i. After that, you can see that, if we unite all segments from all vertices on the path from the root to some vertex v, we find the result for v, which will be the size of the resulting set.

So now we need some data structure that would support three operations: add(l, r), subtract(l, r), count(). The first one should add 1 to all positions from l to r, inclusive. The second should subtract 1 from all positions from l to r, inclusive. The last should count the number of non-zero element. This all can be done either with segment tree or sqrt-decomposition.

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

Comments Comments (37)
| Write comment?
»
12 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Actually, the complexity of your solution to the problem C is O(NsqrtN + Nlog2N) and it can be decreased to O(Nlog2N). The reason is that the total number of divisors of all numbers between 1 and N, inclusive, is O(NlogN).

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

    I'm still unclear why the total number of divisors of all numbers between 1 and N, inclusive is O(NlogN). Can you explain it a bit more? Sorry for a naive question and my bad english!

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

      A very naive way to think of it is this:

      You can calculate all divisors of all numbers from 1 to n using a sieve whose complexity is O(nlogn). Also, in each step, you calculate exactly one divisor of a number. So, there can only be O(nlogn), The sieve can be visualized as:

      for(int i = 2; i <= n; i ++) {
   for(int j = i; j <= n; j += i) {
      //now we know that i is a divisor of j
   }
}
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks a lot. now I got it!

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

div1 c can be solved in O(nlogn). See my submission

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

    Isn't your submission O(Nlog^2N). Aren't you basically using a modified sieve with exponentiation at every step?

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

      You are right, I CONSIDERED pow as O(1), while in fact it is O(logn). But there is a way to make it faster, because the number of factors of N is between O(sqrt(n)) and O(logN), so when we use pow(x,y), x has a upper bound and y is not greater than n, so we can calculate pow(x,y) before(in between O(nlogn) and O(n*sqrt(n)), and I think it's more close to (nlogn) ), and when we use it, it only takes O(1) time.

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

Seems like there's a little typo in the explanation for Div2 E/Div1 C. It should be The result is equal to 1q1 2q2 ...  kqk since i takes value between 1 and k, not p

Btw, thanks for the editorial. My solution for Div1 C is the same but I forgot to handle the case where the subtraction yields negative value :(

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

nice problems, especially problem D div 2, just in my opinion. :)

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

Problem Div1-B How could the first part be calculated using dp ? explain

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

    One of the solution is like this:

    Suppose m has n digits and di is the i-th digit of m. Let f(i, j, 0) be the number of integers, with i digits maximum, that have exactly j lucky digits and are less than d1d2... di (that is, the first i digits of m) and let f(i, j, 1) be the number of integers, with i digits maximum, that have exactly j lucky digits and equal d1d2... di, i ≥ j. It's easy to see that f(i, j, 1) is either 0 or 1. Let's also assume that we already have two functions, N(x) and L(x), that compute the number of non-lucky and lucky digits less than x respectively.

    Base cases:

    1. f(1, 0, 0) = N(d1)

    2. f(1, 1, 0) = L(d1)

    3. f(1, 0, 1) = 0 if d1 is a lucky digit, 1 otherwise

    4. f(1, 1, 1) = 1 if d1 is a lucky digit, 0 otherwise

    Transitions:

    1. f(i, j, 1) = 1 if there are exactly j lucky digits in d1, d2, ... di, 0 otherwise

    2. If j = 0 then

    f(i, j, 0) = 8f(i - 1, j, 0) + N(di)f(i - 1, j, 1)

    else

    f(i, j, 0) = 8f(i - 1, j, 0) + N(di)f(i - 1, j, 1) + 2f(i - 1, j - 1, 0) + L(di)f(i - 1, j - 1, 1)

    Then, the number of integers between 1 and m (inclusive) that have exactly k lucky digits is f(n, k, 0) + f(n, k, 1), minus 1 if k = 0 since we don't want to count the number 0 in.

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

Div2 B can be solved in O(1) even if the range of the numbers become unlimited.

x a b c y d e f z

Note that a+b+c+d+e+f+x+y+z = 3s where s is the sum of a line. But x+y+z = s, so a+b+c+d+e+f = 2s. Aka the total sum of the numbers given is 2s. Divide by 2 to get s.

Now the rest is easy: x = s-a-b, y = s-c-d, z = s-e-f.

This is correct as long as the given numbers are indeed correct (a+f = b+e = c+d). This also proves that there is only one solution.

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

In problem 258A, for the catchy case (all 1,such as 111111) input data set is may be wrong. Because my friend's accepted code gives equal number of one as like as input. he hasn't handle such case. My friend's handle is "zitu_cuet" (without quote). Or you can see this link... My friend's submission's link . For input "1111" his output is "1111". But codeforces compiler gives "111". You can see pretest 10 or 31. As he didn't handle such case how can these output come ???

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

    I think his solution is right because in codeforces any uninitialized variable becomes 0 and when he makes j=0 , p is 0 and he doesn't add the first 1. I'm not exactly sure but I think this is the only reasonable explanation.

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

      Humm... It's clear to me now.... :) this matter was not known by me.... thanks for your reply :)...

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

Hey , Is there not a direct way to reach the editorials of any particular contest whether new or old . After much time searching the editorials on the site , I found the way to here by a link in Recent Actions ... There should be some other way too to reach an editorial of a particular contest . Please tell .

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

    Some of the contests have their materials linked under the Contest Materials at the bottom right of the page, like here. Administrators, contest authors and red-rated coders can add missing links.

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

How to solve second part of problem B using dynamic programming? How to take into account that all parties must have distinct numbers?

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

    Consider that the party of LE has number with c lucky digits. Than there are 6 more paries left. No you have only numbers with 0, 1, .., c - 1 lucky digits, each group is intependent. Hence the state of DP is [current number of lucky digits (gropus that we consider)][current sum of lucky digits][current number of free (such that no number is assigned yet) parties]. Let it be [d][sum][cnt]. On such state you can iterate number k (0 ≤ k ≤ cnt) — the number of parties that would have number with exactly d lucky digits. You should place that k numbers among cnt that are left. This gives you a multiplier C(cnt, k). The number of assignment is (as in the statement) cd * (cd - 1) * ... * (cd - k + 1). Hance you go from [d][sum][cnt] into [d-1][sum + k*d][cnt  -  k] with multiplier C(cnt, k) * cd * (cd - 1) * ... * (cd - k + 1).

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

How to solve div1 E ???

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

I wonder if it is possible for you to include links to relevant code implementations of the algorithms you've described above in your editorial please?

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

    yup it would be great if there are links to some well commented implementations!

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

If it's possible, report someone solution of task D(div 1), please.

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

    I am also very interested. The problem seems to be very beautiful and hard. Even some idea will be a good thing :)

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

      I have solution already:)
      Let's support F[i][j] = probability that a[i]>a[j].
      At first. F[i][j]=1, if a[i]>a[j] and 0 else.
      When we need to swap a[x] and a[y] with probability= 0.5:
      It's logically that for (i!=x,y): F[i][x]=F[i][y]= 0.5*F[i][x] + 0.5*F[i][y].(Because probability that on x-th position will be a[x] or a[y] will be same).
      Also logically: F[x][i]=1-F[i][x], F[y][i]=1-F[i][y]. F[x][y]=F[y][x]=0.5.
      Answer=sum F[i][j] for i<j.

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    Denote d[i][j] (i < j) as probability of p[i] > p[j].
    How can we count array d after swap p[a] and p[b]? (a < b)
    Just do the following for all 0 ≤ c < n:
    d[c][a] = d[c][b] = d[c][a] + d[c][b], c < a;
    d[a][c] = d[b][c] = d[a][c] + d[b][c], b < c;
    d[a][c] = d[a][c] + (1 - d[c][b]), a < c < b;
    d[c][b] = (1 - d[a][c]) + d[c][b], a < c < b;
    d[a][b] = .

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

How can we realise segment tree such , that we can count number of non-zero elements in LogN time , also we need to increase all elements by 1 on interval or decrease by 1 also in LogN time.

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

    Let's calculate the amount of zeros: for this you can calculate minimum on the segment and the amount of this minimum, because all values (in problem E Div1) are non-negative.

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

      haha , I got it now ,nice way :)

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

      What if the value in the problem can be negative, and is still asking for the amount of non-zero elements, can it still be solved??

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Sorry, all my solutions in previous rev. were wrong :-(
        I'm only know obvious solution using sqrt-decomposition and with complexity O(logNsqrtN) :-(

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

          Using nsqrt(n) memory(feasible only if enough memory). per-query time can be made sqrt(n). For each block store what is number of elements =i for each i(possibly using coordinate compression in first place). Then for updates which cover entire block just update offset. Else update the entire block(only zeroing out previous elements and updating new elements in sqrt(n) time). For query directly return offset result in each block.

          Have you figured out a per-query log(n) solution?

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

Please anyone describe the proof of solution problem div2 e/div1 c . thanks in advance.

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

I am not able to understand editorial for DIV 1 C anyone can explain me. Thanks in advance:)

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

Something about the execute time of python3 with the problem C.Actually,my solution is O(Nsqrt(N)+NlogNlogN),although I use the mutithreading by python3,I just get TLE...maybe I just don't get the better algorithm with problem C...

→ Reply