ANUAAA - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

Mo’s algorithm
Number Theory

PROBLEM:

For a prime P and array A, F(A, L, R, P) denotes number of A[i], (L ≤ i ≤ R) divisible by P. Given an array A of size N and another array B of size M, find
imag
where,
L = (B[i] + B[j]) N** **R = (B[i] - B[j] + N) N

EXPLANATION:

Read post in pre-requisite if you don’t know about Mo’s algorithm.

If we note that L and R being generated here are random. So, we’ll have to calculate F(A, L, R, P), for each query. So our problem now is that:
Given M * M queries of form L, R, for each query find Sum[F(A, L, R, P)2] for all primes p less than 106.

Now, we can note here that if we have answer for query (L, R), how fast can we calculate answer for (L, R+1). Suppose we have an array cnt, where cnt[i] denotes the F(A, L, R, i) (i are primes). So our answer here is sum{cnt[i]2} for all i primes.
Now, we have to make certain changes in cnt array since a new number A[R+1] has been added.

ans = answer for (L,R)
for all p = prime factors of A[R+1]:
    //update the answer
    //answer is affected due to change in cnt[p]
    ans -= cnt[p]*cnt[p]
    cnt[p]++;
    ans += cnt[p]*cnt[p]
print ans

And, similarily we can also remove a number from our answer.
In complexity: O(number of prime factors), we can insert/delete a number from our data structure.
So, basically, what we have here is a data structure in which we can insert/delete a number in O(K), where K < number of distinct prime factors of number(worst case 7).
If we have all the numbers in range [L, R] organized in our data strcture, we can transform to [L’, R’] in O((|L-L’| + |R-R’|) * K).

Now, what we’ll use here is popularly known as Mo’s algorithm among chinese. It’s a offline query algorithm. We process all our queries in such a order such that transform cost is minmised.
Here’s the sorting function we use:

//we break array A into sqrt(N) chunks.
S = the max integer number which is less than sqrt(N);
bool cmp(Query A, Query B)
{
    //if starting point belongs to different chunks
    //sort on increasing starting point
    if (A.l / S ！= B.l / S) return A.l / S < B.l / S;
    
    //if starting point is present in same chunk
    //sort according to decreasing ending point.
    return A.r > B.r
}

We sort all the queries by this comparator, and process all queries in order. It can be proved easily that the total transform cost is O(N * sqrt(N) * K).

SOLUTIONS:

Setter’s solution
Tester’s solution

2

Practice link redirects to contest link for some problems

3

Please check now.

4

A solution that doesn’t uses the sqrt(N) decomposition:

We can first sort the array b and then just process the queries in original order, that is:

for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++)
        process query L = b[i] + b[j], R = b[i] - b[j]

We can process queries just the same way it is described in editorial, that is doing O((∆L + ∆R) · K) stuff to move between adjacent queries.

One can prove that due to sorted order of b the total complexity will be O(N · M · K), but with pretty big constant factor.

2 Likes