DIVQUERY - editorial

[utkarsh_lath]

Problem Link:

Practice
Contest

author: Tasnim Imran Sunny
tester: Roman Rubanenko
editorialist: Utkarsh Lath

Difficulty:

Medium

Pre-requisites:

offline processing of queries, factorizing small integers

Problem:

Given a sequence of N integers a[i], answer Q queries. Each query is described by three integers L, R, K meaning how many numbers in the sub-array from L to R are multiple of K.

Quick Explanation:

The queries can be answered online(meaning answering all queries, one by one, as soon as they are asked) as well as offline(meaning taking all the queries, processing them together and return their results), the offline solution goes as follows(online solution is also discussed later):

Each (L, R, K) query can be broken into two queries, query(L-1, K) and query(R, K). (query(L, R, K) = query(R, K) - query(L-1, K)).
The array a is processed from left to right and count[k] = number of multiples of k seen so far is maintained. Query (x, K) is answered immediately after a[x] is processed.

Explanation:

via offline processing

Given a single integer a[i], it would be easy to tell which k’s are divisible by a[i](by factorizing a[i]'s). Therefore, it would also be easy to answer the queries for a fixed array, because we could factorize each number and store the number of occurrences of each factor.

Therefore, the real hardness of problem lies in the fact that we are being queried arbitrary subarrays.

If a problem can be solved efficiently for an array, and more elements can be also be added to the array efficiently, without hurting the ability to solve the problem efficiently, then the problem can also be solved (offline) for arbitrary prefixes(or suffixes) of the array.

Our understanding of the problem so far satisfies the above property, so we can answer queries efficiently for any prefix of the array(I will answer the how part in a short while).

This means, we can answer queries which ask “how many numbers among the first L are multiples of K”

But, solving the above problem would be sufficient for us as well, because we can always break a query (L, R, K) into two queries (R, K) and (L-1, K), which asks for number of multiples of K among the first R and first L-1 numbers respectively.

Note that this technique works only because ‘+’ operation is invertible. Therefore, if the problem asked for “highest multiple of K in the interval L to R”, we could not use this method. The online method described in next section will be upto the task.

Offline processing

To accomplish solving the problem for arbitrary prefixes, given it can be solved for the array, can be done as follows:

sort all queries (x, K) in increasing order of x.
make an array named count of size K_max, and initialize all entries to 0
for i = 1 to N
    for each j | a[i] 
        count[j++]
    for all queries of the form (i, K):
        report answer of query = count[K]

For further details on how to implement this, look at testers’ or editorialists’ code.
The overall time complexity will be O(A_max^0.5 * N + Q log Q) if all factors are found by trial division.

This can be speeded up to O(A_max * log A_max + N * F + Q log Q), where F is the maximum number of factors any integer can have. This speed-up can be achieved by precomputing all factors of all numbers upto A_max.

for i = 1 to A_max
    for j = i; j < A_max; j+=i
        factors[j].push_back(i)

Both the solutions were acceptable. These two(with and without pre-computing factors) solutions were used by the Tester and the Editorialist respectively.

Online Algorithm

The main idea is that each number in the array can be multiple of at most 128 numbers(refer list of highly composite numbers). Therefore, for each value of K, we can store locations of all of its multiples, and answer queries by binary searching.

for i = 1 to N
    input a[i]
    for j in factors of a[i]
        occurances[j].push_ back(i)
for i = 1 to Q
    input L, R, K
    x = smallest index i such that occurances[K][i] >= L
    y = smallest index i such that occurances[K][i] > R
    // x and y can be found by binary search, or STL's [lower_ bound](http://www.cplusplus.com/reference/algorithm/lower_bound/) and [upper_bound](http://www.cplusplus.com/reference/algorithm/upper_bound/) functions
    report y - x

The problem setter used an offline variant of the above solution.

Related problems

For practice on offline processing of queries(need not be “easy”), refer to
1
2
3
4

Solutions:

Setter’s solution
Tester’s Solution
Editorialist’s Solution

[bugkiller]

“This can be speeded up to O(A_max * log A_max + N * F + Q log Q)” -> Can a solution not speeded up pass?

[manic]

#include
#include
#include
using namespace std;

int main()
{
int c,i,j,n,q,k,f,p,l,m;

cin>>n>>q;
int v[n];
bool v2[10000];
memset(v2,false,sizeof(v2));
m=0;
for (i=0;i<n;i++)
{
    cin>>v[i];
    if (v[i]>m)
    {
        m=v[i];
    }

}
for (i=0;i<q;i++)
{
    memset(v2,false,sizeof(v2));
    cin>>p>>f>>k;
    c=0;
    for(j=k;j<=m;j=j+k)
    {
        v2[j]=true;
    }


    for (j=p-1;j<f;j++)
    {
        int aux;
        aux=v[j];
        if (v2[aux])
        {
            c++;
        }

    }
    cout<<c<<endl;
}

}

[contesant]

there is also sqrt decomposition solition and it is easier to implement .

here is my solution :

dp[K][R] = how many number 'x' in range [1 , R] such that K | x .  " x = 0 (mod K)"
vector<int> occ[x] = sorted indexs of occurances of x .
so if input a = {1,9,3,4,3,1,4,3}; then occ[3] = {3 , 5 , 8};

for each query{
    if(K > 500)
        for(j = K ; j < 10 ^ 5; j += K)
            answer = answer + upper_bound(in occ[j] , R) - lower_bound(in occ[j] , L);
    else
        answer = dp[K][R] - dp[K][L - 1];
}

[utkarsh_lath]

Yes, as mentioned testers’ solution was not speeded up.

[sap88coder]

Loved the Editorial…fantastic job!

[mjnovice]

can someone please explain, the “tree” part of the setter’s solution ?

[jarekczek]

My n log n solution for n = 12M passes, while on my comp it runs for 7 seconds. Chef’s time limit is 1s. I’m afraid the max test 100K x 83160 is not included. Is it? If not, please add such test to practice room.

[sobhagya]

I came up with the offline logic apart from the fact that how to handle those large multiples but, after seeing that only at max 128 multiples can be there. I feel lame.

[betlista]

Same here. If I knew there are at most 128 divisors, maybe I’ll get AC.

[utkarsh_lath]

The setter is using binary indexed tree to find prefix sums.

[mrolympia]

please explain your approach .

[nishant_25]

from the above editorial what i got is that

first find all factors of a[i] and then check whether k is in that factor list or not if k is a factor than count++

first run a loop from 0 to L-1

find whether k is a factor of a[i] compute count 1

second run a loop from 0 to R

find whether k is a factor of a[i] compute count 2
then print count 1-count 2

am i thinking it right?
if not than please help
as i am unable to get editorial’s or tester’s or setter’s solution.

[arnabbcs08]

Certainly learnt a new method the offline version

[utkarsh_lath]

Yes @nishant_25 , you are right, you got the important part of it.
But your current complexity is O(N * Q). It can be speeded up, by doing your process simultaneously for all the queries. That is what Both tester’s and editorialist’s solutions do, by maintaining count for all possible k’s, as you loop from i to N.

[nishant_25]

can you please explain in more detail the part which says that process simultaneously for all the queries and maintain count for all possible k’s as you loop from 1 to n. because my above solution is still showing TLE.

[betlista]

@nishant_25: @utkarsh_lath was refering to your

for(j=p1;j<=p2;j++)

part. The last important thing is, that you can do is:

• for each divisor 2 - MAXA you can create list of indexes, that divisor divides
• if you process the input in order, those lists are ordered
• in those ordered lists you can use binary search…

[nishant_25]

u mean to say inside this loop build a list of factors of a[i] and in that ordered list search(using binary search) whether k is present or not
and repeat the above process for all elements from p1 to p2

[betlista]

No. You can do preprocessing when you load the array (it’s not changing). This part is in O(n*sqrt(MAXA)). Result of preprocessing is array of vectors, that for divisor k contains indexes of elements, divisor k divides.

Later when you have those list prepared, you can answer the query in O(log n) time using binary search in those lists…

[betlista]

For input from problem statement lists are (if I didn’t do mistake somewhere):

2: 4 5 7 8
3: 1 5 6 7 8
4: 4 7
5: 2
6: 5 7 8
7: 
8: 
9: 6
10:
11:
12: 7

• so there are two indexes in list 2 between 3 and 6 (first query)
• in list 4 is one index between 3 6
• list 3 - 4 items
• list 7 - 0 items
• list 6 - 1 item

and 2, 1, 4, 0, 1 is requested result