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 2naire?Solved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 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^(ni), or you take a guess. If you guess, your expected win is p*a[i1]. 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^(ni) / a[i1]
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[i1]
if t < eq < 1:
a[i] = (((eq  t) / (1  t)) * 2^(ni))
+ (((1  eq) / (1  t)) * ((1+eq)/2) * a[i1])
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  RockPaperScissors TournamentSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math simulation
 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*(n1)/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 GameSolved 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:  sorting strings
 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 SquareSolved 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, mr, nc)
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 nonnested forloops. You just need to search the left and right columns, and the top and bottom rows. 
#10910  Marks DistributionSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  This problem boils down to putting (tp*n) items into n boxes. There's a DP method, but I did the closed form:
Let x = (tp*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 (n1) pipes.
This is (x+n1) C x, or:
(x+n1)! / [x! * (n1)!]
I used BigInteger to store the intermediate calculations, because I'm lazy like that. 
#10918  Tri TilingSolved 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 (n2) and add one of the following:









So you can make 3*a[n2]. Also, to every other term (n4), (n6), etc. you can tack on one of these:






So you must also add 2*a[n4], and 2*[n6], etc.
So all together, a[n] = 3*a[n2] + 2*a[n4] + 2*a[n6] + ... + 2*a[0]. 
#10921  Find the TelephoneSolved 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 9sSolved 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 WordsSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math sorting
 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:  math strings
 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 depthfirst search from each node to see which one has the most children. 
#10929  You can say 11Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math sorting
 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  ParitySolved 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 BearSolved 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 graph sorting
 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. 
#10954  Add AllSolved 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 (n1) 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 ChocolateSolved 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 emailSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  dijkstra
 Solution Description:  This is a straightup 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). 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
