[Practice Mode] HackerCup-2013 Round-1 :: DeadPixel

Lession-11: General approach is always successful. For this problem,Just imagine how 'ROBO't Scans the book.
i.e. From left to right or top to bottom or right to left or bottom to top.
If you don't know yet, watch ROBO Movie :P ...Seriously.

Lession-12: Set is another beautiful STL Container that you need to know.

Lession-13: If you want to make use of sort at the best, I recommend not to use any comparator function. Believe it or not It runs out of memory if you use any comparator function.

Lession-14: Love C++ More and More, especially when there is no need to write Deque or Queue or Hashmap or Multimap or Set and other Standard function. Of course there are many languages which are having rich libraries but C++ has its own mark. May be my love towards pointers :P is coming out in dis way :D.

Lession-15: Jintak tak Jintak...Jinta...Jinta tha Thahhh...!! Working on Other problems.

// =====================================================================================
//       Filename:  deadPixel.cpp
//    Description:  
//        Created:  02/07/2013 04:06:57 PM
//         Author:  BrOkEN@!
// =====================================================================================

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

#define TIMER 1
#define MAX 40000

#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
#define FOREACH(it,a) for(typeof(a.begin()) it=a.begin(); it != a.end(); ++it) 

using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef deque<PI> DQ;
typedef long long LL;

int W=0,H=0,P=0,Q=0,N=0,X=0,Y=0,a=0,b=0,c=0,d=0;
VI v;
DQ xs;


int getPossible(){
	set<int> k;
	FOREACH(i,xs){k.insert((*i).second);}
	k.insert(H);	
	
	int d=0,pre=-1;
	FOREACH(i,k){
		if((*i)-pre-1 >= Q){
			d+=((*i)-pre-1)-Q+1;
		};
		pre= *i;
	}

	return d;
	
}

LL solve(){
	v.clear();

	v.push_back(PI(X,Y));
	FOR(i,1,N-1){
		v.push_back(PI((v[i-1].first * a + v[i-1].second * b + 1) % W ,(v[i-1].first * c + v[i-1].second * d + 1) % H));	
	}	
	
	sort(v.begin(),v.end());

	LL sum=0LL;
	xs.clear();
	
	VI::iterator it=v.begin();
	FOR(d,0,W-P){
		while(!xs.empty() && ((xs.front()).first<d)){
			xs.pop_front();
		}

		while(it!=v.end() && (*it).first<=P-1+d){
			if(	(xs.empty()) || 
				((xs.back()).first<(*it).first) || 
				(((xs.back()).first==(*it).first) && ((xs.back()).second<(*it).second))
			){
				xs.push_back(*it);
			}
			++it;
		}
		sum+=(LL)getPossible();
	}
	return sum;
}

int main(){
#ifdef TIMER
	clock_t t=clock();
#endif
	int T=0;
	scanf("%d",&T);
	FOR(t,1,T){
		scanf("%d %d %d	%d %d %d %d %d %d %d %d",&W,&H,&P,&Q,&N,&X,&Y,&a,&b,&c,&d);
		printf("Case #%d: %lld\n",t,solve());
	}

#ifdef TIMER
	printf ("It took %f seconds to run.\n",((float)(clock()-t))/CLOCKS_PER_SEC);
#endif	
	return 0;
}

[Practice Mode] HackerCup-2013 Round-1 :: Security

Lession-7: Match finding is always an easy job, If you know HopCraft-Karp algorithm.

Lession-8: Lexicographic means Lexicographic, nothing else. You have a very small meta-dictionary Keep that in Mind. :P

Lession-9: Continue to read standard algorithms. :D

Lession-10: If you think that it can be fixed, It can be fixed.

// =====================================================================================
//       Filename:  security.cpp
//    Description:  
//        Created:  02/03/2013 01:22:50 AM
//         Author:  BrOkEN@!
// ====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>

#define TIMER 1
#define NIL 0
#define INFINITE 1000
#define KMAX 101
#define MMAX 51
#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef set<VI> vS;

char k1[KMAX],k2[KMAX];
int m=0,l=0;
bool dp[MMAX][MMAX];
int H[2*MMAX][3];



bool compare(int a,int b){
 int x=l*a,y=l*b;
 for(int i=0;i<l;i++){
  if( (k1[x+i]!='?') && (k2[y+i]!='?') && (k1[x+i]!=k2[y+i])){
   return false;
  }
 }
 return true;
}


