Codechef June 2013

I’ll describe my solutions of Codechef – June 2013. In this contest I have solved 5 problems using C++.

  • Lapindromes (Ad Hoc – Implementation)
  • Predictopus (Probability)
  • W String (Ad Hoc – Implementation)
  • Dessert Wizard (Ad Hoc – Implementation)
  • Little Elephant and Mouses(Dynamic Programming)

Sigue leyendo

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