Latin American Summer School

Hello, I'm here today to write about the Latin American Summer School for the World Finalists of the ACM/ICPC. The goal of the school was to train the teams for the World Finals, but it was open for non-finalists teams too. As I didn't managed to get a team to go with my university so I got a remaining spot in a team from Universidade Federal de Campina Grande. We stayed for two weeks in Campinas, which is by the way, a lovely city.

The school worked as follows, we arrived at 8 o'clock for a breakfast and then for a 3 hours class, then after a lunch, a 5 hour contest to train our skills on the given subjects. I've enjoyed and learned a lot there, the infra-structure of Unicamp is amazing, so we had classes and contest in a good environment. I'd like to thanks Unicamp and the organizers of the event, as well the professors which were Fidel Shaposnik in the first week and Jakub Radoszewski in the second one, and of course, my team mates from UFCG.

Here are the links for the training held in the first week, the second week ones will be posted soon, as the professor used a different contest environment:

http://ahmed-aly.com/Standings.jsp?ID=3595
http://ahmed-aly.com/Standings.jsp?ID=3608
http://ahmed-aly.com/Standings.jsp?ID=3644
http://ahmed-aly.com/Standings.jsp?ID=3655

Dominoes Arrangement and Domino

Hi, surfing on BRSPOJ again, I've found a problem similar to another one that I already solved in Aizu Online Judge, they are these two: LinkAOJ and LinkSPOJ.

For the AOJ one, the input is a little different, but in it's essence, it's the same, given 'N' pieces of domino blocks   determine if it's possible to use all the pieces to form an whole valid sequence Dominoes. I've found 2 solutions, one using backtrack which runs in O(M + 2^N) with 'M' being the maximum number of values on a side of a piece and 'N' the total number of pieces.

This solution is good, but it's enough to pass through the tough system test of BRSPOJ, so I've turned to a graph solution, which is better, running only with a simple Depth-First-Search plus 2 iterations over the 'M', which runs in O(|V| + |E| + 2*M): These are the both solutions:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int a, b, i, j, k, n, ok, teste = 1, mem[7][7];

void rec(int now, int deep) {
    if(deep == n) {
        ok = 1;
        return;
    }
    for(j = 0; j &lt; = 6; j++) {
        int i = j;
        if(mem[now][i]&gt; 0) {
            mem[now][i]--;
            mem[i][now]--;
            rec(i, deep + 1);
            if(ok == 1) return;
            mem[now][i]++;
            mem[i][now]++;
        }
    }
}

int main(void) {
    while(scanf("%d", &amp; n) &amp; &amp; n != 0) {
        memset(mem, 0, sizeof(mem));
        ok = 0;
        for(i = 0; i &lt; n; i++) {
            scanf("%d%d", &amp; a, &amp; b);
            mem[a][b] += 1;
            mem[b][a] += 1;
        }
        for(k = 0; k &lt; = 6; k++) {
            rec(k, 0);
            if(ok == 1) break;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 ? "sim" : "nao");
    }
    return 0;
}

and

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int a, b, n, ok, teste = 1, mem[7][7], vis[7], ct[7];

void dfs(int x) {
    vis[x] = 1;
    for(int j = 0; j <= 6; j++) {
        if(vis[j] == 0 && mem[x][j] == 1) dfs(j);
    }
}

int main(void) {
    while(scanf("%d", &n) && n != 0) {
        memset(mem, 0, sizeof(mem));
        memset(vis, 0, sizeof(vis));
        memset(ct, 0, sizeof(ct));
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &a, &b);
            ct[a] += 1;
            ct[b] += 1;
            mem[a][b] = 1;
            mem[b][a] = 1;
        }
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0) {
                dfs(i);
                break;
            }
        }
        ok = 1;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0 && !vis[i]) {
                ok = 0;
            }
        }
        int o = 0;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] % 2 == 1) o++;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 && (o == 0 || o == 2) ? "sim" : "nao");
    }
    return 0;
}

Minimum Cut Problem

