JOIN
 Match Editorial
SRM 259
Monday, August 22, 2005

Match summary

SRM 259 kicked off A few hours before the start of the Google Code Jam, providing one last chance for coders to practice their trade before switching arenas and tackling the quals. Division 1 coders were faced with a rather difficult problem set, particularly the medium problem which had many submissions, but few successful ones. Topping out the list was ploh, who would have got 5th if it weren't for 150 points during the challenge phase. ivan_metelsky had the highest score from coding, and took second, while rem rounded out the top 3. In division 2, xuezaiyue took first by a wide margin, followed by first timer e-yura and Chenhong.

# The Problems

CompetitionStatistics
Used as: Division Two - Level One:
 Value 250 Submission Rate 240 / 254 (94.49%) Success Rate 194 / 240 (80.83%) High Score topiori for 249.93 points (0 mins 28 secs) Average Score 222.41 (for 194 correct submissions)

The simplest way to do this is to loop over the elements in the input. As you go, keep a counter. If an element if positive, increment the counter, otherwise reset it to 0. The return value is simply the maximum value this counter achieves.

PrimePolynom
Used as: Division Two - Level Two:
 Value 600 Submission Rate 215 / 254 (84.65%) Success Rate 55 / 215 (25.58%) High Score vdave for 582.38 points (4 mins 58 secs) Average Score 440.82 (for 55 correct submissions)

The examples in this problem showed that the greatest return was less than 100, so a simple brute force approach to finding the first non-prime should work. Initialize M to 0, and then start iterating the values of the quadratic. For each value of the quadratic, check if it is prime. Almost all coders had the right basic approach, but many (almost 75%) failed because of bugs in their prime checker. The most common errors seem to be related to the number 1 (which is not prime) and 2 (which is prime). Here is a very simple way to find if a number if prime:

```    boolean isPrime(int N){
if(N<2)return false;
for(int i = 2; i*i<=N; i++){
if(N%i == 0)return false;
}
return true;
}
```

NumericalSequence
Used as: Division Two - Level Three:
 Value 900 Submission Rate 98 / 254 (38.58%) Success Rate 73 / 98 (74.49%) High Score King_Bette for 846.77 points (7 mins 12 secs) Average Score 591.92 (for 73 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 157 / 185 (84.86%) Success Rate 130 / 157 (82.80%) High Score lovro for 247.98 points (2 mins 34 secs) Average Score 204.91 (for 130 correct submissions)

At first, you might think that this problem would require some sort of complicated dynamic programming, or other algorithm. However, a little more thought leads to a simple greedy algorithm. In order for the sequence to be a palindrome, the two numbers on the ends must match. If they do, we can remove them, and continue working on the rest of the sequence. If not, then the smaller of the two must get bigger (there is no way for the bigger one to get smaller). Hence, we combine the smaller of the two end numbers with the one adjacent to it and continue with the resulting sequence.

SuperString
Used as: Division One - Level Two:
 Value 600 Submission Rate 159 / 185 (85.95%) Success Rate 43 / 159 (27.04%) High Score rem for 572.18 points (6 mins 19 secs) Average Score 430.56 (for 43 correct submissions)

Like the division 2 medium, only about a quarter of the submissions for this problem passed. In this case, it was the time limit that caused many failures.

First off, note that there are up to 2500 characters in the combined sequence. This is quite a few, but not so many that an O(N^2) algorithm won't work. That means that we can afford to consider every possible substring, as long as we are quick about it. The most common way to do this was simply with two nested loops like this:

```for(i = 0 to lengthof(s)-1){
int[] cnt = new int[26];
int goodness = 0;
for(int j = i to lengthof(s)-1){
int v = s[j]-'A';
if(cnt[v] == 0)goodness++;
else if(cnt[v] == 1)goodness--;
cnt[v]++;
//here we have the goodness of the substring from i to j, inclusive
}
}
```
From here, we just need to find the substring with the highest goodness, and we need to handle ties appropriately. Of substrings that start at the same place, we want shorter ones, so we only need to consider substrings for which the goodness has just increased. As long as you do that, runtime should be no problem, and you can use the built in string comparison functions to do the rest.

CardRemover
Used as: Division One - Level Three:
 Value 900 Submission Rate 80 / 185 (43.24%) Success Rate 25 / 80 (31.25%) High Score ivan_metelsky for 761.72 points (12 mins 35 secs) Average Score 612.38 (for 25 correct submissions)

To start off on this problem, let's think backwards. Say we are going to remove every card but the first and last ones. In that case there must be some card, call it X that is going to be the last on removed. If this is the case, then all of the cards to the left of X and all of the cards to the right of X (except the end cards) must be removed first. Since these two sets of cards can't affect each other, we can solve the two halves independently. Of course, if we can't remove all of the cards to the left, and all of the cards to the right, then we can't end up removing X at the end.

Now, there is another case. Let's say that we can't remove every card but the end ones. In this case there must be some card, X, which doesn't get removed. As before, we can try to remove the cards to the left and right of X independently. So, this leads us to a fairly simple algorithm to recursively solve the whole problem:

```    //returns the number of things that can
//be removed between a and b, exclusive.
int solve(int a, int b){
int ret = 0;
for(int x = a+1; x<b; x++){
int s1 = solve(a,x);
int s2 = solve(x,b);
if(s1 + s2 + 2 == b-a && match(a,b)){
//match returns true if cards a and b have sufficient
//conformity.  So here we can remove all cards to
//right and left and also card x.
ret = max(ret,s1+s2+1);
}else{
ret = max(ret,s1+s2);
}
}
return ret;
}
```
Of course, you need to add some memoization to cache the result for a particular (a,b) pair, or else you will time out.

By lbackstrom
TopCoder Member