Our current solutions to the problems in this volume are below. If a problem is not shown here, then we have not posted a solution yet.

# #10900 - So you want to be a 2n-aire?

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: easy Algorithms Used: dynamic programmingmath Solution Description: At the outset, it's very easy to believe that you should guess if p > 0.5, and leave if p < 0.5, but this is not the case. On earlier questions, the amount you stand to gain in the future is very high, so you will end up guessing even if p < 0.5. It is easiest to calculate the expectation by starting from the end of the game and working backwards. Let a[i] be your expectation when there are i questions remaining. a[0] = 2^n (If there are no questions left, then you must have won the game) Now to calculate a[i], we have to look at two cases. You either walk away with i questions remaining, and win 2^(n-i), or you take a guess. If you guess, your expected win is p*a[i-1]. We want to find the point at which it makes no difference whether you guess or walk. Call this the equilibrium probability, eq: eq = 2^(n-i) / a[i-1] If p < eq, then you walk, and if p > eq, you guess. p is of course generated from the interval [t,1], so if eq < t, then you will always guess. So putting it all together, there are two cases: if eq < t: a[i] = (t + 1)/2 * a[i-1] if t < eq < 1: a[i] = (((eq - t) / (1 - t)) * 2^(n-i)) + (((1 - eq) / (1 - t)) * ((1+eq)/2) * a[i-1]) So to clarify the latter case, the first term corresponds to walking away, and the latter term corresponds to guessing. (eq - t) is the size of the interval [t, eq] in which you walk, and (1 - eq) is the size of the interval [eq, 1] in which you guess. Both are normalized by (1 - t), the size of the full interval. At the end, output a[n].

# #10903 - Rock-Paper-Scissors Tournament

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: mathsimulation Solution Description: Use an array and an arraylist to map the combos: arraylist(0) = "rock" arraylist(1) = "scissors" arraylist(2) = "paper" then you can just say: map[0][1] = 1; (rock vs scissors = 1 point) map[1][0] = 0; map[2][0] = 1; etc. Then, setup a wins array and a plays array. For each game (remember, there are k*n*(n-1)/2 of them, not just k), you can use arraylist.indexOf() to get the appropriate indexes to use with the map array - and add that value in the map array to the wins array (that is, only if the players chose different actions) while incrementing the plays array. At the end, iterate through all the players with i, and if plays[i] != 0 output (wins[i]/plays[i]), otherwise output "-". You'll need to use a BufferedReader to take the input in.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: math Solution Description: Keep two arrays, w[] and l[] where w[i] is the number of wins player i has, and l[i] is the number of losses player i has. At the end, for each player, if w[i] + l[i] = 0, output "-". Otherwise, output w[i] / (w[i] + l[i]). In Java you'll need to use BufferedReader and StringTokenizer as there are many, many lines of input (up to 500,000 per case).

# #10905 - Children's Game

 Solved By: peter Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: sorting Solution Description: Take the input into an array, and sort it with a custom comparator. The comparator should use BigIntegers, and compare the BigInteger casts of (a+b) and (b+a). So: return new BigInteger(a+b).compareTo(new BigInteger(b+a)); Then just sort the array using the comparator, and output the array's contents to a string buffer (backwards) that you can then print.

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: sortingstrings Solution Description: This is just a string sorting problem. Represent all integers all strings. For any two strings, you want to concatenate them in the order that produces the greatest string. So sort all of the strings in the following manner: Given two strings a and b, if a+b > b+a, then a comes before b, otherwise, b comes before a.

# #10908 - Largest Square

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: searching Solution Description: Let a[i][j] be the character in the ith row and jth column. For each center (r,c) given, determine the maximum side length a square could have given the size of the grid. maxSize = min(r+1, c+1, m-r, n-c) maxSize = (maxSize*2) - 1 The first line determines the distance to the closest wall, and the second line converts that into a maximum possible side length. Note that, in a grid, the side length of any square centered at a grid point must be odd. Start with bestSize = 1, and then run a loop like this: for(int s=3;s <= maxSize;s += 2) s is the size that is currently being checked. For each s, check the ring in question around the starting point, and confirm that each character is the same as the character in the center. If they are, then add 2 to bestSize. Otherwise, stop processing the query and move on to the next one. For example: bbbbb aaaaa aaaaa aaaaa bbbbb center = (2,2) In the first loop, we'll check the first ring, so these starred locations: ----- -***- -*-*- -***- ----- Everything matches the center, so we add 2 to bestSize (now 3) and test the enxt ring. Here we fail, so we stop and output 3. Searching each ring can be done in 1, 2 or 4 non-nested for-loops. You just need to search the left and right columns, and the top and bottom rows.

