ACM ICPC

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

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