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 eyura and Chenhong. The ProblemsCompetitionStatisticsUsed as: Division Two  Level One:
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. PrimePolynomUsed as: Division Two  Level Two:
The examples in this problem showed that the greatest return was less than 100, so a simple brute force approach to finding the first nonprime 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: Used as: Division One  Level One:
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. SuperStringUsed as: Division One  Level Two:
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. 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:
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. //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 == ba && 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. 
