Monday, June 12, 2006 Match summary
The second TopCoder High School Single Round Match, first one for the Beta region, attracted 109 registrants (59 of them newcomers) and proved to be quite eventful. With challenge opportunities left in all 3 problems, the heat was rising as the end of the intermission approached. When the coding phase ended there were 209 problems open for challenge, 94 250-pointers, 77 500-pointers and 38 1000-pointers. The first few minutes of the challenge phase were a real bloodbath as 250-pointers failed all around to the dreaded poison = elixir case. All in all, during the challenge phase 24 250-pointers were brought down along with 10 500-pointers and 12 1000-pointers. This amounts to a grand total of 46 successful challenges (the systests took down only 21 solutions!). The ProblemsFountainOfLifeUsed as: Level One:
The math solution t >= pool / (poison - elixir)pool will always be positive and (poison - elixir) can be either positive, negative or zero. If (poison - elixir) is negative or zero, than the mixture will never become deadly since pool will be at least 1. If (poison - elixir) is positive then we need to find the minimal t for which the above holds true. Because pool / (poison - elixir) is a positive number and t must be at least equal to it, the minimal t is in fact equal to pool / (poison - elixir). Once you have this writen on the paper, coding it is quite simple. The following code solves the task: public double elixirOfDeath(int elixir, int poison, int pool){ if ( poison <= elixir ) return -1.0; return 1.0 * pool / (1.0 * (poison - elixir) ); } The most common error on this problem was the lack of '=' in the if, causing either wrong return value or a division by zero. ApocalypseSomeday Used as: Level Two:
The Brute-force solution public int getNth(int n){ int x = 665; while ( n > 0 ){ ++x; if ( Integer.toString(x).indexOf("666") != -1 ) --n; } return x; }The O(n) solution Another way to approach this problem is to further expand the idea that we used to examine the runtime of the BF solution. Beastly numbers can be divided into patterns, like ****666, ***666*, etc. For every pattern let us remember the last number we used to fill in the * in an array pat. In order to find the next beastly number, we simply iterate the array pat and use the next number for that pattern to form a beastly number, constantly keeping the smallest number found thus far. Since there is a fixed number of patterns and you will iterate them n times, the complexity is O(n). The exact details and the code for this solution are left as an exercise to the reader. For testing purposes the 100,000th beastly number is 22,230,666, the 1,000,000th is 177,966,663 and the 10,000,000th is 1,666,008,549. Wizarding Used as: Level Three:
The O(3^n) recursive solution string s, r; int bestpower; public void solve(int depth, String c){ if ( depth == s.length() ){ // check if we have an empty incantation if ( c == "" ) return ; // we have a candidate for the counterspell so we check it's power int power = 1; for (int i = 0; i < c.length(); i++ ){ power *= (c.charAt(i) - 'A' + 1); power %= 77077; } // compare the current counterspell and the best found thus far if ( power > bestpower ){ bestpower = power; best = c; } else if ( power == bestpower ){ if ( c.length() < best.length() ) best = c; else if ( c.length() == best.length() && c.compareTo(best) < 0 ) best = c; } } else { // first use the letter as-is solve(depth + 1, c + s.charAt(depth)); // next try to delete it solve(depth + 1, c); // now try to replace it if ( r.charAt(s.charAt(depth) - 'A') != '-' ) solve(depth + 1, c + r.charAt(s.charAt(depth) - 'A')); } } public String counterspell(String spell, String rules){ bestpower = -1; s = spell; r = rules; // start from the first character with an empty counterspell solve(0, ""); return best; } The non-recursive solutions Recursion was not necessary to solve this problem. Non recursive solutions exist. Check nordom's, kupicekic's, marek's and Burunduk1's challenge solutions for examples. Those solutions are not all the same -- they implement different algorithms. Some of those are quite difficult to come up with and code, and it would be too much to examine in detail each and every one of them, but here are a few useful observations:
|
|