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