KDATZERO - Editorial (Kodeathon 15.2)

PROBLEM LINK:

Practice

Contest

Author: Satyam Gupta

Tester: Pulkit Sharma

Editorialists: Satyam Gupta

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment Tree with Lazy Propagation, Number Theory

PROBLEM:

You are given N integers, denoted by A_1, A_2, … , A_N
Now you are given Q queries, each of whom is of following two types:
Type 1: 1 L R: Print the no. of trailing zeros (zeros in the end) in the multiplication of no.s in range [L,R] of array A[], i.e. no. of zeros in A_L * A_{L+1} * … * A_R
Type 2: 2 L R V: Multiply the all the numbers in range [L,R] with V.

EXPLANATION:

A number has trailing zeros equal to the no. of times it can be divided by 10 with remainder 0. Since 10 = 2*5, in other words we can say that a number has trailing zeros equal to the no. of times it can be divided by both 2 and 5 with remainder 0. So, we don’t need the number itself rather the no. of times it can be divided by 2 and 5 with remainder 0. So, if a number can be divided by ‘2’ for x times and by ‘5’ for y times, then that no. will have min(x,y) trailing zeros.
Since any element of array can go only upto 2000, we can calculate the no. of times a number can be divided by 2 and 5 for all numbers from 1 to 2000 using this pseudo-code:

 for i=1 to 2000:
  div2[i]=0
  div5[i]=0
  x=i
   while x%2==0 :
     div2[i]=div2[i]+1
       x=x/2

   while x%5==0 :
     div5[i]=div5[i]+1
       x=x/5

In other words div2[i] = no. of times 2 appear in prime factorization of i and similarly div5[i] = no. of times 5 appear in prime factorization of i

Now for example,
1500 = 2*2*3*5*5*5
So, div2[1500]=2 and div5[1500]=3
then, no. of trailing zeros in 1500 = min(2,3) = 2

Then for no. of trailing zeros in the multiplication of no.s in range [L,R],
x=div2[A_L]+div2[A_{L+1}]+...+div2[A_R]
y=div5[A_L]+div5[A_{L+1}]+...+div5[A_R]
No. of trailing zeros = min(x,y)

Since we need to work on ranges, we can use segment tree. For each node that represents range [L,R] we need to keep sum of the div2 and div5 from A_L to A_R.
For merging left and right nodes into the parent node, refer to the pseudo-code below:

 merge(parent,left,right):
   parent.two = left.two + right.two
   parent.five = left.five + right.five

Because update queries over ranges, we need to use lazy propagation on segment tree.
For type 2 queries of form (2 L R V), we will store the changes to be made (i.e. adding div2[V] and div5[V] to the node members “two” and “five” respectively of range [L,R]) seperately and then later during the Type 1 query, update the tree as needed.

Complexity of this solution:

For preprocessing O(NlogN) and for each query O(logN)

Final complexity = O(NlogN + QlogN)

AUTHOR’S AND TESTER’S SOLUTIONS:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

#define N 100000
#define MAX 500000

struct Tree_Node
{

    int two,five;

} tree[MAX],lazy[MAX],arr[N],dummy;

int div2[2005],div5[2005];

void build(int node, int a, int b)
{
    if(a > b) return;

    lazy[node].two=lazy[node].five=0;

    // Init Values
    if(a == b)
    {
        tree[node].two = arr[a].two;
        tree[node].five = arr[a].five;
        //cout<<a<<" "<<b<<"node:"<<node<<endl;
        return;
    }

    int lt=node<<1;
    int rt=lt+1;

    build(lt, a, (a+b)/2);
    build(rt, 1 + ((a+b)/2), b);

    //Init Internal nodes
    tree[node].two = tree[lt].two + tree[rt].two;
    tree[node].five = tree[lt].five + tree[rt].five;
}

