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

Hatena

Hi, about a time I don't post anything here, I'm finishing my article about graphs, I hope you like it, I'll post the solutions for the problems from several online judges I use in my hatena diary, 'Hatena is a kind of blog, famous in japan, with a clean look'. I'll use it to post solutions because I don't wanna mess this blog with a lot of sparse posts.

http://d.hatena.ne.jp/aajjbb/

Busy

Hello, as you all already know, I'm not posting in the blog lately, I've been busy with both work and study, so I'm unable go post hints and tips for past contests, but I'll be back as soon as possible. I'm preparing some stuff in graph theory that should be helpful. Thanks

Considerations and Tutorial of TopCoder SRM 532

Hi everybody;

Today's SRM was quite exciting, the problem set was tricky but nice, an easy 250, and not too difficult but with some tricky test cases and a harder than usual 1000 which until now I'm unable to think in any possible "in-time" solution, I guess it's because I'm really bad at DP.

I'll write a brief tutorial about this round problems which I was able to solve, in the contest time, I just solved the 250 one, who was quite easy, but in less than 5 minutes in practice room, I solved the 600 problem without issues;

250:

Reading the statement carefully, it's easy to notice that the approach is:
Find the Maximum and Minimum values of the array, theses values are the minimum possible bound for the set; then check all the values between this whole set who's not in the array;

My solution in the actual contest is ridiculous expensive, so, there's an better solutions which runs O(N) (with N as the size of the array), and then check, all the values within the interval ((max - min) + 1), then check the intervals who's not in the array, in other words (((max - min) + 1) - array.size())

Here's some pseudo-code(inspired in python):

max = negative infinite
min = infinite
for i in array:
   if i > max:
     max = i
  if i < min:
     min = i

return (max - min) + 1 - array.size()

500:
Notice that for any valid sequence, all the elements in the "middle" of the concatenated string must have only digits number, then, we can find the right solution in maximal O(N^2 * N - 2):

We check all the possible right-end and left-end strings:, then is just try this possibilities, with all the existing mid-strings(strings who's doesn't have '.')

Here Comes the Code:


import java.util.*;

public class DengklekMakingChains {
public int maxBeauty(String[] chains) {
int max = 0, N = chains.length;
String t = "";
for(int i = 0; i < N; i++) t += chains[i];
max = get(t);

for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i != j) {
String tm = chains[i];

for(int k = 0; k < N; k++) if(k != i && k != j) {
boolean ok = true;
for(int l = 0; l < 3; l++) {
if(chains[k].charAt(l) == '.') ok = false;
}
if(ok) tm += chains[k];
}
tm += chains[j];
max = Math.max(max, get(tm));
}
}
}
return max;
}
public int get(String s) {
int mx = 0;
for(int i = 0; i < s.length(); i++) {
int j = i;
int tmp = 0;
while(j < s.length() && s.charAt(j) != '.') {
tmp += s.charAt(j) - '0';
j++;
}
i = j;
mx = Math.max(mx, tmp);
}
return mx;
}
}

Considerations about Top Coder SRM 531

Hello everybody, since I moved from wordpress to blogger, I didn't posted anything here, so, this post is just to say what i thought about the TC last srm.

The problems were cool, as in DIV 2, was presented a tricky problem set, in 250 problem I was a kind nervous to does not decrease my rank again so, I sacrificed an elegant and efficient solution to an expensive O(2^N * N), the 500 problem was a classical DP Bottom Up possible solution, but as vexorian posted in his blog, there was a Top-Down solution.. The 1000 problem was another graph problem, about MST, as I don't major both DP and MST yet, I was only able to solve the 250, it was a shame, but I'm studying this both subjects now to make a better appearance in the next SRM, that will happen tomorrow, See you there!

I've found nice editorials in the vexorion blog and in Seulgi Kim blog, who's also my friend, take a look if you be interested;

http://vexorian.blogspot.com/
http://sk765.blogspot.com/

Starting again

due to boring problems with my last blog in wordpress, now I'm moving to blogger, for a reason of simplicity and lazyness, so i'm starting again...