# #10910 - Marks Distribution

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programmingmath Solution Description: This problem boils down to putting (t-p*n) items into n boxes. There's a DP method, but I did the closed form: Let x = (t-p*n). We want to put x items into n boxes. We can represent this with a partition: X | X X X | This is the partition 11, 13, 10. The X's are items, and the pipes are delimiters that separate boxes. As you can see, the last box is empty. So what we are actually doing is arranging a sequence of x X's and (n-1) pipes. This is (x+n-1) C x, or: (x+n-1)! / [x! * (n-1)!] I used BigInteger to store the intermediate calculations, because I'm lazy like that.

# #10918 - Tri Tiling

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: I would suggest reading the solution to this problem at www.algorithmist.com as it's a bit more formal than my method. But in any case, here's what I did: First, if n is odd, there are zero possibilities. You can't tile something of odd area with only even tiles. Also, if n = 0, output 1. You can tile a 3x0 rectangle in one way: don't place any tiles. If you draw out the possibilities by hand for n = 2, 4, and 6, you should begin to see a pattern. You can take all the arrangements of (n-2) and add one of the following: -- -- -- || || -- -- || || So you can make 3*a[n-2]. Also, to every other term (n-4), (n-6), etc. you can tack on one of these: |--| |--| ---- ---- |--| |--| So you must also add 2*a[n-4], and 2*[n-6], etc. So all together, a[n] = 3*a[n-2] + 2*a[n-4] + 2*a[n-6] + ... + 2*a[0].

# #10921 - Find the Telephone

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: strings Solution Description: Iterate through the line. If the character is a 1, 0, or -, just output it. Otherwise, loop through an array(8 long) of strings, with each containing the letters for telephone number(2+i) where i is the index of the letters in the array. if(array(i).contains(charAt(current))) output(i+2)

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: strings Solution Description: Make an array of 256 characters where a['A'] = 2, a['Z'] = 9, and so on (don't forget '0', '1' and '-'). Then just print a[char] for all characters in each given string.

# #10922 - 2 the 9s

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: recursion Solution Description: Literally define a recursive function that takes integers a and b. If a < 10, return b if a % 9 == 0, and return -1 otherwise. If a >= 10, sum its digits and return recursivefunction(sum, b+1) Then, in your normal function, sum the digits of the input right away, and just return recursivefunction(sum, 1).

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: sorting Solution Description: Just keep adding all of the digits together (iteratively; no need for recursion) until the sum of digits is less than 10. If you hit 9, then success, otherwise, failure.

# #10924 - Prime Words

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: mathsorting Solution Description: Use a prime sieve to generate the primes -> you only need them up to about 1100. The rest is self explanatory. NOTE: Just be careful - they consider the number 1 to be a prime number.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: mathstrings Solution Description: Use the Sieve of Eratosthenes to generate all the primes up to 1100 or so. Then just calculate the value for each string and check if it's prime.

# #10926 - How Many Dependencies?

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: other graph Solution Description: Just run a depth-first search from each node to see which one has the most children.

# #10929 - You can say 11

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: mathsorting Solution Description: Just use BigIntegers and see if N % 11 = 0.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: math Solution Description: Just use BigIntegers and take mod 11. There can be leading zeroes on the number, so make sure that you print them out as well.

# #10931 - Parity

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: ad hoc Solution Description: Just convert the number to base 2, and count the number of 1's.

# #10945 - Mother Bear

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: strings Solution Description: Cast each string to upper case, remove all the punctuation and whitespace, and check if the string is a palindrome.

# #10946 - You want what filled?

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: other graphsorting Solution Description: Do a floodfill from every point in the grid that isn't a period, and keep a list of the holes you find and the characters associated with. Sort this list at the end as per the given criteria, and output it.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: greedy Solution Description: Hopefully it's clear (or you're at least convinced by the sample input!) that you always want to add the smallest numbers first. You'll always have to do (n-1) additions, so you may as well involve the smallest numbers as much as possible. This is really easy to implement with a priority queue. Just dump all the numbers in, and then continuously pull the first two out, and push the sum back in.

# #10970 - Big Chocolate

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: ad hoc Solution Description: Every time you break the chocolate, you get one more piece. So when you break it once, you have 2 pieces. When you break again, you get 3 pieces. It doesn't matter how you break it. So, to get M*N pieces, you must break it M*N - 1 times.

# #10986 - Sending email

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: easy Algorithms Used: dijkstra Solution Description: This is a straight-up Dijkstra problem, but with a sparse graph. With 20,000 vertices, an O(V^2 log V) implementation will not run in time. But, there are no more than 50,000 edges! So, you must implement a version for sparse graphs that runs in O(E log V).