Segment Trees - Range Minimum Query Application

Hello, today I'll post a implementation of a Segment Tree which fits for Range Minimum Query.

 I've been studying segment trees about a time, and I'm starting to understand them now, this implementation runs in O(N) for construction and O(log(N)) for query and update.

 Another things is that the source code of the post is stored in a Github Gist

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

Maximum-Flow

Hi, I've just implemented in C++ and good and clean Edmonds-Karp Maximum-Flow implementation, hope it would be useful to you too

#include <iostream>
#include <vector>

using namespace std;

vector graph[MAXN];
int capacity[MAXN][MAXN];

int max_flow(int source, int sink) {
    int residual[MAXN][MAXN];
    memset(residual, 0, sizeof(residual));
    while(1) {
        int prev[MAXN];
        memset(prev, -1, sizeof(prev));
        int actual[MAXN];
        memset(actual, 0, sizeof(actual));
        prev[source] = source;
        actual[source] = INF;
        queue q;
        q.push(source);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i];
                if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
                    prev[v] = u;
                    actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
                    if(v != sink) {
                        q.push(v);
                    } else {
                        while(prev[v] != v) {
                            u = prev[v];
                            residual[u][v] += actual[sink];
                            residual[v][u] -= actual[sink];
                            v = u;
                        }
                        goto end;
                    }
                }
            }
        }
        end:;
        if(prev[sink] == -1) {
            int sum = 0;
            for(int i = 0; i < MAXN; i++) {
                sum += residual[source][i];
            }
            return sum;
        }
    }
}

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

About Alcumus

I've just found an nice place for who enjoy problems, the site is Alcumus, it has a lot of interesting problems, and all of them with solutions.