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.

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.

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/