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

Codeforces Beta Round #67 (Div. 2) Problem D

Link: D. Big Maximum Sum

This is my solution.

typedef long long LL;

int n, v[5010];

struct FOUR{
    LL m, l, r, t;
} T[20010], DP[55];

void crear(int a, int b, int it){
    if(a == b){
        T[it].m = T[it].l = T[it].r = T[it].t = v[a];
        return;
    }
    int mid = (a+b)>>1, left = it<<1, right = left+1;
    crear(a, mid, left);
    crear(mid+1, b, right);
    T[it].t = T[left].t + T[right].t;
    T[it].m = max(max(T[left].m, T[right].m), T[left].r+T[right].l);
    T[it].l = max(max(T[left].l, T[left].t+T[right].l), T[left].t);
    T[it].r = max(max(T[right].r, T[left].r+T[right].t), T[right].t);
}

FOUR unionFour(FOUR auxL, int j){
    FOUR auxR = DP[j], r;
    r.t = auxL.t + auxR.t;
    r.m = max(max(auxL.m, auxR.m), auxL.r+auxR.l);
    r.l = max(max(auxL.l, auxL.t+auxR.l), auxL.t);
    r.r = max(max(auxR.r, auxL.r+auxR.t), auxR.t);
    return r;
}

int main(){
    int m, l, a, ind;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n ;i++){
        scanf("%d", &l);
        for(int j=1; j<=l ;j++)
            scanf("%d", &v[j]);
        crear(1, l, 1);
        DP[i] = T[1];
    }
    scanf("%d", &ind);
    FOUR fr = DP[ind-1];
    for(int i=1; i<m ;i++){
        scanf("%d", &ind);
        fr = unionFour(fr, ind-1);
    }
    cout<< max(max(fr.t, fr.m),max(fr.l, fr.r)) <<endl;
}

Codeforces Beta Round #59 Solution Problem E

This is the code of watashi, he used “backtrack” and a “mask” to solve this problem.

#include <cstdio>
#include <algorithm>

using namespace std;

char str[10][10];
int hash[1<<20];

const int lj[] = {-1, 1, 1, 1, 2, 3};
const int rj[] = {-1, 3, 4, 5, 5, 5};
const int dx[] = {0, 1, 1};
const int dy[] = {1, 0, 1};

bool gao() {
    int index = 0;
    for (int i = 1; i <= 5; ++i){
        for (int j = lj[i]; j <= rj[i]; ++j){
            index <<= 1;
            if (str[i][j] == 'O')
                index ^= 1;
        }
    }
    int& ret = hash[index];
    if (ret == 0) {
        ret = -1;
        for (int i = 1; ret < 0 && i <= 5; ++i) {
            for (int j = lj[i]; ret < 0 && j <= rj[i]; ++j) {
                if (str[i][j] != 'O') continue;
                for (int k = 0; ret < 0 && k < 3; ++k) {
                    int x = i, y = j;
                    while (str[x][y] == 'O') {
                        str[x][y] = 'X';
                        x += dx[k];
                        y += dy[k];
                        if (!gao()) {
                            ret = 1;
                            break;
                        }
                    }
                    while (x != i || y != j) {
                        x -= dx[k];
                        y -= dy[k];
                        str[x][y] = 'O';
                    }
                }
            }
        }
    }
    return ret > 0;
}

int main() {
    for (int i = 1; i <= 5; ++i)
        for (int j = lj[i]; j <= rj[i]; ++j)
            scanf(" %c", &str[i][j]);
    puts(gao() ? "Karlsson" : "Lillebror");
}

Codeforces Beta Round #55 – Problem B

Codeforces Beta Round #55 Problem B
Although the solution of this problem is realy easy, I use dynamic programming.

bool DP[10002];
int main(){
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    memset(DP, 0, sizeof(DP));
    DP[0] = true;
    for(int i=0; i<n ;i++){
        scanf("%d", &v[i]);
        for(int j=10000; j>=0 ;j--){
            if(DP[j])
            DP[j+v[i]] = true;
        }
    }
    for(int j=10000; j>=0 ;j--){
        if(DP[j] && j&1){
            printf("%dn", j);
            return 0;
        }
    }
    printf("0n");
}

The other solution is to add all, if the sum is odd print, if the sum is even subtract the smallest odd number.
Example:

3
2 3 11 = 16 => 16 - 3 = 13 (this is the result)

Bolivian contest problem A – Ajustando el volumen

La solución consiste en ir guardando paso a paso todos los resultados como se ve tendrá una complejidad de O(n*b) donde ‘b’ es el limite mayor y ‘n’ es la cantidad de elementos.
Sin programacion dinamica puede alcanzar una complejidad de O(2^n) lo que daría tiempo excedido.

int main() {
    int n, aux, a, b, ans;
    bool DP[51][1010];
    while (cin>>n && n) {
        vector<int> v(n);
        memset(DP, 0, sizeof(DP));
        for(int i=0; i<n ;i++)
            scanf("%d", &v[i]);
        scanf("%d %d", &a, &b);
        DP[0][a] = true;
        for(int j=0; j<n ;j++) {
            int act = v[j];
            for (int i=0; i<=b ;i++) {
                if(DP[j][i]){
                    if (i+act <= b)
                        DP[j+1][i+act] = true;
                    if (i-act >= 0)
                        DP[j+1][i-act] = true;
                }
            }
        }
        int res = -1;
        for(int i=0; i<=b ;i++)
            if(DP[n][i])
                res = i;
        printf("%dn", res);
    }
    return 0;
}

Bolivian contest problem G – Pares de Ruth-Aaron