void update(int node, int a, int b, int i, int j, Tree_Node val)
{

    int lt=node<<1; //left child = node*2
    int rt=lt+1;    //right child = node*2 + 1

    if(lazy[node].two != 0 || lazy[node].five != 0)
    {
        tree[node].two += lazy[node].two * (b-a+1);
        tree[node].five += lazy[node].five * (b-a+1);

        if(a != b)
        {
            lazy[lt].two += lazy[node].two;
            lazy[lt].five += lazy[node].five;
            lazy[rt].two += lazy[node].two;
            lazy[rt].five += lazy[node].five;
        }

        lazy[node].two = lazy[node].five = 0;
    }

    if(a > b || a > j || b < i)
        return;

    if(a >= i && b <= j)
    {
        tree[node].two += val.two * (b-a+1);
        tree[node].five += val.five * (b-a+1);

        if(a != b)
        {
            lazy[lt].two += val.two;
            lazy[lt].five += val.five;
            lazy[rt].two += val.two;
            lazy[rt].five += val.five;
        }

        return;
    }

    update(lt, a, (a+b)/2, i, j, val);
    update(rt, 1+(a+b)/2, b, i, j, val);

    tree[node].two = tree[lt].two + tree[rt].two;
    tree[node].five = tree[lt].five + tree[rt].five;
}

Tree_Node query(int node, int a, int b, int i, int j)
{
    int lt=node<<1;
    int rt=lt+1;

    if(a > b || a > j || b < i) return dummy;

    if(lazy[node].two != 0 || lazy[node].five != 0)
    {
        tree[node].two += lazy[node].two * (b-a+1);
        tree[node].five += lazy[node].five * (b-a+1);

        if(a != b)
        {
            lazy[lt].two += lazy[node].two;
            lazy[lt].five += lazy[node].five;
            lazy[rt].two += lazy[node].two;
            lazy[rt].five += lazy[node].five;
        }

        lazy[node].two = lazy[node].five = 0;
    }

    if(a >= i && b <= j)
        return tree[node];

    Tree_Node q1 = query(lt, a, (a+b)/2, i, j);
    Tree_Node q2 = query(rt, 1+(a+b)/2, b, i, j);

    if(q1.two==dummy.two) return q2;
    if(q2.two==dummy.two) return q1;

    Tree_Node res;
    res.two = q1.two + q2.two;
    res.five = q1.five + q2.five;

    return res;
}

int main()
{

	//freopen("zeros.in","r",stdin);
	//freopen("zeros.out","w",stdout);

    int i,n,q,x,l,r,c,t;
    Tree_Node val,ans;

    dummy.two=-1;

    //Calculating the count of 2 and 5 in prime factorization of a no. for no.s upto 2000
    for(i=2; i<=2000; i++)
    {
        x=i;
        while(x%5==0)
        {
            div5[i]++;
            x/=5;
        }
        while(!(x&1))
        {
            div2[i]++;
            x/=2;
        }

    }
	cin.sync_with_stdio(false);
	cin.tie(NULL);
    //scanf("%ld",&t);
    cin>>t;

    while(t--)
    {
        //scanf("%ld%ld",&n,&q); //Input n and q
        cin>>n>>q;

        for(i=0; i<n; i++)
        {
            //scanf("%ld",&x); // Input a[i]
            cin>>x;

            //Only the count of 2 and 5 in it's prime factorization is needed
            arr[i].two=div2[x];
            arr[i].five=div5[x];
        }

        build(1, 0, n-1); //Build segment tree

        for(i=0; i<q; i++)
        {
            //scanf("%ld%ld%ld",&c,&l,&r);
            cin>>c>>l>>r;

            l--;  //Decrease by 1 since array is 0-indexed
            r--;

            if(c==1)
            {
                ans=query(1, 0, n-1, l, r); //Query range [l, r] for total no. of twos and fives
                printf("%ld\n",min(ans.two,ans.five));
            }
            else
            {
                //scanf("%ld",&x);
                cin>>x;

                val.two=div2[x];   //Only the count of 2 and 5 in it's prime factorization is needed
                val.five=div5[x];

                update(1, 0, n-1, l, r, val); // Increment range [l, r] by twos and fives of 'val'

            }
        }
    }
    return 0;
}
1 Like

solution link is not working :frowning:

//