Shane
BAN USERimport java.util.*;
public class PermutationFromSignature {
static ArrayList<Integer> res;
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String input = sc.next();
res = new ArrayList<Integer>();
permGenSig(input);
for(int i = 0; i<res.size();i++){
System.out.print(res.get(i)+" ");
}
System.out.println();
}
static void permGenSig(String input){
if(input.length()==0) return ;
int i = input.lastIndexOf('I');
int n = input.length()+1;
if(i==-1){
for(int j = 0; j<=input.length(); j++){
res.add(n-j);
}
}
else{
if(i==0) {
res.add(1);
for(int l = 0; l<input.length();l++) res.add(n-l);
return;
}
permGenSig(input.substring(0, i));
int count = 0;
for(int j = i+1;j<=input.length();j++){
res.add(n-count);
count++;
}
}
}
}
Repsonjamramos45, Graphics Programmer at CGI-AMS
I am a strong writer with a passion for story-telling who has extensive experience of writing literary compositions, articles, reports ...
Te problem can be solved by creating a segment tree and storing the sorted array for every interval. This can be done in O(n^2). There are ~2n nodes in total. In the interval tree. For every interval, sorted output can be created from its children in O(n) just like its done in merge sort. So preprocessing takes O(n^2) time and O(nlogn) space.
- Shane October 06, 2015For every request can be broken down in intervals. For ex- an array of size 16 and request [4-12], request can be broken down into intervals [4-7],[8-11] and [12]. We need to find the Kth statistic of these sorted arrays. In general, a query can be broken down into atmax logn intervals. TC of finding Kth statistic of H sorted arrays of total size n is logn *H. Here H is logn hence, TC to serve a request is O(logn *logn).