Kostroma's blog

By Kostroma, 9 years ago, translation, In English


Create an array used of 100 elements. i-th element for the segment (i, i + 1).

For every student except Alexey set used[i]  =  true for each segment (i,  i  +  1) in the segment of that student. After that for each subsegment (i,  i  +  1) of Alexey's segment add 1 to result if used[i]  =  false.


First of all, calculate how many L's we can bring so that the result will not exceed N. It's .

Now, if R·K  ≥  N we may increase any of K numbers by 1. At some moment sum will be equal to N becase sum of K R's is greater than N. So answer in this case is YES.

If R·K  <  N, we can't get K or less numbers because their sum is less than N. But we can't get more than K numbers too, because their sum is more than N. So answer is NO.

Complexity: O(1) for every query. Overall complexity: O(t).


Let's factorize all n numbers into prime factors. Now we should solve the problem for every prime independently and multiply these answers. The number of ways to split pk into n multipliers, where p is prime, is equal to C(k  +  n  -  1,  n  -  1) (it can be obtained using the method of stars and bars, you can read about it here, choose 'combinatorics'). So we have a solution that needs time.


First of all, let's consider n  +  1  =  p is prime. Then we can prove by induction that the answer is . Base for p  =  3 is obvious. If this equality holds for p, and q is the next prime, then answer for q is equal to answer for p plus q  -  p equal summands , that is , that's we wanted to prove.

Next using that the distance between two consecutive primes not exceeding 109 does not exceed 300, we can find the answer as a sum of the answer for the maximal prime not exceeding n and several equal summands . We see that the denominator is a divisor of 2pq, which fits in long long.


We can write all vertices in the list in order of dfs, then the descendants of the vertex from a segment of this list. Let's count for every vertex its distance to the root level[v].

Let's create two segment trees st1 and st2. If we are given a query of the first type, in st1 we add x  +  level[vk to the segment corresponding to the vertex v, in st2 we add k to the segment corresponding to the vertex v.

If we are given a query of the second type, we write st1.get(v) - st2.get(v) * level[v].

The complexity is O(qlogn).

You can use any other data stucture that allows to add to the segment and to find a value of an arbitrary element.

Also there exists a solution using Heavy-Light decomposition.


Let's prove a useful fact: sum of number of invertions for all permutations of size k is equal to . The prove is simple: let's change in permutation p for every i pi to k  +  1  -  pi. Then the sum of number of invertions of the first and the second permutations is , and our conversion of the permutation is a biection.

Now we suppose that we are given a permutation of numbers from 0 to n  -  1.

Let's go at p from left to right. What permutations are less than p?

  • Permutations having first number less than p0. If the first number is a  <  p0, than in every such permutation there are a inversions of form (first element, some other element). So in all permutations beginning with a there are a·(n  -  1)! inversions of this from. Moreover, there are inversions not including the first element, their sum is sumAll[n  -  1]. Then, counting sum for all a we have inversions.
  • Permutations beginning with p0. At first, we should count the number of inversions, beginning in p0. There are cnt·p0 of this form, where cnt is the number of permutations beginning with p0 and not exceeding p. Then we should count the inversions not beginning in the beginning. But it is the same problem! The only exception is that if p1  >  p0, there are p1  -  1 available numbers less than p1, but not p1. So we get a solution: go from left to right, keep already used numbers in Fenwick tree, and then solve the same problem, assuming that the first number is not pi but pi - (the number of used numbers less than pi).

The last we should do is to count the number of permutations not exceeding the suffix of p and beginning the same. It can be precomputed, if we go from right to left. In this case we should do the same as in the first part of solution, but consider that the minimal number is a number of already used numbers less than current.


We will describe an algorithm and then understand why it works.

For every prime we will maintain a list of intervals. At the first moment for every pi we add in its list interval [0;ai), other primes have an empty list.

Then we go from big primes to small. Let's consider that current prime is p. If in its list there exists an interval [x;y), $x < k, y > k$, we divide it into two parts [x;k) and [k;y).

Then for every interval [x;y), x  ≥  k (in fact, in this case x  =  k) we add to the answer for p y  -  x. For intervals, where y  ≤  k, we add to list of every prime divisor of p  -  1 invterval [x  +  1,  y  +  1). If p  -  1 has some prime if more than first power, we should add this segment several times.

After that we should conduct a "union with displacement" operation for every prime which list was changed. If in one list there are 2 invervals [x,  y), [z,  t) so that y  ≤  z  >  x, we replace them with one interval [x,  y  +  t  -  z) (so we added t  -  z to the right border of the first interval). Then we go to next (lesser) p.

Why does it works? If we take function φ one time, for every prime p which divides n, n is divided by p and multiplied by p  -  1 (or, the same, by all prime divisors p  -  1 in corresponding powers).

Now we can observe that intervals in lists contains the numbers of iterations, when the number contains the corresponding prime number. Bigger primes do not affect smaller, so we can process them earlier. If after i-th iteration the number contains prime number p, after i  +  1-th iteration it contains prime divisors of p  -  1, and we add segments in accordance with this. The k-th iteration is the last, so the existence of the interval [k,  x) means that after k-th iteration we have (x  -  k)-th power of this prime. From this it is clear why we unite the intervals if that way.

Why does it work fast?

  1. Because we precalculated the minimal prime divisor of each number up to MAXPRIME using linear Eratosthenes sieve. (Well, it's not necessary)

  2. Because for each prime there's no more than intervals, because for each [a,  b) range . Practically there is no more than 6 segments at once.

Any questions about the editorial are welcome! Especially the English one :)

This post was restored from google cache, and I have edited formula once again. If you notice some mistake, please send be a private message.

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

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

Can you explain more deeply your Div2-D solution??? I do not understand your function. Did you make it approximately? Sorry if I am annoyed.I'm just newbie and I really want to learn new thing. :)

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

    No. It's an exact solution. We divide all the summands of the given sum to groups of equal summands. If p and q are consecutive prime numbers then there are q - p each of them equal to `. Notice that . Then we sum all of them.

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

      Ahhh I got it!!! Thank you very much. Nice problem.

9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Badly Editoral ever. !!!!

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

Can someone explain DIV1-A problem more deeply?
" Now we should solve the problem for every prime independently and multiply these answers "
why it's true ?

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

    because the way you distribute some prime factor say into the n slots is independent on the way you distribute another prime factor on these n slots

    you can think of a problem analogous to this problem suppose instead of the n slots in this problem we have n boxes and instead of prime factors we have different types of objects like balls,oranges,..etc.

    lets say the number of ways to distribute the balls to the boxes are 10 ways and there are 20 ways to distribute the oranges

    now we want to know overall how many ways to distribute both oranges and balls to the boxes

    you can notice for every way in the 10 ways to distribute the oranges you can do any of the 20 ways to distribute the oranges , so that's why we just multiply the answers because the way you distribute oranges has nothing to do with the way you distribute balls and you can use anyway of the first with anyway of the second.

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

Great problem set.. though editorial could be even better. :)

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

I am getting wrong answer for Div2-C. Could someone explain me why? Here's my submission — http://codeforces.com/contest/397/submission/12231922

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

Hello Everyone, can someone please explain me solution of Div.2 E with more details?

I'll be grateful if someone'll, any help is appreciated!

More exactly: how does it work & why does it work?