EQUAKE - Editorial

aug14
editorial
equake
lazy
medium
segment-tree

#1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Medium

PREREQUISITES:

Segment Trees/Lazy Propagation

PROBLEM:

Rotation by power F on an integer P is defined as circularly shifting the digits of number F times. Leading zeroes are maintained while rotation.
You have an array A of N(<=8*105) integers where Ai <104. There are M(<=2*105) queries. Queries are of two types:

  • Type 0, described by 0 Li Ri Fi: For each element on interval [Li, Ri] rotate it with power Fi.
  • Type 1, described by 1 Li Ri: Print the largest element on interval [Li, Ri].

EXPLANATION:

First let us discuss a simple problem where queries are of form “update(i,x) ie. update A*=x” and “query(l,r) print largest element in l to r”. This can be done straightaway by segment trees. You can learn about segment trees from here.
Now, suppose the update query requires us to update an interval in the array ie. add value to all elements in range l to r. For this we maintain at each node in the segment tree the value that is to be added in the interval. In lazy version we only mark those child which need to be updated and update it when needed. Before every update/query on an interval we propagate the lazy flag to the children if required. You can learn more on lazy propagation from here.

In our question, the update query is to circularly rotate all elements in a range. Note that a number of K digits is same after K circular rotations, so we can process update queries modulo length. But in our question we can have A_i of length 1 or 2 or 3 or 4 digits, so we process queries modulo LCM(1,2,3,4)=12.

We build a segment tree where each node stores a lazy flag which denotes by how much this segment is to be rotated. Also each node stores and array of size 12, where arr* denotes the maximum element in the interval denoted by current node where each element has been rotated by i.

This pseudo code will make it clear:

struct node
{
    int ar[12];
    // arr*=the maximum in the interval denoted by current node
    // where each element has been rotated by i.
    int p;
    // lazy flag for how many rotations are to be propagated
}

node tree[4*MAXN]; //declaring the tree

// we build the tree initially
build_tree(node, a, b)
{
    if(a==b)    // leaf node
    {
	    for i=1 to 11:
		    tree[node].ar*=rotate(A[a],i)  // A[a] rotated by i.
    }
    
    build_tree(node*2,a,(a+b)/2);   // build left child
    build_tree(1+node*2,1+(a+b)/2,b);   // build right child

    // initialise root value
    for(i=1 to 11)
        tree[node].ar*=max(tree[node*2].ar*,tree[1+node*2].ar*)
}

// rotate each element A* to A[j] by value
update(node, a, b, i, j, value)
{
    if(tree[node].p!=0) // this node needs to be updated
    {
	    //we need to rotate each element by tree[node].p
	    //this is equivalent to left circularly rotating the array tree[node].ar by tree[node].p
	    tmp=tree[node].ar
	    for i=1 to 11:
	        tree[node].ar* = tmp[(i + tree[node].p) % 12];

    	if(a!=b)    //propagate the rotation to children
		{
	        tree[node*2].p += tree[node].p; // Mark child as lazy 
	        tree[node*2].p %= 12; 
	        tree[node*2+1].p += tree[node].p; // Mark child as lazy 
	        tree[node*2+1].p %= 12; 
	    }

    	tree[node].p=0; //reset the lazy flag for current interval
    }
    if(current segment not with range [i,j])
	return;
    if(segment[a,b] within [i,j])
    {
	    rotate whole array tree[node].ar by tree[node].p;
	    if(a!=b)
		    mark children as lazy;
    	reset current node;
		return;
    }

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child

    for i=0 to 11
	    tree[node].ar* = max(tree[node*2].ar*, tree[node*2+1].ar*);       // Init root value
}

//query tree to get max element value in range [i,j]
query(node, a, b, i, j)
{
    if [a,b] out of range: return -inf;
    if(tree[node].p!=0) // node needs to be updated
    {
	    update array ar;
	    if(a!=b) mark children lazy;
	    reset current node;
    }

    if(segment[a,b] with [i,j])
	    return tree[node].ar[tree[node].p];

    q1= query(node*2, a, (a+b)/2, i, j); // Query left child
    q2= query(node*2, 1+(a+b)/2, b, i, j); // Query left child
    
    return max(q1,q2);
}

Each update and query takes O(log N) worst case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution


#2

@darkshadows

I have nearly done the same thing the only difference in my code and your code is that i have programmed the query in different way .

Now the problem is that I am getting Wrong Answer could anyone please help me to figure it out .

Here’s my code link:


#3

Hey, I was doing exactly the same way as described here, but getting TLE. Later I did some optimizations and got AC. But I still do not understand why this code doesn’t pass. Can someone help me.

http://www.codechef.com/viewsolution/4505322


#4

can someone explain me plz that why we are maintaining an array of size 12 = lcm(1,2,3,4). I know the number of digits are maximum 4, but why taking their lcm ???


#5

in above sudo code in function update(node, a, b, i, j, value)

if(segment[a,b] within [i,j])
{
rotate whole array tree[node].ar by tree[node].p;
if(a!=b)
mark children as lazy;
reset current node;
return;
}

here the whole array tree[node].ar should be rotated by value not by tree[node]
am i wrong ???


#6

What update array ar in query function means ?? Is it to rotate number or something else ??


#7

i think in worst case it will take 12*logN correct me if im wrong


#8

Since it covers all combinations. By example, say you have an array of 4 elements with one of each length. The index that will be in front will propagate as the following

  • 1 1 1 1 1 1 1 1 1 1 1 1
  • 1 2 1 2 1 2 1 2 1 2 1 2
  • 1 2 3 1 2 3 1 2 3 1 2 3
  • 1 2 3 4 1 2 3 4 1 2 3 4

Note that all columns are unique and that the next column will again be the same as the first.


#9

Yes i think it is a typo… It is not updated yet…