Google Code Jam – Round 1B 2013

Solution of Problem B. Falling Diamonds small:

It can be solved following the next steps:

  1. Find the center of the pyramid: because each solution has a pyramid.
  2. If the point is in the pyramid 100% of times will have a diamond.
  3. If the point is not up to the pyramid 0% of times will have a diamond.
  4. Calculate the provability with SetsWithDiamondOnXY / TotalValidSets Sigue leyendo

UVA 459 – Graph Connectivity (Depth First Search solution)

Simple solution using DFS algorithm.

#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;
typedef long long   LL;

bool G[300][300], vis[300];

void dfs(int x) {
  if(vis[x]) return;
  vis[x] = true;
  for(char i='A'; i<='Z' ;i++)
    if(G[x][i])
      dfs(i);
}

int main() {
  int casos;
  string cad;
  char N;
  cin >> casos >> cad;
  for(int i=0; i<casos ;i++) {
    memset(vis, 0, sizeof(vis));
    memset(G, 0, sizeof(G));
    int r = 0;
    if(i) printf("n");
    N = cad[0];
    while(cin>>cad && cad.size() != 1)
      G[ cad[0] ][ cad[1] ] = G[ cad[1] ][ cad[0] ] = true;
    for(char i='A'; i<=N ;i++) {
      if(vis[i]) continue;
      dfs(i);
      r++;
    }
    printf("%dn", r);
  }
}

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

ACM ICPC Latin America 2011 – B – Ball Stacking

You need the accumulated value for all items, the accumulated value is the prize that you obtain when select an item (see image).

image1

The accumulated value can be obtained with DP. When you select an item is required select the uppers items, you can sum their accumulated values. But exist an area that you repeat and you need subtract this repeated area (see image).

image2

Now you need combine all accumulated values for find the maximum prize, when you join two accumulated values you need consider that exist an repeated.
You only need combine an accumulated value with the past ones.For implementation is neccesari change the pyramid by a matrix.

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem B - Ball Stacking
 * @contest: ACM ICPC Latin America Regional 2011
 */
#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[1002][1002];

int main(){
 int n, x;
 scanf("%d", &n);
 while(n){
  LL r = 0LL, aux, now_inc;
  for(int i=1; i<=n ;i++){
   DP[i][n-i+2] = 0LL;
   for(int j=1; j<=i ;j++){
    x = i-j+1;
    scanf("%lld", &aux);
    DP[x][j] = aux + DP[x][j-1] + DP[x-1][j] - DP[x-1][j-1];
    r = max(r, DP[x][j]);
   }
  }
  for(int i=1; i<=n ;i++){
   for(int j=n-i+1; j>=1 ;j--){
    now_inc = DP[i][j] - DP[i][j-1];
    r = max(r, DP[i][j] + DP[i-1][j+1]);
    DP[i][j] = max( max(DP[i-1][j+1] + now_inc, now_inc), max(DP[i][j+1] + now_inc, DP[i-1][j]) );
   }
  }
  printf("%lldn", r);
  scanf("%d", &n);
 }
}

ACM ICPC Latin America 2011 – A – Army Buddies

This problem is a simple case of elimination for ranges, given a range, we need remove it and obtain it’s neighbors. the best option for this case is a structure of linked list.

For example the second case in the problem:
S=10 B=4   ===> * 1 2 3 4 5 6 7 8 9 10 *
2 5        ===> * 1(2 3 4 5)6 7 8 9 10 *
                * 1 6 7 8 9 10 *
6 9        ===> * 1        (6 7 8 9)10 *
                * 1 10 *
1 1        ===> *(1)                10 *
                * 10 *
10 10      ===> *                  (10)*
                * *

This is my implementation and you can see in live archive’s statistic (Run Time:0.104).

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem A - Army Buddies
 * @contest: ACM ICPC Latin America Regional 2011
 */
#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 vleft[100001], vright[100001];

int main(){
   int n, x, y, m;
   scanf("%d %d", &n, &m);
   while(n){
      FOR(i, 1, n+1){
         vleft[i] = i-1;
         vright[i] = i+1;
      }
      F(i, m){
         scanf("%d %d", &x, &y);
         if(vleft[x] == 0) printf("* ");
         else printf("%d ", vleft[x]);
         if(vright[y] == n+1) printf("*n");
         else printf("%dn", vright[y]);
         vleft[ vright[y]] = vleft[x];
         vright[ vleft[x]] = vright[y];
      }
      printf("-n");
      scanf("%d %d", &n, &m);
   }
}

Sieve of Eratosthenes

This code was tested in problem SPOJ – PRIME1 and some ACM ICPC contests. This considers the prime greater than or equal to 5 have the form: (6^n)+1 or (6^n)-1, for n in the range 1 to ∞.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> primes;
const int MAXP = 31623;
bool criba[MAXP+2];

void generatePrimes() {
    memset(criba, false, sizeof(criba));
    criba[0] = criba[1] = true;
    int raiz = (int) sqrt(MAXP);
    for (int i=3; i<=raiz; i+=2) {
        if (!criba[i])
            for (int j=i*i; j<=MAXP; j += i)
                criba[j] = true;
    }
    primes.push_back(2);
    primes.push_back(3);
    for (int i=5, j=7; i<=MAXP; i+=6, j+=6){
        if (!criba[i])
            primes.push_back(i);
        if (!criba[j])
            primes.push_back(j);
    }
}

Sorting algorithm – Insertion Sort


This is an implementation of the insertion algorithm.

vector<int> insertionSort(vector<int>data){
    int n = data.size(), j, tmp;
    for (int i = 0; i < n; i++) {
        j = i;
        while (j>0 && data[i] < data[j - 1])
            j--;
        tmp = data[i];
        for (int k = i; k > j; k--)
            data[k] = data[k - 1];
        data[j] = tmp;
    }
    return data;
}

As you can see the insertion algorithm is not much difference with the Bubble Sort and is very easy to implement, the following is an example to better understand the operation:

        {18,  6,  9,  1,  4, 15, 12,  5,  6,  7, 11}
        { 6, 18,  9,  1,  4, 15, 12,  5,  6,  7, 11}
        { 6,  9, 18,  1,  4, 15, 12,  5,  6,  7, 11}
        { 1,  6,  9, 18,  4, 15, 12,  5,  6,  7, 11}
        { 1,  4,  6,  9, 18, 15, 12,  5,  6,  7, 11}
        { 1,  4,  6,  9, 15, 18, 12,  5,  6,  7, 11}
        { 1,  4,  6,  9, 12, 15, 18,  5,  6,  7, 11}
        { 1,  4,  5,  6,  9, 12, 15, 18,  6,  7, 11}
        { 1,  4,  5,  6,  6,  9, 12, 15, 18,  7, 11}
        { 1,  4,  5,  6,  6,  7,  9, 12, 15, 18, 11}
        { 1,  4,  5,  6,  6,  7,  9, 11, 12, 15, 18}