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