Facebook Hacker Cup Links

SOLUTIONS

Year 2012

Round Problems Solutions
 Qualification Round  Solution
 Round 1  —
Round 2   —
 Round 3  —
 Final Round
 Winner: Petr

Year 2013

Round Problems Solutions
 Qualification Round  Solution
 Round 1  Solution
Round 2   —
 Round 3  —
 Final Round
 Winner:

Year 2014

Round Problems Solutions
 Qualification Round  —
 Round 1  —
Round 2   —
 Round 3  —
 Final Round
 Winner:

Year 2015

Round Problems Solutions
 Qualification Round  —
 Round 1  —
Round 2   —
 Round 3  —
 Final Round
 Winner: tourist

 

Day-1

Welcome to day 1. 

First Question

for today is “Upvote” given @ Quora Challenges. Personally I love the product developed by team at Quora. It is among my top 3 fav. companies (including Airbnb and Google). Anyways, unfortunately I cannot produce the code for the solution here. But I solved the problem in O(n) worst case runtime.

 

Second Question New Year Chaos

USING BIT

#include &ltiostream&gt
#include &ltalgorithm&gt

using namespace std; 
vector q; 

long n;
long BIT[100001];

void updateBIT(long ind){
    /*
    BIT is used like A[ind] = 1
    and update till ind<=n, BIT
    */
    ind++;
    while(ind<=n){ 
        BIT[ind]++; 
        ind = ind + (ind & -ind); 
    } 
} 

long getSum(long ind){ 
     ind++; 
     long sum = 0; 
     while(ind>0){
        sum += BIT[ind];
        ind = ind - (ind & -ind);
    }
    return sum;
}

int main(){
    int T;
    cin >> T;
    long long ans;
    for(int a0 = 0; a0 < T; a0++){ cin >> n;
        q.resize(n);
        ans = 0;
        bool tooch = false;
        BIT[0]=0;
        for(int q_i = 0;q_i < n;q_i++){ 
           cin >> q[q_i];
           q[q_i]--;
           BIT[q_i+1] = 0;
        }
        for(int i = n-1; i >=0; i--){
           if(getSum(q[i]-1) > 2) {
               tooch = true;
               break;
           }
           ans += getSum(q[i]-1);
           updateBIT(q[i]);
        }
        if(tooch){
            cout << "Too chaotic" << endl;
        }else 
        cout << ans << endl;
    }
    return 0;
}

COUNTING INVERSIONS

Go through the array from end till beginning and keep swapping numbers if current number is smaller than next number. Also increment the count. Every swap is nothing but an inversion.

using namespace std;
vector q;  
long ans;
long start_from;


int main(){
    int T;
    cin >> T;
    for(int a0 = 0; a0 < T; a0++){ 
        int n; cin >> n;
        q.resize(n);
        ans = 0;
        for(int q_i = 0;q_i < n;q_i++){ 
           cin >> q[q_i];
           q[q_i]--;
        }
        bool tooch = false;
        
        for(int i=0; i<n; i++){ 
            if(q[i] > i && q[i]-i > 2){
                    tooch = true;
                    break;
            }
        }
        if(tooch){
            cout << "Too chaotic\n"; continue; 
        } 
        ans = 0; start_from = n-1; 
        while(start_from>=0){
             long ind = start_from;
             while(q[ind]!= ind && ind>0){
                // swap this number with ind-1 number if this is smaller
                if(q[ind] < q[ind-1]){ 
                    swap(q[ind], q[ind-1]); 
                    ans++; 
                } 
                ind--; 
             }
             while(start_from>=0 && q[start_from] == start_from) 
                start_from--;
        }
        cout << ans << endl;
    }
    return 0;
}

Third Question CHOCOLA

I used Segment tree for solving the problem.

#include

using namespace std;

int x[1001], y[1001];
int sgx[6000];
int sgy[6000];
int r,c;
void createSGT(int ind, int f, int t, int *st, int *a){
	
	if(f==t){
		st[ind] = f;
		return;
	}
	createSGT(ind*2,  f, (f+t)/2,  st, a);
	createSGT(ind*2+1,  (f+t)/2 + 1, t,  st, a);
	st[ind] = a[st[ind*2]] >= a[st[ind*2+1]] ? st[ind*2] : st[ind*2+1];
}


int getMin(int ind, int f, int t, int i, int j, int *st, int *a){
	if(t < i || f > j)   return -1;
	if(i<=f && t<=j) return st[ind]; int r1 = getMin(2*ind, f, (f+t)/2, i, j, st, a); int r2 = getMin(2*ind+1, (f+t)/2+1, t, i, j, st, a); if(r1==-1) return r2; if(r2==-1) return r1; if(a[r1] >= a[r2]) return r1;
	return r2;
}

int solve(int x1, int x2, int y1, int y2){
	if(x1==x2 || y1==y2 || (x2-x1 <= 1 && y2-y1<=1)) return 0; 
	if(x2 - x1==1){ 
		int ymin = getMin(1, 0, r-1, y1+1, y2-1, sgy, y); 
		return y[ymin] + solve(x1, x2, y1, ymin) + solve(x1, x2, ymin, y2); 
	} 
	if(y2-y1==1){ 
		int xmin = getMin(1, 0, c-1, x1+1, x2-1, sgx, x); 
		return x[xmin] + solve(x1, xmin, y1, y2) + solve(xmin, x2, y1, y2); 
	} 
	int ymin = getMin(1,0, r-1, y1+1, y2-1, sgy, y); 
	int xmin = getMin(1,0, c-1, x1+1, x2-1, sgx, x); 
	if(x[xmin] >= y[ymin]){
		return x[xmin] + solve(x1, xmin, y1, y2) + solve(xmin, x2, y1, y2);
	}else{
		return y[ymin] + solve(x1, x2, y1, ymin) + solve(x1, x2, ymin, y2);
	}
	
}

int main(){
	int _t;
	cin >> _t;
	while(_t--){
		cin >> c >> r;
		r++; c++;
		x[0] = x[c-1] = 0;
		for(int i=1; i<c-1; i++){ cin >> x[i];
		}
		y[0] = y[r-1] = 0;
		for(int i=1; i<r-1; i++){ cin >> y[i];
		}
		createSGT(1, 0, c-1, sgx, x);
		createSGT(1, 0, r-1, sgy, y);
		cout << solve(0, c-1, 0, r-1) << endl;
	}
}