Match Editorial

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

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.

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

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)

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.

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

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