sunny
BAN USER1) Calculate the length of the string.
2) Create an array str[26], and index being the key increment the value by '1' for each character in the given string.
e.g. gods, str['g''a']++, str['o''a']++, str['d''a']++, str['s''a']++.
O(N) time for this step.
3) Traverse the str array (which is now in sorted order of the characters), Starting from rank '1' give rank to each character in the str array.
thus,
str['d''a'] = 1
str['g''a'] = 2
str['o'  'a'] = 3
str['s'  'a'] = 4
4) Final step to calculate the rank of the permutation. Traverse the string again and do the following:
for(int i=0;i<N;i++){
rank += (str[input[i]  'a']1)*(factorial(Ni1));
//Update the rank of all those characters which are higher in rank than the present.
for(int j=i+1;j<N;j++){
if(input[j]>=input[i]) str[input[j]'a'];
}
}
The above can be modified to handle strings with repeated characters as well.
 sunny April 20, 2012The above problem becomes similar for finding the longest common subsequence between two array of integers...
The extension would be like longest common subsequence between a constant array (input) and a list of array integers (from file). The array from the list of array integers having the longest subsequence is our answer.
This approach will require negligible memory and is almost an inplace search algorithm. The complexity of the algorithm would be O(mn1+mn2+mn3...) where m is the length of the input string and n(i) is the length of the array of ith line integers.
This approach is much more easier to implement as compared to hasmap solution and has almost O(1) space complexity as compared to hashmap solution whose worst case space complexity when all the numbers in the list are distinct is O(n1+n2+n3...)
void order_numb(vector<int> array){
int N=array.size();
int result[3];
result[0]=1;
result[1]=1;
result[2]=1;
result[0]=array[0];
for(int i=1;i<N;i++){
if(array[i]<result[0] && result[1]==1){
result[0]=array[i];
continue;
}else if(array[i]>result[0] && (result[1] == 1  result[1]>array[i])){
result[1]=array[i];
continue;
}
if(array[i]>result[0] && array[i]>result[1]){
result[2]=array[i];
cout<<result[0]<<" "<<result[1]<<" "<<result[2]<<endl;
return;
}
}
cout<<"NO SUCH SUBSEQUENCE"<<endl;
}

sunny
April 03, 2012 An example of a simple pseudorandom number generator is the Multiplywithcarry method invented by George Marsaglia. It is computationally fast and has good (albeit not cryptographically strong) randomness properties (note that this example is not thread safe):[6]
m_w = <chooseinitializer>; /* must not be zero */
m_z = <chooseinitializer>; /* must not be zero */
uint get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32bit result */
}
The above code fails if number elements in increasing order is not equal to the number of of elements in decreasing order. The problem is not explicitly saying that till the mid of the array elements are in increasing order and after that in decreasing order.
The correct way to find would be to traverse the array the till the point a[i]<a[i+1]. As that point arrives, a comparison should be made between a[j] and a[j+1] whichever is bigger is the answer
P N algorithm shall work here.
 sunny March 23, 2016