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.

#10404 - Bachet's Game

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a DP with a very simple array, but it takes a bit of thought to get the array correct.

Let a[] be an array of booleans where a[i] is true if you would win with i stones remaining on your turn.

Initially, a[i] is true for all values that you are allowed to pick. So, if you can take 1, 3, or 8 stones (as in the first example) a[1] = a[3] = a[8] = true. This means that if it's your turn and you can take all of the stones, then you do.

Then, iterate through a[] for i from 1 to n, skipping over the spots you initialized. At each cell, look at a[i-k] where k is a number of stones you can take. If a[i-k] is false for any of the k, then a[i] is true. This means that if you would lose with i-k stones, then you can take k and your opponent will be forced into a losing state.

At the end, Stan wins if a[n] is true. Otherwise, Ollie wins.


#10405 - Longest Common Subsequence

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:dynamic programming
Solution Description: Great little DP. My solution was only like 8 lines.

If you'd like to know more about the longest common subsequence algorithm, both wesley's entry and Google have the code posted. I'll try to go through the logic of it.

When you create this array, you do the DP by filling it up row by row. To start the DP rolling, you first start off by saying "Well, at row[0] and column[0], no matter where along them I am, I know that the LCS is zero since I'm comparing a string to an empty string in those cases." (Remember, one axis is for the number of characters we're considering from String a, and the other is the number of characters we're considering from String b)

You then take baby steps to the next row.

"Well, what about if I just have the first character of String a, what is the LCS if I only have the first character of String b as well? What if I have the first two characters of String b? What about three?"

At this point the array elements will probably be all zeros still. However, when you do come across an instance where, for example: "Okay, I'm looking at array[3][5], that means that I'm looking at the first three characters of String a, and the first five of String b. I've noticed that the third character of String a matches the third character of String b. Well... since they're the same, the LCS up to this point would be 1 for this match here, added to whatever I had earlier at array[2][4] (When I wasn't considering these two). Okay, well then what do I do for the next element in this row... array[4][5]? It shouldn't be zero like the past ones. It should be the maximum of whatever is to the left of it and whatever is above it. In other words, the higher of -> the LCS when String a was one character short, or the LCS when String b was one character short."

From that, I got the algorithm for LCS.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:dynamic programming
Solution Description: As the problem title says, just run Longest Common Subsequence on the two strings. LCS works as follows:

Let X and Y be the two sequences.

a[i][j] = length of the LCS using the first i characters in X, and the first j characters in Y.

The recurrence:

a[i][0] = 0
a[0][j] = 0

a[i][j] = a[i-1][j-1] + 1 (if Xi = Yj)
a[i][j] = max(a[i-1][j], a[i][j-1]) (if Xi != Yj)


#10407 - Simple division

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Take the first case as an example:

701 1059 1417 2312

If we subtract the smallest number (701) from each, we get:

0 358 716 1611

The GCD of these numbers is 179. Now, if we add 701 back in, then the remainder of all the numbers will be the same when divided by 179. Specifically, it will be 701 % 179.


#10409 - Die Game

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Just run the simulation. Hold six variables, one for each side, and start them off with the indicated starting values.

Then, for each command gotten, you have the 'arduous' task of writing five lines depending on the command, to rotate the die.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep 6 variables that hold the 6 sides of the die. Then just hardcode how the variables shift around for each possible direction. At the end, output the top number.


#10417 - Gift Exchanging

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: We want to calculate the probability of every possible arrangement of gifts. So, given a set of gifts like the second sample case, "1 3 2 1 1", create a string like "01112234" that shows one permutation of the gifts. Call this string a. Let a[0] be the gift that your friend brings. Let c[i] be the number of gifts of each type. So in this case, c[0] = 1, c[1] = 3, etc.

For each permutation of the string, calculate the probability of that arrangement occurring. Let p[i][j] be the probability that person i brings a gift of type j. The probability of an arrangement is p[0][a[0]] * p[1][a[1]] * ... * p[n][a[n]]. Add this probability to g[i]. g[i] is the (unnormalized) probability that your friend brings his gift in a box of type i.

At the end, the normalized probability that your friend brings a gift in a box of type i is:

(g[i] / (g[0]+g[1]+...+g[4])) / c[i]

Output the maximum of i from 0 to 4.


#10420 - List of Conquests

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:sorting
Solution Description: Use a HashMap to store the counts for each country, and an arraylist to keep a list of the countries you've seen.

After input, sort the arraylist, and iterate through it - outputting your value in the hashmap for each.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:searching
sorting
Solution Description: With n = 2000, O(n^2) is no problem. Keep a list of tuples that each have a country name and the number of times that country has come up so far. For each input line, increment the corresponding tuple, or make a new one if none exists. Sort the tuples by increasing country name, and output.


#10424 - Love Calculator

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
strings
Solution Description: Just do exactly as the problem states. You might need to use longs to hold the sums, and make sure you're acccounting for when the sum of digits is still > 9.

Use System.out.printf to format your output.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Cast both strings to lower case, and iterate through looking for lower case letters. For each one, add letter-'a'+1 to a running total. Keep adding up the digits until both of your totals are only one digit. Then, just divide the smaller by the larger and output the result. Make sure you put the space between the number and the percent sign.


#10432 - Polygon Inside A Circle

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:2D geometry
math
Solution Description: Take the inputs r and s as doubles.

Output using System.out.printf:

s*(r*r*Math.sin((Math.PI * 2.0)/s))/2.0


Got AC in Java.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
math
Solution Description: If you draw a line from the center of the circle to all the vertices of the polygon, you'll see that the polygon breaks down into triangles. The area of one of these triangles can be easily calculated via a variety of methods (I used Heron's Formula and the Cosine Law). Multiply the triangle's area by the number of sides, and you'll have your answer.

