SRM 563 - The redemption

Hello again, it's been a time since I took part in a official SRM (the last one was SRM 559), and it was held in an atypical afternoon here in Brazil, I've just moved, and my home is a mess, I registered early and went to the kitchen, when I got back to computer, the round was about 5 seconds to start. 

Starting to talk about the problems itself, I started opening 250, it was an really easy problem, different from the last rounds when the easy problems weren't so easy (solvable in a few minutes). The problem asked whether given 2 strings S and T if it's possible to mix to copies of string S so the string becomes equals to T, as the problems asks for only two copies of S, then it's solvable in O(N) being N the length of string S:

Until the submission for problem 250, the arena was working normally, even with the problem with the examples combo box which doesn't keep track of your last tested example and always get your first example  tested by default (in the arena older versions it didn't happened). Then, opening the problem 550, I received the annoying message 'you can only see one problem at time' (I don't remember the message at all but it's something like this), than I had to log off to open the problem again, while coding, there were times when I had to wait more than a minute for a compilation, which made my submission way lower than it should be.

The problem starts talking about a game with two coins in a board, consisting of empty cells '.', obstacles '#' and, you 4 options of plays, move both coins for north, south, east or west, making a move you change both coins to a single direction, if any coin move to a cell with an obstacle, it simply doesn't move. The goal of the game is to move only one single coins out of the board. My solution was an Breadth-First-Search though the graph, using a state of the number of moves, and the location of both coins, simulating the goal of the game:

I'm yet thinking of a state for a dynamic programming solution for problem 1000, it'll be in a edit when available.

I ended up with an +109 rating and becoming green again, I'm pretty happy with good rating after a bad score record.

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 500 and a harder than usual 1000 which until now I didn't thought in any possible "in-time" solution, I guess it's because I'm really bad in dynamic programming.

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 but here is an O(N * log(N)) solution:

In the 600 the idea is quite simple get all the 'non-rusty' chain links, and then, get the most profitable prefix and suffix. It can be done straightforwardly, but the trick starts with possible chains as '9.9' where the link can be both the best prefix and suffix, as we have only two end points "prefix and suffix" we can brute force this two possibilities which I called 'prefixBeforeSuffix' and 'suffixBeforePrefix', which ended up in a O(6*(N*3)) solution, running smoothly under Topcoder time limits.

About C# and Internship

Hello, things are being busy to me lately, it's time of final exams in the university and I'm starting an internship.
In the very first day of the internship I was warned that we would have to work with C# and Perl (instead of my beloved Java and Python), so I started to learn and look out for more information with this languages, fortunately I've noticed they both are cool, I'm now focused on C# which is pretty close to Java in it's syntax, but with some cool features and advantages against Java, I'll list some of them here, which I could find in the first days of study:

• Everything is an object (no wrapper classes)
• Fast and easy to use GUI builder (the code produced isn't awesome, but it's easier and way faster than Eclipse WindowBuilder)
• Simple way to create access methods (get and set)
• Easy and simple API to do work with web resources (Web request and responses)

It's just a few of them, I'm not saying I'll give up Java or something but, it was a good surprise to figure out cool features on a language I had so much prejudice, learning more, I'll probably write a same 'cool stuff' from Perl

SRM 599: Shame

Hello, sadly I'm not in a good mood. Yesterday night I took part in SRM 559, which gave me a (-37) score, a reasonable low score due to a 0 point final score (I didn't solved any problem).

The problem set was harder than usual, with a dynamic programming problem in 250 DIV 2. The problem statement isn't available online due a bug in Topcoder site, so, the problem asks the highest column possible built using blocks of positive heights(of course).

1) With their indexes in ascending order.
2) A block with even height can't be built up a block with odd height.

Clearly a dp problem, I used all the time I could for reach a simple state for the dp but I didn't did it. After a bad sleep night and a wake up against my desire, I gave another chance for this problem, and finally found an winning stated which passed in the system tests.

Think of an a dp[i] which, dp[i] stands for the maximum height for a column ending which block[i];

The base case for a dp[i] is b[i], making it:

$dp[i] = b[i]$
Iterating over the 0 to i blocks, we first check the existence condition number 2 and them check, the maximum ending with b[i] block is dp[j] (column with maximum height ending with b[j]) + b[i] (height of the actual last block) making our state passage being like this:
$ dp[i] = max(dp[i], dp[j] + b[i]) $

The final code is this:
Feel free to ask some doubt or show your thoughts in the comments, for an editorial of 500 HyperKnight problem, check out vexorian Link awesome tutorial.

Java 7 in Xubuntu 12.04

Hello, I'm here today to show to present the easiest way I've found to install both JRE and JDK version 1.7.xx in Xubuntu 12.04 (I think it works in all 'buntu' 12.04 versions). So, to start off, you have to add the following repository for your system:

sudo add-apt-repository ppa:webupd8team/java

Then, update all your repositories:

sudo apt-get update 

Kicking the installation off:

sudo apt-get install oracle-java7-installer

And finally, exporting $JAVA_HOME and $JDK_HOME to your $PATH environment variable:

export JAVA_HOME=/usr/lib/jvm/java-7-oracle
export JDK_HOME=/usr/lib/jvm/java-7-oracle/

Now, your latest version of Java 7 is up and running, to check if everything went alright, you should check:

java -version

and

javac -version

and see if they point out to the version you've just installed. So, hope it help you ;)

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.

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/