Wednesday, August 1, 2007 Match summaryThis match, with the money prizes sponsored by TopCoder itself, attracted 1109 coders, including 5 targets. They faced a tricky set of problems in both divisions. Unfortunately, due to an error in one of the problems, the results from Division 2 had to be removed from the statistics. In Division 1, the submissions started to pop up very quickly with many competitors solving the 250 problem in less than 5 minutes. Soon after that, the solutions for the 500 started to come up, but surprisingly most of them were from blue and yellow coders, with the higher rated coders taking their time. That's often a sign that there is some nonobvious trickiness in the problem, and this time was no exception. Most of the quick submisions were later brought down in the challenge phase and system tests. With around 30 minutes before the end of the coding phase, Petr submitted his third problem, and seemed to be in a comfortable situation to win the match. But very soon after his initial submission he spotted a small bug and was forced to resubmit, which made him lose the lead. After the eventful challenge phase and the system tests, there were three targets ACRush, Petr, and SnapDragon in the top four, but it was zhuzeyuan who claimed the win, and came very close to regaining his target status as well. Congratulations! Even though it won't show up in their profiles, the top performers in Division 2 did a great job on this difficult set, and I'm confident it won't take them long to move up to Division 1, this time for good. The ProblemsSearchBoxUsed as: Division Two  Level One:
String matching is a common, and well known problem. Many more or less sophisticated algorithms exist. But here, with a text no longer than 50 characters, the simplest naive algorithm is more than sufficient. Let's forget for a moment about the "Whole Word" part and look how the search alone can be implemented. return text.indexOf(search, start); Luckily Java already has a method that does exactly what we need; the String.indexOf(String, int) method will find the first occurrence of search inside text starting from the index start, and even return 1 if the match is not found. Of course one can achieve the same with just two loops and comparing character after character, but I would recommend using the builtin functions of your language whenever it's possible for a few reasons:
Going back to the original problem, we still need to take care of the "Whole Word" option. We don't want to destroy our simple and clean code by adding dozens of ifs and hacks to handle corner cases, so we will use a simple trick instead. 1 public int find(String text, String search, String wholeWord, int start) { 2 if (wholeWord.equals("Y")) { 3 search = " " + search + " "; 4 text = " " + text + " "; 5 } 6 returntext.indexOf(search, start);//the general search function discussed above 7 } If wholeWord is "N" we don't need to change anything, the indexOf function will do the work. If it's "Y" we surround the search by spaces, to make sure it won't match a word that is a substring of another word. Additionally we add a space to the beginning and to the end of the text, to make the words touching the edges surrounded by spaces too. The one question that might not be obvious here is: how does adding these space affects the starting and resulting indices? Luckily it doesn't change a thing, by adding a space to the beginning of the text, we make the starting index point one character before the original, and that's good because now we want to match a leading space too. In the same way the returned index is the index of a space before the matched word, which is fine, as the text has one character added at the beginning. With the very low success rate on this problem, I guess the lesson is that, even if a problem looks easy, one should always stop and think before rushing into coding, and try to come up with a way to make the implementation as simple as possible. WhiteHatsUsed as: Division Two  Level Two: Used as: Division One  Level One:
Let's say there is a total N people, out of which W wear white hat. In that case, what should the count array look like? The answer is:
All that's left to do is check if the given array has the property described above, for some value of W. One of the ways to do that is to count the number of occurrences of each element in count, and then loop through all the possible values for W. The sample code follows. 1 public int whiteNumber(int count[]){ 2 int N = count.length; 3 int numbers[]= new int[51]; //elements in count are between 0 and 50, inclusive. 4 for(int x:count) numbers[x]++; 5 if(numbers[0] == N) return 0; //All hats are black. 6 for(int W=1;W<numbers.length;W++){ 7 if( numbers[W1] == W && numbers[W] == NW ) return W; 8 } 9 return 1; //No W was found. 10 } You can see that the condition inside the second loop is a direct translation of the two points stated before. The corner case of W=0 is handled separately to avoid accessing numbers[1]. As a side note, we can avoid the second loop altogether by noticing that W must be the maximal element in count, so that's the only value we really need to check. ElectionUsed as: Division Two  Level Three:
This is the problem that caused the division 2 rating changes to be reverted. It has an incorrect greedy solution that is so appealing that myself, three problem testers, and 15 coders during the match coded it in the same, flawed way. Only after the match was it pointed out in the forum that the way it distributes the votes is not always optimal. As of this writing, I still don't know how to write a correct solution, so I would love to hear from someone who managed that. If anyone is interested in the reference solution used during the match, here is the analysis I wrote before I knew that it didn't work. Treat finding a flaw in the logic as an exercise. Warning: The solution below is not correct and left over only for educational purposeLet's define an array finalOrder that will contain the final candidates ranking, according to our wishes. Since it must match the wishList, for every element k where p = wishList[k] is not 1, finalOrder[p] = k. Now, what about the candidates where wishList is equal to 1? We don't care where they end up, but since we are looking for the solution with the minimal number of additional votes, it's never optimal to change the relative order which they are already in. Take a look at the following example.
The initial ordering is (C, B, E, A, D). Now we want to have the candidate B on the place 0, and the candidate D on the place 3, which makes the ordering look like (B, _, _, D, _). Since there is no point in changing the order of candidates (C,E,A), we put them in the same order on the free spots, which finally gives (B, C, E, D, A). The pseudocode generating the finalOrder can look like this: 1 int[] generateFinalOrder( int[] currentOrder, int[] wishList) { 2 int[] finalOrder={1}; 3 boolean[] used = {false}; //array used to mark the candidates that were already placed on a position. 4 for(i=0; i<wishList.length; i++) if(wishList[i] != 1) { //first filling the elements with fixed positions. 5 finalOrder[wishList[i]] = i; 6 used[i] = true; 7 } 8 for(i=0; i<finalOder.length; i++) { //now filling all the empty spots 9 if( finalOrder[i] != 1 ) continue; //alredy filled 10 for(j=0; j<currentOrder.length; j++){ 11 candidate = currentOrder[j]; 12 if( !used[candidate] ) { //the highest ranked candidate that wasn't placed so far. 13 finalOrder[i] = candidate; 14 used[candidate] = true; 15 break; // breaking the j loop. 16 } 17 } 18 } 19 return finalOrder; 20 } The currentOrder here holds the indices of the candidates, sorted by decreasing number of votes (and a tiebreaker as in the problem statement). What this function does is first place the candidates according to the wishList and than fill the empty spots with the remaining candidates, without breaking the ordering from the currentOrder. It can be also implemented with a lesser complexity, but with no more than 50 candidates it doesn't really matter. Now that we have determined the final ordering, computing the minimum required number of additional votes becomes quite simple. Just look at the candidates starting from the end. Obviously we don't need to add any votes to the candidate who's meant to end the last. For the second to last we need only as many votes as are needed to overcome the last one  and so on, for all the others, every time we add the minimal number of votes needed to overcome the previous candidate (keeping the tiebreaker rule in mind). The total number of votes we added is the final answer. The code follows. 1 public int votesNeeded(int[] votes, int[] wishList) { 2 int result = 0; 3 int[] currentOrder = ... //Just a sorting, so the code ommited. 4 int[] finalOrder = generateFinalOrder( currentOrder, wishList); //the function described above. 5 for(i = finalOrder.length  2; i >= 0; i){ //starting from the second to last and moving backwords 6 int a = finalOrder[i]; 7 int prev = finalOrder[i+1]; 8 if( votes[a] < votes[prev] ){ 9 result += votes[prev]  votes[a]; //adding votes to make a and prev have the same number; 10 votes[a] = votes[prev]; 11 } 12 if( votes[a] == votes[prev] && a > prev ){ //if needed adding one more vote to satissfy the tiebreaker. 13 result ++; 14 votes[a]++; 15 } 16 } 17 return result; 18 }ReverseDistance Used as: Division One  Level Two:
This problem had a short and simple statement, and as often happens a solution that was short, simple... and incorrect. Many coders went for a solution that tries every number, computes its reverse, and checks the difference between them. While this is obviously correct, the running time is what causes the problem. The key observation is that even though the input is at most 1000000, the answer can be as big as twelve digits. That makes it impossible to simply try all the possibilities. How not to get trapped by a problem like this? There is no definite answer but there are few hints that could help you avoid it.
The "divide in two" solutionTry and write your equation in a manner: a b c d e f g h  h g f e d c b a  i j k l m n o pWhere each letter represents a single digit (imagine that numbers are aligned with leading zeros to have the same length). The same thing can be written as: i j k l m n o p + h g f e d c b a  a b c d e f g hWe know the ijklmnop part, as that's what we are given. Now imagine you know the dcba. From the equation above you can see the mnop + dcba = efgh  well, not exactly but the last four digits of mnop + dcba are efgh. So if we already know mnop and we assumed that we know dcba, we can easily compute the efgh. And now, when we have efgh we can reconstruct the whole abcdefgh! The remaining question is: where to take the first half of the number from? Just brute force it. Since it's only half of the digits, the number of options is small enough to check them all. You still need to code it carefully, to handle cases like odd number of digits and tom make sure it runs fast enough. The fairly simple, working Java solution follows: 1 public class ReverseDistance { 2 final long rev(long x){ 3 long r =0; 4 while(x>0){ 5 r=r*10+x%10; 6 x/=10; 7 } 8 return r; 9 } 10 11 int len(long x){ 12 int r=0; 13 while(true){ 14 r++; 15 x/=10; 16 if(x==0)return r; 17 } 18 } 19 20 public String find(int difference) { 21 for(long p=0;p<200000;p++){ 22 long rp = rev(p); 23 long q = rp+difference; 24 int len = len(p); 25 for(int totalLen = 2*len1;totalLen<=2*len;totalLen++){ 26 String qs = ""+q; 27 while(qs.length()>totalLenlen)qs = qs.substring(1); 28 while(qs.length()<totalLenlen)qs = "0"+qs; 29 long y = Long.parseLong(p+qs); 30 if(yrev(y)==difference)return ""+y; 31 } 32 } 33 return "NONE"; 34 } 35 } The greedy solutionWhen I thought about this problem for the first time I wanted to allow inputs as big as 2,000,000,000, so the solution described above won't work on it. I coded up a solution that is entirely based on greedily picking digits, starting from the outmost ones and moving towards the middle. It's not that elegant, as there were quite a few cases to handle to make it work, so I'll just sketch the idea rather than giving a full solution. Assume that a number looks like azb where a and b are single digits and z is a sequence of digits. The reverse of it looks like bya, where y is the reverse of z. Furthermore, assume that azb has the same number of digits as bya (bya can have leading zeros), and that azb > bya. That gives an equation: a z b  b y a  d x fLets look just at the last digits b  a = f, since if azb > bya then a >= b as well. The last digit equation is actually 10 + b  a = f. We can rewrite it as a  b = 10  f It can have a few results, but remember that we are looking for the smallest number that results in the difference, so we want the digit a to be as small as possible. In that case we can set it to: a = 10  f b = 0 Now look at the rightmost digits. Since we already know that a  b = 10  f, then the digit d must be either 10  f or 9 f. If it's not, the difference can not be achieved, and you should return "NONE". If it is, we can consider a and b as computed and move to computing z and y in the same manner. As I said there are more details into it, but that should be enough to give you an idea of how to construct a fully working solution. WeighingScale Used as: Division One  Level Three:
The solution for this problem is quite complicated so I'll just start from the basic observations, and see how it goes from there... Iteration 1Removing all the difficult bits from the statement we get "bla bla bla, return the number of different pairs of weights that, bla, bla, bla." There is only around 1100 of these pairs, so it seems doable to check them one by one.1 int[] count(String[] measures, int A, int B){ 2 int[] result = {0,0,0}; 3 n = measures.length; 4 for( {C, D} in {0..n1}^2 ){ //all pairs of indices 5 if( {A,B} & {C, D} != {} ) continue; //A and B are already taken 6 if( something ) increment one position in result. 7 } 8 return result; 9 } Iteration 2Now we can look a bit closer at what exactly we need to check for each of the pairs.The number of different pairs of weights you can put on the right pan to make it lighter than the left pan, the number of pairs to make both pans the same weight, and the number of pairs to make the left pan lighter.Keeping in mind that each weight can have only one of the three values  10, 20, or 30 grams. We can again check all the 81 combinations and directly see which side of the scale is heavier. The difficult bit is checking if the combination of the values is possible to achieve, considering the results in measures, but for now let's just focus on the part we know how to do. 1 //... We are inside the C,D loop 2 possibleOutcomes = {0,0,0}; 3 for( {w1,w2,w3,w4} in {10,20,30}^4 ){ 4 //Somehow checks if weights A,B,C,D can tak values w1,w2,w3,w4 respectively: 5 if( !possible({A,B,C,D}, {w1,w2,w3,w4}) ) continue; 6 if( w1 + w2 > w3+ w4 ) possibleOutcomes[0] = 1; //left heavier 7 if( w1 + w2 == w3+ w4 ) possibleOutcomes[1] = 1; //same 8 if( w1 + w2 < w3+ w4 ) possibleOutcomes[2] = 1; //left lighter 9 } 10 if( sum(possibleOutcomes) == 1 ){ //checking if there is only one possible outcome 11 result += possibleOutcomes; 12 }So we loop through {w1,w2,w3,w4} and, ignoring the combinations that are not possible, compare the total weight of the left pan with the right pan. The line number 10 implements the sentence "You should only consider the pairs that make the result unambiguously predictable based on the results in measures." If we are able to predict the outcome unambiguously, that means that the left pan was always in the same relation to the right pan, thus possibleOutcomes has only a single 1 in it. The last step is to increment the result on the correct position. Iteration 3Now the solution is almost ready and we still haven't had to do anything difficult! The only part left is a function checking if the weights with indices {A,B,C,D} can have values {w1,w2,w3,w4}. That's the time when we need to take a closer look at the measures matrix. It should be obvious that if we have two weights x and y and measures[x][y] == '+' than for sure x doesn't weigh 10 grams, nor y weigh 30 grams. Moreover, if we have a weight z such as measures[y][z] == '+', then there is no other way to assign values than (x = 30; y = 20; z = 10). To check the possible values for all the weights we can do the following:
1 int dfs( int p, char sign, boolean[]used) { 2 if(used[p]) return 0; 3 used[p] = true; 4 int res = 0; 5 for(int q=0; q <n ;q++){ 6 //Edges with '=' don't add anything to the result, edges '+' or '' do. 7 if(measures[p][q] == '=' ) res = max(res, dfs( q, sign, used)); 8 if(measures[p][q] == sign ) res = max(res, 1 + dfs( q, sign, used)); 9 } 10 return res; 11 } 12 13 14 int[] count(String[] measures, int A, int B){ 15 int[] result = {0,0,0}; 16 possibleWeights = {{true}}; 17 for( x =0; x<n; x++ ){ 18 int plusDepth = dfs(x, '+', new boolean[n]); 19 int minuDepth = dfs(x, '', new boolean[n]); 20 //updating possibleWeight[x] based on the dephts; 21 } 22 // ... 23 // Inside the loop with the four possible weight values 24 if( ! possibleWeights[A][w1]  ! possibleWeights[B][w2]  25 possibleWeights[C][w3]  ! possibleWeights[D][w4] ) continue; 26 //the rest as before 27 } 28And that's all. It wasn't so hard, was it? System> slex is compiling the 1000point problem. System> slex is testing the 1000point problem. System> slex is testing the 1000point problem. System> slex is testing the 1000point problem. System> slex is testing the 1000point problem. Oops it disagrees on the example 3. Is it a wrong example test (again)? ... Iteration 4Back to the drawing board. Let's look at example 3.So, we have only one pair of weights to consider {2,3}, our possibleWeights table looks like:3) {"??+?", "???+", "???", "???"} 0 1 Returns: {1, 0, 0 } We know that w0 > w2 and w1 > w3 thus w0+w1 must be heavier than w2+w3.
So in example we can have 30+20 > 20+10, which makes the left pan heavier, but we can also have 20+20 == 20+20, which makes the both pans the same weight. But wait! How can both w0 and w1 be 20 if the measures says that w1>w2? Well it can't be, it's just that our program doesn't know it yet. The example shows that it's not only important what values a single weight can have, but also if all the four values together match the relation defined by measures. To fix that we introduce one more matrix, Relation[n][n], where each cell can have one of the 4 values:
1 private boolean check(int a, int b, int w1, int w2) { 2 if (Relation[a][b] == ?) 3 return true; //no relation 4 if (Re[a][b] == '' && w1 >= w2) 5 return false; 6 if (Re[a][b] == '=' && w1 != w2) 7 return false; 8 if (Re[a][b] == '+' && w1 <= w2) 9 return false; 10 return true; 11 } 12 13 /** This gets {A,B,C,D}, {w1,w2,w3,w4} **/ 14 private boolean check(int[] ind, int[] w) { 15 for (int i = 0; i < ind.length; i++) 16 for (int j = i + 1; j < ind.length; j++) { 17 if (ind[i] == ind[j]) 18 return false; 19 if (!check(ind[i], ind[j], w[i], w[j])) 20 return false; 21 } 22 return true; 23 } 24Adding this check in the innermost loop makes the solution pass. That was basically the reference solution, and the thought process behind it. You can see the similar structure in SnapDragon's code from the match. 