Hello, working more on BRSPOJ problems (ACM/ICPC Regionals will be held next month) I found a different graph problem Link, the problems asks to find the minimum cut of a graph, my first and naive idea was just sort the edges and remove them by their lesser weights till disconnect some vertex from the graph. The idea was totally wrong, then I started to look for similar problems and solutions over the internet and figured out that it was a simple Minimum Cut problem, and some of their best solutions were the Stoer-Wagner algorithm which works in O(n^3):
Credits goes to Link

 
  #include <iostream>   
  #include <vector>   
  #include <algorithm>   
  #include <queue>   
  #include <stdio.h>   
  #include <stdlib.h>   
  #include <string.h>   
  using namespace std;   
  const int INF = 1000000000;   
  int test, n, m, a, b, c, ans, cont, graph[110][110];   
  int globalMinCut(int n) {   
   bool a[n];   
   int v[n];   
   int w[n];   
   for(int i = 0; i < n; i++) v[i] = i;   
   int best = INF;   
   while(n > 1) {   
    int maxj = 1;   
    a[v[0]] = true;   
    for(int i = 1; i < n; ++i) {   
     a[v[i]] = false;   
     w[i] = graph[v[0]][v[i]];   
     if(w[i] > w[maxj]) {   
      maxj = i;   
     }   
    }   
    int prev= 0 ,buf = n;   
    while(--buf) {   
     a[v[maxj]]=true;   
     if(buf == 1) {   
      best = min(best, w[maxj]);   
      for(int k = 0; k < n; k++) {   
       graph[v[k]][v[prev]]= (graph[v[prev]][v[k]] += graph[v[maxj]][v[k]]);   
      }   
      v[maxj] = v[--n];   
     }   
     prev = maxj;   
     maxj = -1;   
     for(int j = 1; j < n; ++j) {   
      if(!a[v[j]]) {   
       w[j] += graph[v[prev]][v[j]];   
       if(maxj < 0 || w[j] > w[maxj]) {   
        maxj=j;   
       }   
      }   
     }   
    }   
   }   
   return best;   
  }   
  int main(void) {   
   scanf("%d", &test);   
   for( ; test-- > 0; ) {   
    scanf("%d%d", &n, &m);   
    memset(graph, 0, sizeof(graph));   
    for(int i = 0; i < m; i++) {   
     scanf("%d%d%d", &a, &b, &c);   
     a -= 1;   
     b -= 1;   
     graph[a][b] = graph[b][a] = c;   
    }   
    printf("%d\n", globalMinCut(n));   
   }   
   return 0;   
  }   

Topological Sort

Hi this is a fast post, but I think it may be useful to a bunch of people.

Today I've experienced hard times in topological sort. I'm used to use a simple Depth-First-Search recursively to order the vertexes and store the order in the 'order' vector.

 void dfs(int x) {   
   vis[x] = true;   
   for(int u = 0; u < n; u++) {   
    if(!vis[u] && graph[x][u] == 1) {   
     dfs(u);   
    }   
   }   
   order.push_back(x);   
  }   

But, if the graph has a cycle ? in this way, the DFS will end normally and won't tell you that, a good strategy is to think to put colors in the nodes, Imagine like if a vertex is 'WHITE' it has not been visited yet, if a vertex is 'GREY' it has been visited, but it sub-trees hasn't been visited yet and 'BLACK' if the vertex has been visited and all it's sub-trees has been visited too. Taking it inside the code is easy, instead of use a 'boolean' array to check if the node is visited or not, use a numerical array 'int' and set values for the colors, in this example I'm using '0' for 'WHITE, '1' for 'GREY' and '2' for black, then here goes the right code. I have to thank AlexDmitriev, dalex and Malinovsky239 who answered me in the Codeforces forum and gave me this strategy. Thank you guys.

 void dfs(int x) {  
   vis[x] = 1;  
   for(int u = 0; u < n; u++) {  
     if(vis[u] == 1 && graph[x][u] == 1) has = true;  
     if(vis[u] == 0 && graph[x][u] == 1) {  
       dfs(u);  
     }  
   }  
   vis[x] = 2;  
   order.push_back(x);  
 }  

Interligando a Sildavia

Hi, it's been a time since I post something useful in the blog, today I'll talk about a problem from the 'Maratona Mineira de Programação' as the statement is in Portuguese, and probably anyone who's interested to solve it is a native Portuguese speaker, it make more sense to write the post in Portuguese, but to keep my English in practice, I'll write in English:

