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. #10602  Editor NottoobadSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc greedy strings
 Solution Description:  This problem can be solved greedily. Start with the first word. Then, while there are words remaining, find the word the matches the greatest amount of characters from the beginning, and use that one next. So for example, the second input case:
popcorn (7 characters used)
Now, "plum" shares 1 character with the beginning of "popcorn", and the other two words share 0. So, we choose "plum":
plum (10 characters used)
Now, it doesn't matter which word is next.
apple (15 characters used)
And finally,
apricote (21 characters used)

#10603  FillSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  dijkstra other graph
 Solution Description:  You can represent this problem as a graph with 200x200x200 nodes. Each node has three values, a, b, c, representing the amount of water in each of the three jugs. The edge weight between two nodes is how much water must be poured.
You can use Dijkstra, or you can use BFS where you redo a node if you come back to it with a better value (This only works because the bounds are small).
See Also:
Problem 571 (Jugs) 
#10608  FriendsSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  Setup the friends as nodes, and join two if they are friends.
Start at an arbitrary friend (f), and BreadthFirstSearch from there, counting the nodes who are connected to f, and marking each as being visited.
max = Math.max(max, number of connected nodes)
Repeat if a node has not yet been visited.
NOTE: you cannot use an adjacency matrix, since it could be as big as [30000][30000]  and even booleans will throw a runtime error. I used an array of arraylists, but found this out the hard... long way 'sigh; 
Solved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  This is one of the simpler union find problems. Just use union find to form all the groups of friends. Afterwards, search through the groups to find the largest one. This can be done easily with an array where a[i] is the number of nodes that have i as a set leader. Just iterate through all nodes i, incrementing a[leader(i)], then print the largest value. 
#10610  Gopher and HawksSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry other graph
 Solution Description:  This is just a BFS problem with a bit of math. Run BFS on the gopher holes, and consider two holes connected if the distance between them is less than or equal to m*v*60. 
#10611  The Playboy ChimpSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  searching
 Solution Description:  Just binary search the list to see where the chimp would fit, and search linearly from that point to find the two answers. Obviously, handle the cases of when the input is < a[0] or > a[n1]. 
#10618  Tango Tango InsurrectionSolved By:  wesley  Theory Difficulty:  hard  Coding Difficulty:  medium  Algorithms Used:  dynamic programming
 Solution Description:  Our DP will be a series of arrays of size [4][4][3][70].
f(l, r, m, k) is the amount of energy it takes to complete the rest of dance given that you've completed k steps so far, your left foot is on square l, your right foot is on square r, and m is a value (0, 1, or 2) that represents which foot (if any) moved in the last step.
The convention I use for l and r is 0 = Up, 1 = Left, 2 = Right, 3 = Down.
For m I use 0 = no foot moved, 1 = Left, 2 = Right.
So, we want to determine f(1, 2, 0, 0), and return the appropriate sequence of actions. At each step, there are two cases:
Case 1: The next step is '.'
In this case, try moving your left foot to all four squares, and then try moving your right foot to all four squares. Nothing is going to be tapped, but you can use this pause in the music to reposition yourself. If you move a foot, make sure to output the foot that moved, even though it didn't tap.
Case 2: The next step is 'U', 'L', 'R' or 'D':
In this case, try moving your left foot to the appropriate square, and try moving your right foot to that square as well.
In both cases, make sure not to allow any illegal moves.
I recommend having three parallel arrays. Each is indexed as mentioned above, by (l, r, m, k). The first array, COST, is the standard DP array that keeps track of how much energy it takes to complete the dance from the given state. The second array, NEXT, keeps track of some integer or object that points to the next state in the path, and the third array, MOVE, keeps track of what move was taken.
For example, consider the input "LUR". We go through the following transitions to get the output "LRL":
l r m k
1 2 0 0 (move is "L")
1 2 1 1 (move is "R")
1 0 2 2 (move is "L")
2 0 1 3 (sequence is finished)
And the arrays look like this:
NEXT[1][2][0][0] = (1, 2, 1, 1)
MOVE[1][2][0][0] = 'L'
COST[1][2][0][0] = 3
NEXT[1][2][1][1] = (1, 0, 2, 2)
MOVE[1][2][1][1] = 'R'
COST[1][2][1][1] = 2
NEXT[1][0][2][2] = (2, 0, 1, 3)
MOVE[1][0][2][2] = 'L'
COST[1][0][2][2] = 1
At the end of the DP, use the information in NEXT to traverse through the optimal states, and use the information in MOVE to print out the move sequence.