Este problema era similar a los de primos, por lo que la Criba de Eratostenes se acomodaba perfectamente.

Explicación:

El 4 tiene como divisor al 2, el 6 también, como se puede apreciar el 2 es divisor de:

2 4 6 8 10 12 ... n*2

el 3 tiene al:

3 6 9 12 ... n*3

pero el 4 no cuenta por que no es primo y por lo tanto no se encuentra en la factorizacion

entonces el 2 debe sumarse a 2, 4, 6, 8, 10 por que se encuentra en la factorizacion de todos sus múltiplos.

Ejemplo de un n = 10:

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 0 0 0 0 0 0 0 0 0   todos empiezan en 0.

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 0 2 0 2 0 2 0 2   (i = 2)
           ^---^---^---^---^    el dos se debe sumar a todos sus múltiplos

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 0 5 0 2 3 2   (i = 3)
             ^-----^-----^    lo mismo con el 3

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 0 5 0 2 3 2   (i = 4)
               ^--------------  no modifica nada por que no es primo se sabe por que ya tiene un valor (2) en su posición.

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 5 5 0 2 3 7   (i = 5)
                 ^---------^    lo mismo con el 5

       0 1 2 3 4 (5   6) 7 8 9 10
dp[] = 0 0 2 3 2 (5 = 5) 0 2 3 7    ya tenemos el primer par de Ruth-Aaron

Codigo:

vector<int> solve(int n) {
    vector <int> dp(n+1,0);
    for (int i=2;i<n/2;i++) {
        if (!dp[i]) {
            for (int k=i; k<n; k+=i)
                dp[k] += i;
        }
    }
    return dp;
}
int main() {
    vector<int> dp=solve(10000010);
    int a,b;
    while (cin>>a>>b) {
        if (a==0 && b==0)
            break;
        for(int c=a; c<b; c++) {
            if (dp[c]==dp[c+1])
                cout<<c<<" "<<c+1<<endl;
        }
    }
    return 0;
}

Bolivian contest problem E – Extraño sueldo del jefe

Para resolver este problema, cada empleado con sueldo inferior debe pasar su salario + 1 a su jefe, necesitamos que los empleados con menor salario le pasen su salario antes a su jefe
Example:

14
B[] = 0 0 1 1 2 2 2 5 7 5 7 5 7 13
DP[]= 1 1 1 1 1 1 1 1 1 1 1 1 1 1   (cada empleado comienza ganando 1$)

Obviamente el que gana menos en este caso es el 14th empleado ya que existe la siguiente regla: (0

B[] = 0 0 1 1 2 2 2 5 7 5 7 5 7 (13)
DP[]= 1 1 1 1 1 1 1 1 1 1 1 1 2 (1 )
                              ^--^ (1 + 1 le pasa su salario + 1)
luego sigue el 13th empleado
B[] = 0 0 1 1 2 2 2 5 7 5 7 5 (7 )
DP[]= 1 1 1 1 1 1 3 1 1 1 1 1 (2 )
                  ^------------^   (2 + 1 = 3 modifica)
B[] = 0 0 1 1 2 2 2 5 7 5 7 (5 )
DP[]= 1 1 1 1 2 1 3 1 1 1 1 (1 )
              ^--------------^     (1 + 1 = 2 modifica)
B[] = 0 0 1 1 2 2 2 5 7 5 (7 )
DP[]= 1 1 1 1 2 1 3 1 1 1 (1 )
                  ^--------^       (1 + 1 = 2 este es menor que 3)
B[] = 0 0 1 1 2 2 2 5 7 (5 )
DP[]= 1 1 1 1 2 1 3 1 1 (1 )
              ^----------^         (1 + 1 = 2 son iguales no modifica)
B[] = 0 0 1 1 2 2 2 5 (7 )
DP[]= 1 1 1 1 2 1 3 1 (1 )
                  ^----^           (1 + 1 = 2 este es menor que 3)
B[] = 0 0 1 1 2 2 2 (5 )
DP[]= 1 1 1 1 2 1 3 (1 )
              ^------^             (1 + 1 = 2 son iguales no modifica)
B[] = 0 0 1 1 2 2 (2 )
DP[]= 1 4 1 1 2 1 (3 )
        ^----------^     (3 + 1 = 4 modifica)
B[] = 0 0 1 1 2 (2 )
DP[]= 1 4 1 1 2 (1 )
        ^--------^       (1 + 1 = 2 no modifica por que es menor)
B[] = 0 0 1 1 (2 )
DP[]= 1 4 1 1 (2 )
        ^------^         (2 + 1 = 3 no modifica por que es menor)
B[] = 0 0 1 (1 )
DP[]= 2 4 1 (1 )
      ^------^           (1 + 1 = 2 modifica )
B[] = 0 0 (1 )
DP[]= 2 4 (1 )
      ^----^             (1 + 1 = 2 no modifica por que es menor)
B[] = 0 0
DP[]= 1 4
        ^   (4 + 1 = 5 modifica a DP[0] que viene a ser el salario del jefe)
B[] = 0
DP[]= 1
      ^     (1 + 1 = 2 no modifica a DP[0] por que ya tiene un valor mayor)
sol = 5;

El código seria el siguiente:

int v[100010];
int solve(int n){
    vector<int>; DP(n+1, 1);
    for(int i=n; i<0 ;i--)
        DP[ v[i] ] = max(DP[ v[i] ], DP[ i ]+1);
    return DP[0];
}
int main() {
    int n;
    while(scanf("%d", &n) && n){
        for(int i=1; i<=n ;i++)
            scanf("%d", &v[i]);
        printf("%dn", solve(n));
    }
    return 0;
}