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