Facebook Hacker Cup 2013 Qualification Round(Solutions)

No intro is required.

you can find the qualification round problems in the below link.

https://www.facebook.com/hackercup/problems.php?round=185564241586420

Among the three problems, Problem1 and Problem2 are very easy if you come up with the logic soon.
And the third one is straight forward question with a very good logic.

Beautiful strings:
Like every one i started thinking very straight forward for this question, i.e. I need to process the sample data first to get the key string/algorithm as it is appears to be some kind of ciphering method is behind the scenes. 

ABbCcc with the answer 152, so i thought Ca(a)=24, Ca(b)=25 and Ca(c)=26.
So I was started thinking that its Caesar Cipher with shift 24.

So i continued to the second example. Kabooooommm...I was wrong :P

Still i was checking all the ciphering algorithms i knew substitution,transposition, rotational and Affine cipher etc etc.

Wait a minute, what if characters are assigned with values such that the Beauty(a.k.a. weight) of the string is maximized....it will become more beautiful right :P

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 501

char str[MAX];

int findBeautyOfString(){
 int d[26]={0};
 int sum=0,i=0;
 while(str[i]!='\0'){
  if(isalpha(str[i])){d[tolower(str[i])-'a']++;}
  i++;
 } 
 sort(d,d+26);
 for(int i=1;i<=26;i++){sum+=i*d[i-1];} 

 return sum;
}


int main(){
 //ios_base::sync_with_stdio(false);

 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//tweak to skip first line

 for(int t=1;t<=m;t++){
  cin.getline(str,MAX); 
  printf("Case #%d: %d\n",t,findBeautyOfString());
 }

}

Balanced Smileys
Simple logic. Process the characters in forward direction and based on the result of the remaining string evaluate whether it is a balanced string or not.
Its like balanced parenthesis problem, but here we need to ensure that additional decisions have made proper if a smiley is observed.

#include<iostream>
#include<sstream>
#include<fstream>

#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 101

char str[MAX];
int n=0;

bool balanced(int index,int right){
 if(index==n){
  if(right>0){
   return false;
  }
  return true;
 }

 if(str[index]==')' && right==0)  return false;
 if(str[index]=='(')  return balanced(index+1,right+1);
 if(str[index]==')')  return balanced(index+1,right-1);
 if(str[index]==':' && index<n-1 && (str[index+1]==')'||str[index+1]=='(')){
   return balanced(index+2,right)|balanced(index+1,right);
 }
 return balanced(index+1,right);
}


int main(){
// ios_base::sync_with_stdio(false);
 
 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//Tweak to skip first line due to the usage of scanf to get m.

 for(int i=1;i<=m;i++){
  cin.getline(str,MAX);
  n=strlen(str);
  printf("Case #%d: %s\n",i,(balanced(0,0)?"YES":"NO"));
 }
}

Find the Min
This is the problem in which i felt ashamed for never trying to code python.
And I came to know about the power of python.
Logic is simple but the implementation is cumbersome for this problem considering the large data set range, which will make you to go mad to think.

For this one, i have first implemented with the use of hash map in cpp.
But i adopted a brute force method to find the n elements.
For small data set it was working but when it comes to large data set, memory allocation problems(Out of memory and glibc errors as i was coding in ubuntu) etc etc.

/*
Based on Hashmap
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define INS pair<int,int>

using namespace std;


map<int,int> m1,m2;
map<int,int>::iterator it1,it2;



int findNthNumber(int n,int k,int a,int b,int c,int r){
 m1.clear();
 m2.clear();
  
 printf("FindNumber: %d %d %d %d %d %d\n",n,k,a,b,c,r); 
 m2.insert(INS(-1,-1));
 m2.insert(INS(9999999,9999));
 m1.insert(INS(0,a));
 m2.insert(INS(a,0));
 it1=m1.begin();
 for(int i=1;i<k;i++){
  m1.insert(INS(i,(((b*(*it1).second)+c)%r)));
  ++it1;
  m2.insert(INS((*it1).second,(*it1).first));
 } 
   for(;it1!=m1.end();++it1){
    cout<<(*it1).first<<"\t"<<(*it1).second<<endl;
   }

 map<int,int>::iterator min,max,del1,del2,last;
 min=max=m2.begin();
 max++;
 int i=k;
 while(i<n){ 
  while((*min).first+1==(*max).first){
   last=m2.end();
   --last;
   if(max==last){
    min=max=m2.begin();
   }else{
    min=max;
   }
   ++max;
  }
  
  while((*min).first+1<(*max).first){
   
   
   m1.insert(INS(i,(*min).first+1));
   m2.insert(INS((*min).first+1,i));
   ++min;
   
   del1=m1.find(i-k);
   del2=m2.find((*del1).second);
   
   
   m1.erase(del1);
   if(del2==min){
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if((*del2).first < (*min).first){
    min=del2;
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if(del2==max){
    ++max;
    if(max==m2.end()){
     min=max=m2.begin();
     ++max;
    }
    m2.erase(del2);
   }else{
    m2.erase(del2);
   }
   
   if(i==n-1){
    last=m1.find(i);
    return ((*last).second);
   }
   i++;
  }
 }


 return 0;
}

int main(){
// ios_base::sync_with_stdio(false);
 
  
 
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  int n=0,k=0,a=0,b=0,c=0,r=0;
  scanf("%d %d\n%d %d %d %d",&n,&k,&a,&b,&c,&r); 
  if(t==3) 
  printf("Case #%d: %d\n",t,findNthNumber(n,k,a,b,c,r)); 
 }
}

Later wrote the code in python, which was working fine but still the same result with large data set. But you know what , I liked python  and it is uber kewl :D.

A pattern was observed when i printed all the elements of the array in the end for a case, in the brute force method. Tada...!! there it is :D simplified. n I have google'd to find out more about "modulo randomization".

Start with 0, keep inserting the numbers if you don't find them last k. 

if you are deleting a front number which is less than the current number inserted you are free to insert that number just after the current number. 

Otherwise increase the number and continue with the procedure.

So on the whole next k+1 elements will have numbers from 0 to k(order will be different). But the same order will be repeated again for next k+1 elements also.
so you need to determine just k+1 elements from which you can make out the nth element.

/*
Based on Array
*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define __int64 unsigned long long int

#define KMAX 100001
#define MAX 200001


using namespace std;

__int64 n=0ULL,k=0ULL,a=0ULL,b=0ULL,c=0ULL,r=0ULL;
__int64 m[MAX]={0ULL};
int s[MAX]={0};

__int64 findNthNumber(){
 for(int i=0;i<MAX;i++){m[i]=0ULL;s[i]=0;} 

 __int64 sMax=k+k+1ULL;
 
 m[0]=a;
 if(m[0]<sMax) s[m[0]]++;
 for(__int64 i=1;i<k;i++){m[i]=(b * m[i-1] + c)%r;if(m[i]<sMax) s[m[i]]++;}
 
 __int64 i=0,j=k;
 
 while(j<sMax){
  while(s[i]==0){
   m[j]=i;
   s[i]++;
   if(m[j-k]<sMax){
    s[m[j-k]]--;
    if(m[j-k]<i && (s[m[j-k]]<=0)){ i=m[j-k]-1;}
   }
   i++;
   j++;
   if(j==sMax){break;}
  }
  i++;
 }
 
 return (m[k + (n - k - 1) % (k + 1)]);
}

int main(){
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%llu %llu\n%llu %llu %llu %llu",&n,&k,&a,&b,&c,&r); 
  printf("Case #%d: %llu\n",t,findNthNumber()); 
 }
}