PROBLEM LINK:
Author: Satyam Gupta
Tester: Pulkit Sharma
Editorialists: Satyam Gupta
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Segment Tree
PROBLEM:
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.
EXPLANATION:
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 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:
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)
ALTERNATIVE SOLUTION:
Could be implemented using BIT for count and update queries.
AUTHOR’S AND TESTER’S SOLUTIONS:
#include<iostream>
#include<algorithm>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
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
return;
}
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]
return;
if(a == b) { // Leaf node
arr[a]+=value;
tree[node] += value;
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
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]){
ans=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
if(q2<val)
val-=q2;
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("crypto.in","r",stdin);
//freopen("crypto.out","w",stdout);
cin>>N;
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]);
for(i=N-1;i>=0;i--)
{
int ff=query_tree(1,0,N-1,op[i]+1);
sol[i]=d[ans];
update_tree(1,0,N-1,ans,ans,-1);
}
for(i = 0; i < N; i++) printf("%ld ",sol[i]);
return 0;
}