Facebook Hacker Cup 2012 Round 1 – Squished Status

Dynamic Programming – O(n^2)

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

const LL MOD = 4207849484LL;

LL DP[1010];

int stringtoint(string s){
   stringstream ss(s);
   int r;
   ss>>r;
   return r;
}

LL solve(int m, string text){
   F(i, text.S){
      string aux = "";
      for(int j=i; j>=0 ;j--){
         aux = text[j] + aux;
         if(aux.size() >= 4) break;
         if(text[j] != '0'){
            if(stringtoint(aux) <= m){
               if(j == 0) DP[i] = (DP[i] + 1LL) % MOD;
               else DP[i] = (DP[i] + DP[j-1]) % MOD;
            }
         }
      }
   }
   return DP[text.S-1];
}

int main(){
   //freopen("a.in", "r", stdin);
   //freopen("squished_status.txt", "r", stdin); freopen("a.out", "w", stdout);
   int n, m;
   string text;
   scanf("%d", &n);
   F(cas, n){
      memset(DP, 0, sizeof(DP));
      cin>>m>>text;
      printf("Case #%d: %lldn", cas+1, solve(m, text));
   }
}

Facebook Hacker Cup 2012 Round 1 – Recover the Sequence

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

int n, its;
string s;

vector<int> merge2(vector<int> arr1, vector<int> arr2){
   vector<int> result;
   int i=0, j=0;
   while(i < arr1.size() && j < arr2.size()) {
      if(s[its] == '1') result.PB(arr1[i++]);
      else result.PB(arr2[j++]);
      its++;
   }
   while(i < arr1.size()) result.PB(arr1[i++]);
   while(j < arr2.size()) result.PB(arr2[j++]);
   return result;
}

vector<int> reverse_sort(vector<int> arr){
   int k = arr.size();
   if(k <= 1) return arr;
   int mid = int(k/2);
   vector<int> first_half, second_half;
   F(i, mid) first_half.PB(arr[i]);
   FOR(i, mid, arr.S) second_half.PB(arr[i]);
   first_half = reverse_sort(first_half);
   second_half = reverse_sort(second_half);
   return merge2(first_half, second_half);
}

int checksum(vector<int> arr) {
    int result = 1;
    for(int i=0; i<arr.size() ;i++)
       result = (31 * result + arr[i]) % 1000003;
    return result;
}

vector<int> solve(){
   vector<int> v(n), r(n);
   F(i, n) v[i] = i;
   v = reverse_sort(v);
   F(i, n) r[ v[i] ] = i+1;
   return r;
}

int main(){
   //freopen("a.in", "r", stdin);
   //freopen("recover_the_sequence.txt", "r", stdin); freopen("a.out", "w", stdout);
   int t;
   scanf("%d", &t);
   F(cas, t){
      cin>>n>>s;
      its = 0;
      printf("Case #%d: %dn", cas+1, checksum(solve()));
   }
}

Facebook Hacker Cup 2012 Round 1 – Checkpoint

Dynamic Programming – O( 160000000 , sqrt(n) )

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

LL DP[10000005][16];

void generate(){
   FOR(i, 1, 10000005){
      FOR(j, 1, 15){
         if(i == 1) DP[i][j] = 1LL;
         else DP[i][j] = DP[i-1][j];
         if(j == 1) DP[i][j] += 1LL;
         else DP[i][j] += DP[i][j-1];
         if(DP[i][j] > 10000000LL) break;
         if(DP[ DP[i][j] ][0]) DP[ DP[i][j] ][0] = min(DP[ DP[i][j] ][0], LL(i)+LL(j));
         else DP[ DP[i][j] ][0] = LL(i)+LL(j);
      }
   }
}

int cuad(int x) {
   int r = int(DP[x][0]);
   if(r == 0) return x;
   return r;
}

int solve(int x){
   int m = sqrt(x), r = cuad(x)+1;
   for(int i=2; i<=m ;i++) {
      if(x % i == 0){
         int j = x/i;
         r = min(r, cuad(i)+cuad(j));
      }
   }
   return r;
}

int main(){
   //freopen("a.in", "r", stdin);
   //freopen("checkpoint.txt", "r", stdin); freopen("checkpoint.out", "w", stdout);
   generate();
   int r, s;
   scanf("%d", &r);
   F(cas, r){
      scanf("%d", &s);
      printf("Case #%d: %dn", cas+1, solve(s));
   }
}