[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;
}