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 ProblemsBalancedGameUsed as: Division Two  Level One:
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((N1)*p/100) or the number of L's is less than ceil((N1)*q/100), then the that player is unbalanced. ListeningInUsed as: Division Two  Level Two: Used as: Division One  Level One:
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: Used as: Division One  Level Two:
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. 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:
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. 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,ri))return true; } it[d] = 1; return false; }else{ return go(d+1,rit[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. 