The statement and Example test cases can be found here: http://br.spoj.pl/problems/INTERLMG/

The problem asks to return the minimum length of a string to connect all the pair of vertexes:

I used the follow strategy, which is a little bit slow, but it's enough to pass in the system test:

Think the each point as a vertex in a graph, and the string pieces, the weight of the edges between them, we want to find the minimum possible value to the weight of all edges(which have to be equal) to connect all the points;

I've ran a binary search, looking for the minimum weight for this edges, as the number can be real, I used a bound(in this case, 50) to doesn't exceed the time limit, and used each point as a vertex in a graph, checking as a edge if the length of the strihere comes the code:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

using namespace std;

int n, vis[1010], path[1010][1010];
double x[1010], y[1010];

void dfs(int a) {
    vis[a] = true;
    for(int i = 0; i < n; i++) {
        if(path[a][i] == 1 && !vis[i]) {
            dfs(i);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    while(cin >> n && n) {
        for(int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }
        double low = 0.0, high = 10000000.0, mid;
        for(int z = 0; z <= 50; z++) {
            memset(vis, 0, sizeof(vis));
            bool has = false;
            mid = low + (high - low) / 2;
            for(int i = 0; i < n; i++) {
                for(int j = i + 1; j < n; j++) {
                    if(hypot(x[i] - x[j], y[i] - y[j]) < mid) {
                        path[i][j] = path[j][i] = 1;
                    } else {
                        path[i][j] = path[j][i] = 0;
                    }
                }
            }
            dfs(0);
            for(int i = 0; i < n; i++) if(vis[i] == 0) has = true;
            if(has) {
                low = mid;
            } else {
                high = mid;
            }
        }
        printf("%.4f\n", low);
    }
    return 0;
}

Then, I realized that it's also possible to solve the problem in a better way O(N^2 + (N log(N)) + M) with N as the number of points, and M as the edges between the points, here comes the code again:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

using namespace std;

int n, vis[1010], path[1010][1010];
double x[1010], y[1010];

struct UnionFind {
    int N, *id, *sz;

    UnionFind(int _N) {
        id = new int[_N];
        sz = new int[_N];
        for(int i = 0; i < _N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        N = _N;
    }
    int root(int i) {
        while(i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
    bool find(int p, int q) {
        return root(p) == root(q);
    }
    void unite(int p, int q) {
        int i = root(p);
        int j = root(q);
        if(i == j) return;
        if(sz[i] < sz[j]) {
            id[i] = j; sz[j] += sz[i];
        } else {
            id[j] = i; sz[i] += sz[j];
        }
    }
};

struct edge {
    int a, b;
    double len;

    edge(){}
    edge(int _a, int _b, double _len) {
        a = _a;
        b = _b;
        len = _len;
    }
    bool operator<(const edge &e) const {
        return len < e.len;
    }
};


int main(void) {
    ios::sync_with_stdio(false);
    while(cin >> n && n) {
        vector<edge> vs;
        for(int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                vs.push_back(edge(i, j, (double)hypot(x[i] - x[j], y[i] - y[j])));
            }
        }
        UnionFind uf(n+1);
        sort(vs.begin(), vs.end());
        double ans = 0.0;
        for(int i = 0; i < vs.size(); i++) {
            if(!uf.find(vs[i].a, vs[i].b)) {
                uf.unite(vs[i].a, vs[i].b);
                if(vs[i].len > ans) {
                    ans = vs[i].len;
                }
            }
        }
        printf("%.4f\n", ans);
    }
    return 0;
}

Union Find

I've coded an nice Union Find implementation that should be helpful to anyone, it's based on a 'Weighted union find' which also stores an array for the size of the 'leaves' if you imagine a group of union procedures as merges two sub-trees, and to make things better, it only require O(lg N) to both Union and Find procedures, good isn't it ? Here goes the code which is also available on github and hatena

#include 

using namespace std;

struct UnionFind {
    int N, *id, *sz;
    UnionFind(int _N) {
        N = _N;
        id = new int[_N];
        sz = new int[_N];
        for(int i = 0; i < _N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    int root(int i) {
        while(i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
    bool find(int p, int q) {
        return root(p) == root(q);
    }
    void unite(int p, int q) {
        int i = root(p);
        int j = root(q);
        if(sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }
}