bool bfs(){
 queue<int> Q;
 FOR(v,1,m){
  if(H[v][1]==NIL){
   H[v][0]=0;
   Q.push(v);
  }else{
   H[v][0]=INFINITE;
  }
 }
 H[NIL][0]=INFINITE;
 while(!Q.empty()){
  int v=Q.front();Q.pop();
  if(H[v][0] < H[NIL][0]){
   FOR(u,1,m){
    if(v<=m && dp[v-1][u-1] && H[H[u+m][2]][0]==INFINITE){
     H[H[u+m][2]][0]=H[v][0]+1;
     Q.push(H[u+m][2]);
    }else if(v>m && dp[u-1][v%m -1] && H[H[u][2]][0]==INFINITE){
     H[H[u][2]][0]=H[v][0]+1;
     Q.push(H[u][2]);
    }
   }
  }
 }
 return (H[NIL][0]!=INFINITE);
}


bool dfs(int v){
 if(v!=NIL){
  FOR(u,1,m){
   if(v<=m && dp[v-1][u-1] && (H[H[u+m][2]][0]==H[v][0]+1) && dfs(H[u+m][2])){
    H[u+m][2]=v;
    H[v][1]=u+m;
    return true;
   }else if(v>m && dp[u-1][v%m -1] && (H[H[u][2]][0]==H[v][0]+1) && dfs(H[u][2])){
    H[u][2]=v;
    H[v][1]=u;
    return true;
   }
  }
  H[v][0]=INFINITE;
  return false;
 }
 return true;
}

bool hopCK(){
 FOR(i,0,2*m){H[i][0]=INFINITE;H[i][1]=NIL;H[i][2]=NIL;}
 
 int matching=0;
 
 while(bfs()){
  FOR(v,1,m){
   if((H[v][1]==NIL) && dfs(v)){ matching++; }
  }
 }

 return (matching==m); 
}

bool solve(){
 l=strlen(k1)/m;
 
 FOR(i,0,m-1){FOR(j,0,m-1){dp[i][j]=compare(i,j);}}

 if(!hopCK()){return false;} // Do you there won't be a matching exists, then just quit :P

 FOR(i,0,strlen(k1)){
  if(k1[i]=='?'){
   k1[i]='a';
   while(k1[i]<='f'){ 
    FOR(j,0,m-1){dp[i/l][j]=compare(i/l,j);}
    if(hopCK()){ break; }
    k1[i]++;
   }
   if(k1[i]=='g'){ return false; }
  }
 }
 
 return true;
}

int main(){
 clock_t t=clock(); 
 int T=0;
 scanf("%d",&T);
 FOR(t,1,T){
  scanf("%d\n%s\n%s",&m,k1,k2);
  if( solve())
   printf("Case #%d: %s\n",t,k1);
  else
   printf("Case #%d: IMPOSSIBLE\n",t);
 }
  
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}

[Practice Mode] HackerCup-2013 Round-1 :: CardGame

Lession-1: Don't rush...Keep calm and settle down when you know the logic already.

Lession-2: 1,000,000,007 Is a Magic Number :P and Do Not IGNORE it.

Lession-3: Remember the Rule when working with Modulus Operation, "Apply mod before the result".
If you wait until the result to be computed, answers will be tossed away.

(a+b)mod m = (a mod m + b mod m) mod m;
(a*b)mod m = (a mod m * b mod m) mod m; 

Lession-4: Arrays are the Most beautiful data structure that you ever seen :D. Do not hesitate to use them to compute nCr and etc.

Lession-5: Every problem will have simple solution. Think smart not Bigger.

Lession-6: If you see a Modulus, be ready to solve it. Because modulo randomization always periodical. So Gear up.

// =====================================================================================
//       Filename:  cardGame.cpp
//    Description:  
//        Created:  02/02/2013 11:44:39 PM
//         Author:  BrOkEN@!
// =====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>


#define TIMER 1
#define NMAX 10001
#define MOD 1000000007L

#define FOR(i,a,b) for( typeof(a) i=(a); i < (b) ; ++i )

using namespace std;

int N=0,K=0;
long a[NMAX];
long nCr[NMAX][NMAX];


long solve(){
 sort(a,a+N);
 long sum=0L;K--;
 FOR(i,K,N){
  sum+=(a[i]%MOD * nCr[i][K]%MOD)%MOD;
 }
 return sum%MOD;
}

void preCompute(){
 FOR(i,0,NMAX){
  FOR(j,0,i+1){
   if(j==0) nCr[i][j]=1%MOD;
   else nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%MOD;
  }
 }
}

int main(){
 clock_t t=clock();
 preCompute();
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%d %d",&N,&K);
  for(int i=0;i<N;i++){scanf("%ld",&a[i]);};
  printf("Case #%d: %ld\n",t,solve()); 
 } 
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}

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()); 
 }
}