ACM ICPC Latin America 2011 – J – Jupiter Attacks!

This problem is a case of RMQ or Interval Trees.
For join two ranges:

[latexpage][ quicklatex{size=20} R_a + R_b]

[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) cup (B^0f_4 + B^1f_3 + B^2f_2) ]

[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) + (B^0f_4 + B^1f_3 + B^2f_2)B^3 ]

[ quicklatex{size=20} B^0f_7 + B^1f_6 + B^2f_5 + B^3f_4 + B^4f_3 + B^5f_2 ]

With that formula we can pre-calculate some intervals and the intervals can join for solve queries, this my implementation.

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem J - Jupiter Attacks!
 * @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 T[400000], MOD, B[100005];

void insert(int i, int v, int it, int ini, int end){
   if(ini == end){
      T[it] = v % MOD;
      return;
   }
   int le = it<<1, ri = le+1, mid = (ini+end)>>1;
   if(i <= mid) insert(i, v, le, ini, mid);
   else insert(i, v, ri, mid+1, end);
   T[it] = ((( T[le]*B[end-mid] ) % MOD) + T[ri]) % MOD;
}

LL functionH(int x, int y, int it, int ini, int end){
   if(x == ini && y == end) return T[it];
   int le = it<<1, ri = le+1, mid = (ini+end)>>1;
   if(y <= mid) return functionH(x, y, le, ini, mid);
   else if(x > mid) return functionH(x, y, ri, mid+1, end);
   return ((( functionH(x, mid, le, ini, mid)*B[y-mid] ) % MOD) + functionH(mid+1, y, ri, mid+1, end)) % MOD;
}

int main(){
   int b, p, l, n, x, y;
   char op;
   scanf("%d %d %d %d", &b, &p, &l, &n);
   while(b){
      memset(T, 0, sizeof(T));
      memset(B, 0, sizeof(B));
      B[0] = 1;
      MOD = p;
      FOR(i, 1, 100000) B[i] = (B[i-1]*LL(b)) % MOD;
      F(i, n){
         cin>>op>>x>>y;
         if(op == 'E') insert(x, y, 1, 1, l);
         else printf("%lldn", functionH(x, y, 1, 1, l));
      }
      printf("-n");
      scanf("%d %d %d %d", &b, &p, &l, &n);
   }
}

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

ACM ICPC Latin America 2011 – I – In Braille

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem I - In Braille
 * @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;

string s1[] = {".*", "*.", "*.", "**", "**", "*.", "**", "**", "*.", ".*"};
string s2[] = {"**", "..", "*.", "..", ".*", ".*", "*.", "**", "**", "*."};

char ch[305];
char num[105];
char s[3][305];

int it;

void lee(int & n){
   it = n = 0;
   gets(ch);
   while(ch[it]) n = n*10 + ch[it++]-'0';
}

int main(){
   int n;
   lee(n);
   while(n){
      gets(ch);
      it = 0;
      if(ch[0] == 'S'){
         gets(num);
         for(int i=0; i<n ;i++){
            if(i) s[0][it] = ' ', s[1][it] = ' ', s[2][it++] = ' ';
            char numaux = num[i]-'0';
            s[0][it] = s1[ numaux ][0];
            s[1][it] = s2[ numaux ][0];
            s[2][it++] = '.';
            s[0][it] = s1[ numaux ][1];
            s[1][it] = s2[ numaux ][1];
            s[2][it++] = '.';
         }
         s[0][it] = s[1][it] = s[2][it] = 0;
         puts(s[0]);
         puts(s[1]);
         puts(s[2]);
      }
      else{
         for(int i=0; i<3 ;i++)
            gets(s[i]);
         for(int i=0; i<n ;i++){
            int it1 = i*3, j;
            for(j=0; j<10 ;j++){
               if(s[0][it1] == s1[j][0]) if(s[0][it1+1] == s1[j][1])
                  if(s[1][it1] == s2[j][0]) if(s[1][it1+1] == s2[j][1])
                     break;
            }
            num[it++] = j+'0';
         }
         num[it] = 0;
         puts(num);
      }
      lee(n);
   }
}

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

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 #67 (Div. 2) Problem C

Link: C. Modified GCD

This is my solution.

int main(){
    int a, b, n, x, y;
    scanf("%d %d %d", &a, &b, &n);
    int d = __gcd(a, b);
    set<int> v;
    v.insert(d);
    for(int i=1; i <= sqrt(d) ;i++){
        if(d%i == 0){
            v.insert(i);
            v.insert(d/i);
        }
    }
    vector<int> val(v.begin(), v.end());
    for(int i=0; i<n ;i++){
        scanf("%d %d", &x, &y);
        a = 0, b = val.size()-1;
        while(a != b){
            int mid = ((a+b)/2)+1;
            if(val[mid] > y) b = mid-1;
            else a = mid;
        }
        int r=-1;
        if(a+1 < val.size()){
            if(val[a+1] <= y && val[a+1] >= x)
                r = val[a+1];
        }
        if(val[a] <= y && val[a] >= x)
            r = max(val[a], r);
        if(a-1 >= 0){
            if(val[a-1] <= y && val[a-1] >= x)
                r = max(r, val[a-1]);
        }
        printf("%dn", r);
    }
}