Tuesday, April 6, 2004 Match summary The last match before the TCCC may not have been the warmup 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 1^{st}, 2^{nd} and 3^{rd}, 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, Uranium235, rounded out the top 3.
The ProblemsScoringEfficiencyUsed as: Division Two  Level One:
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. Used as: Division Two  Level Two: Used as: Division One  Level One:
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 (feedback_{i} == '') if(feedback.containsCharacter(word_{i})) return false endif else if(feedback_{i} != word_{i}) return false endif endif end for return true endOnce 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:
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(n^{2}). This gives us O(n^{3}) 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(n^{4}) algorithm: set validPairs; foreach potential h(0), h(1) pair tmp = "" for (i = 1 to lengthof(u)) if(u_{i} == 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(n^{4}). This is good enough, but its a bit slow. It turns out we can do as well as O(n^{2}). 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(n^{2}) total. Can anyone do better? AlienMultiplication Used as: Division One  Level Two:
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*bc)%pow10[6]==0 && errors<bestErrors){ bestErrors = errors; return; } if (errors >= bestErrors1) 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)*10^{5} = 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:
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 4^{th} 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 InclusionExclusion 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 2^{m} 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 nonzero 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. As pointed out above, the inclusionexclusion 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 inclusionexclusion 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. 
