Match Editorial

SRM 254
Tuesday, July 26, 2005

Match summary

SRM 254 kicked off at the crack of dawn in the United States. In Europe, Asia and Australia, the hour was slightly more reasonable, and coders flocked from these regions. In division 1, kalinov had the most points from the coding phase. However, the challenge phase hurt him as he lost 50, while misof gained 50 and took first place. However, kalinov's score was still high enough to give him second place, beating out bladerunner who took third. In division 2, the top three spots were all taken by first time competitors: Issi, __OK__, macin.

The Problems

BalancedGame
Used as: Division Two - Level One:

Value	250
Submission Rate	242 / 299 (80.94%)
Success Rate	184 / 242 (76.03%)
High Score	nickel for 243.68 points (4 mins 35 secs)
Average Score	182.11 (for 184 correct submissions)

The problem statement pretty much spelled out how to do this one. Examine each element of the input and count the W's and L's in it. If the number of W's is less than ceil((N-1)*p/100) or the number of L's is less than ceil((N-1)*q/100), then the that player is unbalanced.

ListeningIn
Used as: Division Two - Level Two:

Value	500
Submission Rate	224 / 299 (74.92%)
Success Rate	110 / 224 (49.11%)
High Score	kdz13 for 485.02 points (5 mins 1 secs)
Average Score	375.74 (for 110 correct submissions)

Used as: Division One - Level One:

Value	250
Submission Rate	184 / 186 (98.92%)
Success Rate	148 / 184 (80.43%)
High Score	JongMan for 247.93 points (2 mins 36 secs)
Average Score	224.41 (for 148 correct submissions)

We can solve this problem using a greedy algorithm. Initalize a pointer to the first character of typed. Now, iterate over the characters in phrase. If the current character in phrase matches the character pointed to in typed, advance the point to the character in typed. Otherwise, add the character in phrase to the list of deleted characters. If, when you have iterated over all characters in phrase, the pointer to the character in typed is past the last character, you have a match, and can return the deleted characters. Otherwise, return "UNMATCHED".

    int p = 0;
    String ret = "";
    for(int i = 0; i<phrase.length(); i++){
        if(p<typed.length() && phrase.charAt(i) == typed.charAt(p))p++;
        else ret += phrase.charAt(i);
    }
    if(p!=typed.length())return "UNMATCHED";
    else return ret;

Piglets
Used as: Division Two - Level Three:

Value	1000
Submission Rate	89 / 299 (29.77%)
Success Rate	12 / 89 (13.48%)
High Score	Issi for 672.56 points (22 mins 14 secs)
Average Score	534.53 (for 12 correct submissions)

Used as: Division One - Level Two:

Value	500
Submission Rate	129 / 186 (69.35%)
Success Rate	77 / 129 (59.69%)
High Score	misof for 453.54 points (9 mins 17 secs)
Average Score	291.82 (for 77 correct submissions)

There are two different ways to do this problem. The more commonly used algorithm uses recursion to determine where the piglet should go. Each piglet considers the current situation, and all possible positions and asks the question: "If I go in this position, what will the other piglets do, and how good will that be for me?" Most coders basically took this approach, using dynamic programming to make their solutions run in time -- once you know what will happen from a particular situation, you should avoid computing it again.

This less commonly used, but much simpler and slicker solution goes like this:

    if(trough.charAt(0) == '-')return 0;
    if(trough.charAt(trough.length()-1) == '-')return trough.length()-1;
    int idx = trough.lastIndexOf("--");
    if(idx != -1)return idx;
    return trough.indexOf("-");

First, if one of the ends is open, our piglet takes it. Next, we find the rightmost occurrence of "--", if there is one, and go at that position. This may seem counterintuitive because the problem statement says to pick the leftmost when ties occur. However, at the end of the simulation, when the pigs who come in are sandwiched immediately, they will pick the leftmost spots first, since the delay is 0 for them. Hence, every spot to the left of the spot we pick will be filled up before we are finally sandwiched. If we were to pick a spot further left the delay would be less, as there would be less open spots to our left. If we picked the spot one position to the right, the delay would be the same, while spots further right must cause an immediate sandwich. Finally, if there is no occurrence of "--", simply take the leftmost open spot, if there is one.

SelfCatalogue
Used as: Division One - Level Three:

Value	1000
Submission Rate	21 / 186 (11.29%)
Success Rate	17 / 21 (80.95%)
High Score	liympanda for 643.47 points (24 mins 10 secs)
Average Score	511.62 (for 17 correct submissions)

A brute force approach to this problem runs with plenty of time so long as you do a little bit of pruning. The basic algorithm uses recursion to try many possible counts.

A good first step is to figure out an upper bound on the total number of digits in a valid sentence. If there is a count less than 10, but more than 0 for every digit, then there are 20 total digits. This suggests that perhaps 2 of the counts could be 10 or higher, for 22 digits total. If 3 or more of the counts were 10 or higher, there would have to be at least 30 digits, which is a lot more than 3 double digit numbers provide. So, we know that the sum of the counts is at most 22. It turns out that if we generate all of the possible counts whose sum is 22 or less and which are consistent with the input, we can easily check them and run the solution can run in time, provided you generate the counts in lexicographic order.

int[] it;
int[] a = new int[10];
int cnt = 0;
public int[] construct(int[] a){
    it = a;
    if(go(0,22))
        return it;
    else 
        return new int[0];
}

    /*
    * The go function tries to place a count for digit d,
    * bounded above by r.  r starts at 22, the upperbound
    * for the sum of the counts, and is decreased in
    * recursive calls to ensure that the sum stays at 22 or
    * less.  The function returns true if a valid solution
    * is found, and false otherwise.
    **/

boolean go(int d, int r){
    if(r<0)return false;
    if(d == 10){
        for(int i = 0; i<10; i++)a[i] = 0;
        for(int i = 0; i<10; i++){
            if(it[i]>0){
                a[i]++;
                if(it[i]<10)a[it[i]]++;
                else {
                    a[it[i]%10]++;
                    a[it[i]/10]++;
                }
            }
        }
        for(int i = 0; i<10; i++){
            if(a[i] != it[i]){
                return false;
            }
        }
        return true;
    }
    if(it[d] == -1){
        it[d] = 0;
        if(go(d+1,r))return true;
        for(int i = 1; i<=r; i++){
            it[d] = i;
            if(go(d+1,r-i))return true;
        }
        it[d] = -1;
        return false;
    }else{
        return go(d+1,r-it[d]);
    }
}

The code above can be further optimized in many ways (it runs in about 1.5 seconds as is on some cases). For one thing, once we have already assigned some digits, we can easily come up with a better lower bound for some of the counts. For instance, if we have already assigned the fact that there are '2 occurrences of 1', then there must also be at least 1 occurrence of 2.

We can also find better upper bounds on the counts for some digits. For instance, there can certainly be at most 3 occurrences of 9. If there were 4 occurrences, then three of the counts would have to be 9, which would make more than 22 total digits. If we add similar upper bounds for all the digits, the runtime drops off significantly. There are all sorts of further optimizations you could add if you felt inclined to do so, but they aren't needed.