|
Match Editorial |
Tuesday, April 6, 2004
Match summary
The last match before the TCCC may not have been the warm-up that competitors were looking for, as division 1 had one of the hardest sets in recent memory -- only 10 competitors solved more than 1 problem. Of those, tomek, bladerunner and Klinck were the only coders to solve all 3 problems, taking 1st, 2nd and 3rd, respectively. In division 2, coders had it a bit easier, with most coders solving the easy, and over half solving the medium. First timer kaylin took first by less than a point over Artist_, while long time TopCoder, Uranium-235, rounded out the top 3.
The Problems
ScoringEfficiency
Used as: Division Two - Level One:
Value 250 Submission Rate 156 / 172 (90.70%) Success Rate 148 / 156 (94.87%) High Score NeverMore for 243.67 points (4 mins 36 secs) Average Score 190.96 (for 148 correct submissions)
A fitting problem to follow March Madness. In order to calculate the points per shot, you need to know 3 things: the total number of points, the number of free throws attempted, and the number of field goals attempted. The simplest way to find all of these is to just have 6 separate cases, one for each possible value of the elements. Clearly, you should just copy and paste these strings from the problem statement, since typing them in yourself is a good way to introduce typos. That was by far the most common solution, and pretty much everyone got it right. There are a few ways in which you could get clever if you really wanted to, but with only 6 cases to deal with, coding each one up is pretty simple.
If you want to see how this metric works in the NBA (or how it worked in the '00-'01 season), check this out.
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 122 / 172 (70.93%) Success Rate 83 / 122 (68.03%) High Score SamBob for 462.54 points (8 mins 13 secs) Average Score 324.84 (for 83 correct submissions)
Value 250 Submission Rate 153 / 158 (96.84%) Success Rate 129 / 153 (84.31%) High Score antimatter for 246.85 points (3 mins 13 secs) Average Score 213.20 (for 129 correct submissions)
This is a bit tougher than it looks at first glance. Its pretty simple to verify that the characters which have been revealed so far match up. But then you have to make sure that there isn't a letter, some of whose instances have been revealed, and some of whose instances have not. Lets consider a method, matches, which takes strings feedback and word, and returns true if word matches the feedback. Once we have this part written, we're 90% done. The first thing we want to do is make sure the strings are the same length. Assuming they are, we look at each character in word. If a character is in word, opposite a '-' in feedback, then we need to make sure the same character doesn't appear anywhere in feedback. If the corresponding character in feedback isn't a '-', we just check that they match:
boolean matches(feedback,word)
if(lengthof(feedback)!=lengthof(word))return false;
for (i = 1 to lengthof(feedback))
if (feedbacki == '-')
if(feedback.containsCharacter(wordi))
return false
endif
else
if(feedbacki != wordi)
return false
endif
endif
end for
return true
end
Once we have this written, the rest of the solution is just a matter of checking each word. If there are zero that match, or more than one that matches, return "", otherwise return the matching word.
An alternative solution uses regular expressions to do the matching. A '-' can be any character that doesn't appear in feedback, so, we can build a regular expression out of feedback as follows (in Java):
String letters = feedback.replaceAll("-","");
String regex = feedback.replaceAll("-","[^"+letters+"9]");
Then, matching is exactly identical to regular expression matching. Note that the '9' is not a typo, but is neccessary to make are regular expression valid if letters = "".
Homomorphism
Used as: Division Two - Level Three:
Value 1000 Submission Rate 12 / 172 (6.98%) Success Rate 5 / 12 (41.67%) High Score Uranium-235 for 605.98 points (26 mins 55 secs) Average Score 473.17 (for 5 correct submissions)
This problem is a bit easier than it looks. Behind all the big fancy words, the algorithm is relatively simple. Basically, we need to find h(0) and h(1) so that if we simultaneously replace all of the 0's in u with h(0) and all of the 1's in u with h(1), we get v. Now, without any loss of generality, lets say that the first character of u is a '1'. Then, h(1) needs to be the first i characters of v, for some i >= 1. Thus, there are O(n) possibilities of h(1). Now, to find h(0), we can just try every substring of v, of which there are O(n2). This gives us O(n3) combinations of h(0) and h(1) to consider. Finally, to check a given h(0) and h(1), we can just do it in the obvious way: intiialize tmp = "", iterate over characters of u, and append h(0) or h(1) to tmp, depending on the character in u. This adds another factor of n to your runtime, and you end up with an O(n4) algorithm:
set validPairs;
foreach potential h(0), h(1) pair
tmp = ""
for (i = 1 to lengthof(u))
if(ui == 0)
tmp = tmp + h(0)
else
tmp = tmp + h(1)
endif
end for
if(tmp == v)
validPairs.add(h(0),h(1))
endif
endfor
return validPairs.size()
The algorithm above is O(n4). This is good enough, but its a bit slow. It turns out we can do as well as O(n2). Lets continue to assume that u starts with a '1'. First, we count the number of 0's and 1's in u, z and o, as well as the number of leading ones, leading. Now, we know that z*|h(0)| + o*|h(1)| == |v|. Thus, given h(1), we can find the length of h(0). Since u starts with leading ones, the first leading * |h(1)| characters of v are accounted for. The next |h(0)| characters in v make up h(0). Thus, we can find all potential h(0), h(1) pairs in time O(n), and we can then check the pair against v in time O(n), for O(n2) total. Can anyone do better?
AlienMultiplication
Used as: Division One - Level Two:
Value 600 Submission Rate 20 / 158 (12.66%) Success Rate 8 / 20 (40.00%) High Score tomek for 377.76 points (25 mins 8 secs) Average Score 286.54 (for 8 correct submissions)
This problem was pretty hard, but when it comes down to it, its just brute force with some pruning. First off, note that the answer is at most 6, since we can just change the 6 digits of c. So, as we are changing digits, if we ever get to 5, and still aren't done, then we shouldn't bother to change any more. Once we figure that out, we should work from right to left. Once we have the rightmost (ones) digits of a, b and c fixed, and (a*b)%10 == c%10, the next digit to the left can no longer mess up what we already have. That is, regardless of what we do to the hundreds digits of a, b and c, we will still have (a*b)%10 == c%10. This suggest a recursive solution, where we first change the tens digits then the hundreds digits, and so on. We stop recursing if we have ever made 5 or more changes, and aren't done yet. Also, to make things a bit quicker, once we have changed the digits of a and b in a particular place, we can tell right away what the corresponding digit of c should be. Here is dgarthur's solution, where pow10 is an array with powers of 10.
int bestErrors = 6;
void recursiveCorrect(long a, long b, long c, int pos, int errors)
{
if ((a*b-c)%pow10[6]==0 && errors<bestErrors){
bestErrors = errors;
return;
}
if (errors >= bestErrors-1) return;
for (int d1 = 0; d1 < 10; d1++)
for (int d2 = 0; d2 < 10; d2++){
int newErrors = errors;
long newA = setDigit(a,pos,d1);
long newB = setDigit(b,pos,d2);
if (a != newA) newErrors++;
if (b != newB) newErrors++;
int d3 = (int)getDigit(newA*newB,pos);
long newC = setDigit(c,pos,d3);
if (c != newC) newErrors++;
recursiveCorrect(newA, newB, newC, pos+1, newErrors);
}
}
Now, there is clearly some concern that this solution might timeout. We are changing at most 5 out of 18 digits, and there are 10 possibilities for the new value of each digit. This gives us an upper bound of C(18,5)*105 = 8.6E8, which is too many. However, in reality, the number is much smaller, since most changes to digits in a or b will also require a change in c. A solution following this algorithm should run in well under a second.
SquareFree
Used as: Division One - Level Three:
Value 1000 Submission Rate 16 / 158 (10.13%) Success Rate 6 / 16 (37.50%) High Score tomek for 800.51 points (14 mins 58 secs) Average Score 620.46 (for 6 correct submissions)
Let's start by counting the number of square free integers less than or equal to k, for some k. Instead of doing this directly, we'll calculate the number of integers less than or equal to k that have a perfect square as a factor, and subtract this from k. If an integer has a perfect square as a factor, then it has the square of a prime as a factor, since any square can be broken up into the product of some primes squared. Therefore, we only need to count the integers with squares of primes as factors. Consider the number of integers less than or equal to k with 4 as a factor (4 is the square of 2). Every 4th number has 4 as a factor, so there are floor(k/4) integers with 4 as a factor. Similarly, there are floor(k/9) integers with 9 as a factor. However, we can't just add these together to get the number of integers with 4 or 9 as factors, since we would end up counting the integers with 36 as a factor twice (the have both 4 and 9 as factors). The simplest way to deal with this is to use the Inclusion-Exclusion Principle. To avoid double counting integers divisible by 36, we subtract floor(k/36). So, if we are considering the first three primes squared, then there are floor(k/4) + floor(k/9) + floor(k/25) - floor(k/36) - floor(k/100) - floor(k/225) + floor(k/900) integers with one of the 3 squared primes as factors. Unfortunately, there are 2m terms to the full equation, if we have m primes to consider. Luckily, most of those are 0, and don't need to be computed. We can find all the non-zero terms using recursion as follows (assume primesSquared is a sorted array holding enough primes squared so that the biggest one is bigger than k).
//idx is the index of the prime we are looking at //soFar is the product of some primes squared //k is as described above //this returns the number of integersOnce you get this far, you are just a couple steps away. First, you need to compute primesSquared. This can be done fastest with the Sieve of Eratosthenes. Finally, we need to find an integer m such that m - recurse(0,1,m) == n. A simple binary search will suffice for this.
//less than or equal to k which have //soFar and some prime squared as a factor int recurse(int idx, long soFar,int k){ int ret = 0; //If primesSquared[idx]*soFar > k,
//then floor(primesSquared[idx]*soFar/k) == 0, //so all further terms are 0 if(primesSquared[idx]*soFar > k)return 0; //Otherwise, add the number of integers
//divisible by primesSquared[idx]*soFar to ret ret += (int)(k/primesSquared[idx]/soFar); //Then, add terms that don't include primesSquared[idx], //but do include soFar and some other prime squared ret += recurse(idx+1,soFar,k); //Finally, subtract terms that include //both primesSquared[idx] and soFar and some other prime squared ret -= recurse(idx+1,soFar*primesSquared[idx],k); return ret; }
As pointed out above, the inclusion-exclusion principle could potentially result in a lot of calculations. However, a bit of analysis suggests that we don't need to worry about it too much. The product of the first 6 primes squared is 4*9*25*49*121*169 = 901,800,900. So, at most we will need to consider terms made from 6 primes squared (of which there are a lot). However, once we get up into the higher primes, most of the terms with more than a single prime squared can be ignored. Analysis gets a bit tricky beyond here (it is possible, but beyond the scope of this article). Suffice it to say that it turns out you only need to consider about 50,000 terms, which is easy to do in 8 seconds. You have to do this as many as 31 times (for the binary search), but that is still plenty fast. In fact, the slowest part of the whole algorithm ends up being the Sieve of Eratosthenes, which takes O(sqrt(n) * log(n)).
An alternative solution involves using the M'bius Function to compute the sum of the all the terms we found using the inclusion-exclusion principal. The math behind this approach is a bit more involved, but it boils down to computing the M'bius Function up to about sqrt(n). Without going into the details, here is dgarthur's solution along these lines:
public int getNumber(int n){
long lb = 1;
long ub = 1700000000;
long i, j;
long maxMoebius = (long)Math.sqrt(ub);
int moebius[] = new int[(int)maxMoebius];
int prime[] = new int[(int)maxMoebius];
for (i=0; i<maxMoebius; i++){
moebius[(int)i] = -1;
prime[(int)i] = 1;
}
for (i=2; i<maxMoebius; i++){
for (j=2*i; j<maxMoebius; j+=i) prime[(int)j] = 0;
if ( ((long)Math.sqrt(i))*((long)Math.sqrt(i)) == i){
for (j=i; j<maxMoebius; j+=i)
moebius[(int)j] = 0;
}else if (prime[(int)i] == 1){
for (j=i; j<maxMoebius; j+=i)
moebius[(int)j] = -moebius[(int)j];
}
}
while (lb < ub){
long m = (lb+ub)/2;
long thisN = m;
for (i = 2; i < maxMoebius; i++)
thisN -= moebius[(int)i] * (m / (i*i));
if (thisN < n)
lb = m+1;
else
ub = m;
}
return (int)lb;
}
You can read more about Square Free numbers and there applications at MathWorld.