#10622  Perfect Pth PowersSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Given that the square root of 2^31 is less than 47,000, there must not be more than 47,000 (positive) inputs that return "2" as their answer. In the same way, the cubic root of 2^31 is less than 1300, there are no more than 1300 (positive) inputs that return "3".
Given that the vast majority of inputs will return "1", you can just pregenerate all of the answers that won't return "1", store them in a hash map, and output them when necessary.
Don't forget: input numbers can be negative too. 
#10633  Rare Easy ProblemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  First, note that M is (N div 10) ("div" being integer division).
NM is then approximately 9N/10. Given that (N div 10) <= (N / 10), we know that (NM) <= 9N/10. Also, the difference between (N div 10) and (N / 10) is at most 10.
Let X = NM. We can a range of numbers [10X/9 + 20, 10X/9  20] and test each one to see if it is a possible solution.
A range this wide is just for safety. You definitely don't need to have a range that wide, and you can actually prove that if there are multiple solutions, there are at most two solutions and the difference between them is 1.
Unsigned 64bit integers make this problem easier, but you can manage with signed 64bit integers if you do (X + X/9) rather than (10*X) / 9. 
#10642  Can You Solve It?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc math
 Solution Description:  Consider the lines with equation x+y = C to be different "levels". So, coordinates with the same C are on the same level. Note that you first go through level 0 [(0,0)], then level 1, [(0,1) (1,0)], etc.
Let the input coordinates be x1, y1, x2, y2. Let l1 = x1+y1 be the level of the source, and let l2 = x2+y2 be the level of the finish. There are two cases:
Case 1: Source and finish on same level
In this case, just output y1  y2.
Case 2: Source and finish on different levels
In this case, output y1 + x2 + (l2l1) + cumsum(l1+1, l21), where cumsum(x,y) returns the sum of all numbers between x and y inclusive, or 0 if x > y.
For more intuition behind this formula, read on:
 y1 is the number of steps it takes to get to the end of level l1
 x2 is the number of steps taken past the beginning of level l2
 (l2l1) is the number of transitions between levels that we have to do
 cumsum(l1+1, l21) is the number of nodes on all levels between l1+1 and l21 inclusive
Note that you must use longs to hold some of the higher values. 
#10651  Pebble SolitaireSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming recursion
 Solution Description:  It's fairly easy to do this as a topdown DP. Keep an array of length 2^12 where a[i] is the minimum number of pebbles left over starting from state i. i is a binary representation of the current state of the game. So for instance,
ooo = 110100 (base 2) = 52 (base 10)
and a[52] would be 1, because you can reduce this state to 1 pebble by moving right twice.
The recurrence is pretty simple. Just try all possible moves and recurse on them. If there are no possible moves, then count the number of pebbles remaining and return that as your answer. 
#10673  Play with Floor and CeilSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  It actually *is* pretty easy to prove this theorem.
If you take p = floor(x/k), you'll be missing an extra x % k. So add 1 to x % k numbers to get:
q = x % k
p = k  q. 
#10678  The Grazing CowSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry math
 Solution Description:  An ellipse is the set of points, {P}, such that the distance from P to a fixed point F1, plus the distance from P to a fixed point F2 is a constant for all points in the set. The rope and the two posts define such a set, so the area the cow can move in is an ellipse.
The area of an ellipse is a*b*pi where a and b are half the distance of the minor and major axes respectively. It shouldn't be too hard to see that:
a = sqrt((L/2)^2  (D/2)^2)
b = L / 2 
#10680  LCMSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  Let P(n) be the multiset of prime factors of n. So, P(60) = {2, 2, 3, 5}.
The LCM of a set of numbers {a1, a2, a3, ..., an} is the product of the intersection of P(a1), P(a2), ..., P(an). Intuitively, this means that you need "enough" of each prime factor in the LCM to "satisfy" each of the numbers.
Let a[i] be the LCM of the numbers from 1 to i. To determine a[i+1], factorize i+1, then see if you need any of its factors.
Keep an array c[] where c[j] is the number of times you've used j as a factor in your LCM so far. When you factorize i+1, check if the count of each factor, j, is greater than c[j]. If it is, multiply your current LCM by j until the count is satisfied.
Now, the LCM grows very quickly, so we don't want to actually store the entire LCM in a[]. Instead, we store the last 7 or so digits before the final string of zeros. So, if our LCM was 182158203800000000, we would store "1582038" in a[]. This can be accomplished by the following code:
while(a[i] % 10 == 0)
 a[i] /= 10
a[i] %= 10000000
We keep 7 digits because the largest number we might multiply a[i] by is 6 digits long. 
#10684  The jackpotSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a straightforward Maximum Interval Sum DP. You can solve it in O(n) as follows:
Let a[i] be the ith bet. Then,
dp[0] = a[0]
dp[i] = max(dp[i1] + a[i], a[i])
So, either choose to continue the sequence, or start a new one if the previous one wasn't profitable.
Output the maximum value in dp[], if it's greater than 0. 
#10696  f91Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:   Solution Description:  if(n > 100)
output n10
else
output 91
Use stringbuffers to avoid TLE. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Simulating the function is too slow (for Java at least), but if you test it out on a few small numbers, you'll notice a pattern:
f91() returns 91 for all numbers <= 100, so just output 91, or n10 as necessary.
In Java you'll need BufferedReader AND StringBuffer. 
#10699  Count the factorsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Use the Sieve of Eratosthenes to generate all the primes up to 1,000,000. For each input, check whether each prime divides it.
You don't need to do an O(sqrt(n)) check. O(n) will do fine. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
