CYCENCR - Editorial (Kodeathon 15.2)




Author: Satyam Gupta

Tester: Pulkit Sharma

Editorialists: Satyam Gupta




Segment Tree


You are given N integers, denoted by A_1, A_2, … , A_N representing the encoded message, and another N integers, denoted by R_1, R_2, … , R_N representing the operations performed on the original array which resulted in array A. You need to find the original array/message.


Let B be the original array on which operations R are performed sequentially from left to right to get array A.

An operation (Rotation Factor) R_i is performed on the i^{th} element i.e. B_i, this operation removes B_i from it’s position and inserts it on the position which is R_i positions left to i. From this we can conclude that the position of B_i can only be affected by operations from i to n, because insertions are to the left.

So, if we backtrack, we know that the position of the last element which is B_n is only affected by R_n, and by reversing that operation on A_n we get the original B_n. That means $(R_n

+1)^{th}$ term from end of array $A$ is $B_n$, and after that $(R_{n-1}

+1)^{th}$ term from end of array A is B_n and so on… (Note: We need to exclude the elements B_i to B_n in array A i.e. excluding all the elements we had found till this iteration from array A because every term B_i we find will be independent of all the terms beyond B_i).

For this algorithm to work, we will maintain a Boolean array D. If D_i is 1 that means element is included in the count of elements from the end, otherwise not. So, we need to build a segment tree on this array D, in order to query the count and also update the array when an element needs to be excluded.

This segment tree will have the usual implementation except a slight modification in the query function. Pseudo-code of the query function is as follows:
alt text

Result of this query function is stored in the global variable ans.

Using this segment tree, we can implement the above explained algorithm to attain the desired solution.
Complexity of this solution: O(NlogN)


Could be implemented using BIT for count and update queries.


using namespace std;


int N;
#define MAX 4000000 // Why? :D
#define inf 0x7fffffff

int arr[1000005],ans;
int tree[MAX];

 * Build and init tree
void build_tree(int node, int a, int b) {
    if(a > b) return; // Out of range

  	if(a == b) { // Leaf node
    		tree[node] = arr[a]; // Init value

	build_tree(node*2, a, (a+b)/2); // Init left child
	build_tree(node*2+1, 1+(a+b)/2, b); // Init right child

	tree[node] = tree[node*2] + tree[node*2+1]; // Init root value

 * Increment elements within range [i, j] with value value
void update_tree(int node, int a, int b, int i, int j, int value) {

	if(a > b || a > j || b < i) // Current segment is not within range [i, j]

  	if(a == b) { // Leaf node
    		tree[node] += value;

	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

	tree[node] = tree[node*2]+ tree[node*2+1]; // Updating root with max value

 * Query tree to get max element value within range [i, j]
int query_tree(int node, int a, int b,int val) {

	if(a > b ) return -inf; // Out of range

	if(a==b && arr[a]){
        return arr[a];

	if(tree[node]<val) // Current segment is totally within range [i, j]
		return tree[node];

    int q2 = query_tree(1+node*2, 1+(a+b)/2, b, val); // Query right child

	else if(q2>=val){
        return q2;
	int q1 = query_tree(node*2, a, (a+b)/2, val); // Query left child

	int res = q1+q2; // Return final result

	return res;

int d[1000005],op[1000005],sol[1000005];

int main() {
   // freopen("","r",stdin);


    int i;

    for(i = 0; i < N; i++) arr[i]=1;

    build_tree(1, 0, N-1);

    for(i = 0; i < N; i++)scanf("%ld",&d[i]);

    for(i = 0; i < N; i++)scanf("%ld",&op[i]);

        int ff=query_tree(1,0,N-1,op[i]+1);

	for(i = 0; i < N; i++) printf("%ld ",sol[i]);

	return 0;