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/