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 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^(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: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*(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: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 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 programming
math
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: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 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: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 - 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 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 All

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).





Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site