Note that the radius can be given as a real number, not just an integer.

Unfortunately, the judge has precision issues for this problem. I've tried a few different solutions and none of them are accepted in Java. So understand the idea behind the problem, and then use Peter's solution as it might be the only form that works.


#10450 - World Cup Noise

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: We want all of the n-bit sequences without 2 adjacent 1's. We can add 0 to any sequence of length n-1, and we can add 1 to any sequence of length n-1 that doesn't end in a 1. It turns out there are a[n-2] of these.

So the recurrence is just a[i] = a[i-1] + a[i-2], or of course, the Fibonacci numbers.

Note that you need to use longs to store a few of the higher values.


#10465 - Homer Simpson

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is an unbounded knapsack problem with a twist. We're actually maximizing weight rather than value. The value of each burger is 1, and the weight is the time it takes to eat it.

Let w[i] and v[i] be the maximum weight and value possible with i minutes, respectively.

w[0] = v[0] = 0

for i from 1 to t
- pick the burger type that will maxmimize weight
- break ties by maxmimum value
- update w[i] and v[i] accordingly

At the end, print v[t], and print t - w[t] if w[t] < t.


#10469 - To Carry or not to Carry

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: I wish we had a facility to mark certain problems as SUPER easy, 'cause this is one of them.

Take two longs in (a and b), and output a^b (Java).

a ^ b is the Java equivalent of a XOR b.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: As the problem hints at, just take the bitwise exclusive or (XOR) of the two numbers. Make sure you're using unsigned ints or longs.


#10473 - Simple Base Conversion

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Not much to this one. Just do the conversions. Remember that the input might end on *any* negative number, not just -1.


#10474 - Where is the Marble?

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:searching
sorting
Solution Description: Sort the input, and then run a binary search to find the right marble. Once you've found it though, work backwards through the array to find the *first* occurence of that marble.


#10479 - Then Hendrie Sequence

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:math
Solution Description: The sequence, strategically broken up into blocks, looks like this:

0 | 1 | 0 2 | 1 00 3 | 02 11 000 4 | 1003 0202 111 0000 5 |

We note that the ith block has length 2^(i-2) (excepting the first block which has length 1). Also, the ith block consists of (i-2) pieces from prior blocks, and then the number i-1.

For example, the 6th block has:

1 0 0 3 (1 copy of block 4)
02 02 (2 copies of block 3)
111 (3 copies of block 2)
0000 (4 copies of block 1)
5 (the number (6-1))

As every block is defined in terms of the block before it, we can write a recursive function that simplifies the problem down until it reaches a known value (say, the first 10 values of the sequence or so).

If the number given, n, is a perfect power of 2, we just return log2(n). Otherwise, we use k = floor(log2(n)) to determine which block n belongs to.

n - 2^k is how far along the block n is. We add up the lengths of the subblocks, i*2^(k-i-1) for i from 1 to k until the cumulative sum is greater than or equal to (n - 2^k). The index i at which we stop is the number of the subblock that n belongs to.

We can now simplify n down to 2^(k-i-1) + (n - 2^k - 1)%(2^(k-i-1)) + 1, and recurse on this new value. Note that (k-i-1) can be < 0, in which case the first 2^(k-i-1) should be set to 0, and the latter should be set to 1.

Be wary of double precision as it isn't quite good enough for this problem. I would suggest doing everything in longs to avoid rounding errors. For instance, log(2^63 - 1) / log(2) gives 63, when then actual value is slightly less than 63.

(Thanks to A. Henrey for explaining the structure of the sequence and outlining the solution presented here)


#10487 - Closest Sums

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
searching
Solution Description: Take in the input, and then calculate the sum of every pair of inputs. Sort these sums, and for each query, binary search to find the closest sum.


#10489 - Boxes of Chocolates

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: For each box, the number of chocolates inside is a1 * a2 * a3 * ... * ak. Of course, this number could be quite large. Luckily, we have modular arithmetic:

(a1 * a2 * ... * ak) % m = (((a1 % m) * a2) % m) * a3) ... ) % m

So, take % N after each multiplication to keep the total product small. This will give you the residual number of chocolates in each outer box. To get the overall residue, add all of these small residues together, and take % N once more.


#10491 - Cows and Cars

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: There are two ways of getting a car. Either you pick a cow first and then switch to a car, or you pick a car first, and then switch to another car.

In the first case, the chance of picking a cow first is (NCOWS / (NCOWS+NCARS)). Then, the chance of switching to a car is (NCARS / (NCARS+NCOWS-NSHOW-1)). Multiply these together to get the probability of the first case. The -1 is to account for the door that you've already picked, as you can't switch to it.

The second case is quite similar. The chance of picking a car first is (NCARS / (NCARS+NCOWS)). Then, the chance of switching to a car is ((NCARS-1) / (NCARS+NCOWS-NSHOW-1)). The first -1 accounts for the car that you've already chosen, just like the second one.

Sum these two cases together, and you have your answer.


#10499 - The Land of Justice

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
3D geometry
math
Solution Description: The sphere starts with 4*pi*r^2 surface area. We can ignore r (assume it's 1), so we have 4*pi SA. When you cut a wedge out of a sphere, that wedge has two new faces, each one of which is a semicircle. Therefore, the wedge has a whole circle of new SA, or another pi of SA.

So, if we cut the sphere into N wedges, we have 4*pi + N*pi as the total SA. N*pi / 4*pi is then the profit. This reduces to N/4 as the profit. But we want a percentage, so multiply by 100 and get (25*N)% as the final answer.

Don't forget the special case where N = 1, and make sure you use longs. N might be in the int range, but 25*N is not.





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