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

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