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