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. #10000  Longest PathsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dijkstra floyd warshall other graph
 Solution Description:  Given the small bounds (N = 100), you can just use FloydWarshall with edge weights of 1 to solve this. Obviously there are many other faster algorithms, such as Dijkstra or DP on a DAG, but FloydWarshall is the fastest to code by far. 
#10002  Center of MassesSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  math polygon sorting
 Solution Description:  The formula for center of mass (centroid) is fairly simple:
((1/6)*A) * [sum across all points i from 1 to N] (x_i + x_i+1)*(P_i CP P_i+1)
...where A is the area of the polygon, and CP stands for the cross product of two points.
The first thing you must do though is sort the points. Let P0 be the leftmost bottommost point. That is, the point with the lowest ycoordinate, with ties broken by lowest xcoordinate. Sort the remaining points by increasing angle from the xaxis. So for example, in the third sample case the points should be in this order:
(7, 12)
(4, 10)
(3, 6)
(4, 4)
(6, 3)
(8, 3)
(9, 8)
Now the points are sorted in clockwise order, and the above formula will work.
A word of warning though: there are colinear points in the input. The formula works fine for colinear points, but only if they're sorted clockwise properly, which may not be the case for points that are colinear with P0. The safest thing to do is to remove them before applying the formula, but there's a quick way to neutralize them instead.
When sorting, if two points are found to have the same angle with P0 and the xaxis, put the point that is farther from P0 before the one that is closer. Then, after sorting, run through the set of points from P0 to PN1. If two adjacent points in the array are colinear with P0, make the later point the same as the former point. So for example, if you have the input:
(0,0)
(3,3)
(1,1)
(4,4)
(2,2)
(0,2)
First sort them so that you get:
(0,0)
(4,4)
(3,3)
(2,2)
(1,1)
(0,2)
And then overwrite every pair of adjacent colinear points with the leftmost one to get:
(0,0)
(4,4)
(4,4)
(4,4)
(4,4)
(0,2)
Now everything will work properly. You could use a convex hull algorithm to remove the colinear points, but I think this is a bit simpler.
I wasn't able to get this problem to run in time in Java because of the size of the input. With scanf/printf in C though, it works just fine.
See Also:
Problem 109 (SCUD Busters) 
#10003  Cutting SticksSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a DP problem with a fairly intuitive recurrence. To cut a stick, we must pay for the length of the stick, plus the cost of cutting up its substicks. This leads us to the following:
Keep an array of integers, a[], that holds points whee the stick will be cut. Include 0 and l as points as well. For example, in the test case...
10
4
4 5 7 8
...the array will have elements 0,4,5,7,8,10.
Let i be the point where the stick starts.
Let j be the length of stick (in cuts). This means that dp[1][2] holds the cost of the stick that starts at point 1, and is 2 cuts long. For the above test case, that means the stick (4,7).
dp[i][1] = 0
(A stick that's only one cut long doesn't need to be cut any more, and therefore doesn't cost anything).
dp[i][j] = minimum across all k in range[1,j1](dp[i][k] + dp[i+k][jk]) + (a[i+j]  a[i])
To clarify the recursive step a bit... Iterate through all cuts between point i and point i+j, and find the one for which dp[i][k] + dp[i+k][jk] is the minimum. To this minimum, add (a[i+j]a[i]) which is the length (and therefore cost) of the stick. 
#10004  BicoloringSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  BFS (breadth first search)
Start from an arbitrary node (I said node 0), by adding it to a queue.
while(queue not empty)
take off front
colour children
if one child was already coloured
fail
if child not colored
color him
add him to the queue 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  Bicoloring can be done quickly with a depthfirst search or a breadthfirst search. Make the first node color 1, and put it in your stack (or queue). Whenever you take an element out of the stack, color everything that it's attached to the opposite color. If at any point you're trying to overwrite one color with the opposite color, the graph cannot be bicolored. Otherwise, it can. 
#10006  Carmichael NumbersSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Hard code a data table. Generating the numbers runs at O(n!), which is disgusting.
If you're impatient, you can even just look up the first <65000 Carmichael numbers, instead of generating them. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  The simplest thing to do for this problem is to brute force the Carmicahel numbers, and then hardcode them. There are only 15 in the given range.
Use the Sieve of Eratosthenes to generate the primes up to 65000. Then, any nonprime n that satisfies a^n mod n = a for all a < n is a Carmichael number.
To calculate a^n mod n without BigInteger:
res = a;
for(1 to n1)
{
res *= a;
res %= n;
}
It may take 2 minutes or so to determine the 15 Carmichael numbers. 
#10007  Count the TreesSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  It's easier to consider unlabelled trees first, and label them afterwards.
To make an unlabelled binary tree, you choose one node to be the root, and then choose how many nodes to put in each of the left and right subtrees, and then recurse. This gives us the following recurrence:
a[0] = 1
a[1] = 1
a[n] = a[0]*a[n1] + a[1]*a[n2] + ... + a[n1]*a[0]
To label the tree, we assign a permutation of the numbers 1 to n to it. So, to get the number of labelled binary trees with n nodes, output a[n] * n!
BigInteger is recommended.
See Also:
 Problem 991 (Safe Salutations) 
#10008  What's Cryptanalysis?Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  brute force strings
 Solution Description:  loop through each character, and add one to that character's count in an array 26 long.
if you're tricky, and have an array of letter objects, you can then sort it and output. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Keep an array of 26 objects that each hold a character (from A to Z) and a number. Translate the entire string to uppercase, and then iterate through it. Whenever you encounter a character between A and Z, add 1 to that character's number in the array.
At the end, sort the array (by number descending, then character ascending) and print out all values greater than 0. 
#10009  All Roads Lead Where?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall other graph
 Solution Description:  You can ignore everything they say about the whole cities and levels system, and just treat this as any other BFS problem. Given the guarantee that no two cities start with the same letter, you can throw away all of the city name except for the first letter.
With the small bounds (26 cities), you can even use FloydWarshall.
Don't forget to print a blank line between cases. Given that the sample input has only one case, it's easy to miss during testing. 
#10010  Where's Waldorf?Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force searching strings
 Solution Description:  This is fairly simple to do, but takes a bit to code, and it's easy to make mistakes.
Use an array, a[][], to hold the letters in the puzzle. For each word, iterate through all cells and search in all 8 directions. You don't need to optimize this at all; the test input isn't that large.
There are three things to watch out for:
1) Case doesn't matter. Change all input into one case or the other as soon as you get it.
2) Don't exceed the bounds of your array.
3) Check that you can find words in all 8 directions. For instance, I use a case like this:
5 5
abcde
fghij
klmno
prstu
vwxyz
8
mhc
mie
mno
mtz
msx
mrv
mlk
mga 
#10012  How Big Is It?Solved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  2D geometry brute force dynamic programming
 Solution Description:  With only 8 circles, there are only 8! possible combinations. This can be brute forced without issue.
It isn't enough to just calculate the distance between two circles because you'll end up with a case like (2.0, 0.1, 2.0) where the middle circle doesn't affect the size of the box as it fits between the two other circles. So instead, for each arrangement of circles, keep track of the xcoordinate of the center points of each one and do a sort of miniDP:
Let c[i] be the center point of the ith circle. Let r[i] be the radius of the ith circle. Let dist(i,j) be the horizontal distance between the centers of the ith and jth circles.
c[0] = r[0]
c[i] = max(r[i], max[across all j < i](c[j] + dist(i,j))
At the end, the size of the box needed for this arrangement is:
max[across all circles i](c[i] + r[i])
So run this DP for all arrangements of circles, and return the minimum value you find. 
#10013  Super long sumsSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Use a stringbuffer for output, a BufferedReader for input, and a StringTokenizer to seperate the two numbers on each line.
Make two character arrays, m long, and fill them with the input. Create a carry boolean and iterate from the end to the beginning of the arrays, adding pairs of digits and keeping track of when to add the carry  and outputting the determined digit at each iteration to your string buffer. At the end, reverse your string buffer and output.
Runs in time with Java. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Read Peter's solution. It's pretty hard to get this run in time in Java unless you do exactly what he says. Make sure you use char arrays, and not ints. Integer.parseInt is likely the issue. 
#10014  Simple CalculationsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  This problem can be solved by repeated substitution.
We are given:
An = (An1 + An+1) / 2  Cn
Or rearranging:
2An = An1 + An+1  2Cn
We can use this to solve for An1:
3An1 = 2An2 + An+1  2Cn  4Cn1
And so on:
4An2 = 3An3 + An+1  2Cn  4Cn1  6Cn2
So at the end we get:
(n+1)A1 = nA0 + An+1  2Cn  4Cn1  6Cn2  ...  (2n)C1 
#10015  Joseph's CousinSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math simulation
 Solution Description:  Use the Sieve of Eratosthenes to generate the primes up to 50,000 or so. The 3500th prime is less than 40,000 I believe. Store your primes in an array, p[].
Just simulate the process. A dynamic array makes things very simple. Keep an index variable, initally at 1. Then at the ith iteration:
index = (index + (p[i] % a.size)) % a.size
Remove the element at this index, and then repeat. Make sure to decrement 1 from the index to compensate for the missing element. At the end, just print out the last remaining element. 
#10017  The Never Ending Towers of HanoiSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  recursion simulation
 Solution Description:  If you've taken any introductory computer course, you've probably seen the recursive solution to the Towers of Hanoi. If not, it isn't too hard to come up with, but here it is:
To move N pegs from a source peg to a goal peg with the third peg as a spare, you first move the top N1 disks to the spare, then move the biggest peg to the goal, and then move the N1 disks to the goal. So the recursive solution looks like this:
hanoi(1, source, goal, spare):
 Move the one disk from the source to the goal
hanoi(N,source, goal, spare):
 hanoi(N1, source, spare, goal)
 hanoi(1, source, goal, spare)
 hanoi(N1, spare, goal, source)
Use three stacks to simulate the pegs. When you reach the base case, print out the current state of the stacks. You should put a second base case that stops the whole process when you've hit the number of moves required. 
#10018  Reverse and AddSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math strings
 Solution Description:  Use String Buffers and longs
StringBuffer class has a reverse function, and you can just use a while loop that checks
while(!inputBuf.toString().equal(inputBuf.reverse().toString()))

Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  The easiest way to reverse the number is to cast it to a string, reverse the string, and cast it back. Just keep adding the reverse as per the problem.
If the string is already a palindrome, then output 0 additions.
Make sure you're using unsigned ints or longs. 
#10019  Funny Encryption MethodSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Straight forward follow the algo given.
for b1, just do bitwise comparisons, looping from 0 to 31 (i), and checking 1<< i & n (where n is the given number)
for b2, treat the number as hex, and convert to decimal by multiplying from the right by 16^i (where i is the index from the right starting at 0). Then, follow above once more and output. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  A decimal number can be converted into a binary string very easily:
while(num > 0)
{
str = (num%2) + str;
num /= 2;
}
For the hexadecimal number, just convert it into decimal, then covert the decimal number into a binary string. 
#10023  Square rootSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Here's a link to a BigInteger square root implementation: http://sfuacm.wikia.com/wiki/Big_Integer_Square_Root
You probably don't want to have to come up with this during a contest... Just keep it in your codebook :D
But, it's good to know how the NewtonRaphson method works. It's a *very* fast algorithm for finding roots. 
#10025  The ? 1 ? 2 ? ... ? n = k problemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Let T[n] be the nth triangular number. Let i be the smallest number such that T[i] >= k. Obviously i is a lower bound for n.
Now, if T[i]  k is even, then we can negate some of the numbers from 1...i to make the formula work. If T[i]  k isn't even, then we can try T[i+1], and T[i+2]. The triangular number sequence goes {even, odd, odd, even, even, odd, odd, etc.} so we never need to check more than 2 triangular numbers above i.
Note that if k is negative, you can just negate the entire expression, so there is no difference in n.
Note the special case k = 0. n must be >= 1, so you cannot say n = 0 if k = 0. 
#10026  Shoemaker's ProblemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  greedy sorting
 Solution Description:  Sort the inputs by cost/time ratio decreasing, then by index increasing, and output the indexes.
Basically, we want to get rid of the jobs with the highest fines, but not if they'll take us a long time. So eliminate the ones with the highest cost/time ratio first. 
#10033  InterpreterSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Keep an array of strings that represents the RAM. You can use integers as well, but leading zeros need to be handled then. Make sure that if you use strings, you initialize the entire array to "000".
After that, just simulate the process. Keep a variable that points to the next address to be executed. Make sure that you don't increment the variable after a goto. Also, make sure that you take mod 1000 after all arithmetic operations. 
#10034  FrecklesSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  This is just a Minimum Spanning Tree problem. Use Kruskal's algorithm to find the optimal solution. Using unionfind to implement Kruskal is probably the easiest way. 
#10035  Primary ArithmeticSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Take in the two strings, and add zeros to the front of the smaller one (if there is one).
Then just keep a counter and a boolean for carrys, and iterate from the right to the left  using the carrys and adding to the counter as necessary.
Be careful of the output  you have special cases where the count = 0 or 1. Also, be sure that you don't try to take a shortcut and only iterate the length of the smaller string  you MUST add zeros to the front and iterate through the entirety of BOTH. Try this case if you doubt me:
9999 1 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Create three arrays of integers, a[], b[], c[]. Fill arrays a and b with the digits of the input numbers. All unused cells should be 0.
For example, 12345 + 56:
a[] = 0000012345
b[] = 0000000056
c[] = 0000000000
c is the carry array, so iterate from right the left filling in the carry array. c[i] is a 1 if a[i+1] + b[i+1] + c[i+1] >= 10. So afterwards:
a[] = 0000012345
b[] = 0000000056
c[] = 0000000110
Output the number of cells in c that have a 1 in them. Note that 0 isn't pluralized as it normally would be. 
#10036  DivisibilitySolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  We want to know if the sequence is divisible by K, so we want to know if we can find an arrangement of +/ such that the final value % K = 0.
We can use DP to keep track of what values (mod K) we can end up with after a certain subsequence.
Let a[i] be a list of possible values (mod k) after putting +/ between the first i values in the sequence. Let Xi be the ith value in the sequence.
a[0] = {Xi%k}
a[i] = {all numbers V such that there exists a value, A, in a[i1] such that V = (A + Xi%K)%K or V = (A + (K  Xi%K))%K}
If and only if a[n] contains 0, then the sequence is divisible by K. 
#10038  Jolly JumpersSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force
 Solution Description:  keep a boolean array for differences seen. keep a 'last' variable to hold the last variable you saw.
iterate through the line, and if ever you encounter a (currentlast) again, output Not jolly. If that never happens, output Jolly.
Make sure you handle:
1 1 5 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Hold all of the input in an array where a[i] is the ith number. Also create an array of booleans where b[i] is true if a difference of i has appeared somewhere in the sequence.
For each i from 0 to n2, check if b[a[i]  a[i+1]] is true. If it is, then output "Not jolly". Otherwise, set it to true. If you iterate through the entire sequence and find no repeated differences, output "Jolly". 
#10041  Vito's FamilySolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  A simple DP which takes a little thinking.
In the DP, you will iterate from 2 to 29999 (technically 1 to 29999).
Starting state:
min = inf
r = # of relatives
below = 0 (number of relatives in houses with #'s below the current which is 1)
above = r  street[1] (number of relatives in houses with #'s above the current)
here = street[1] (number of relatives here)
sum = the sum off the distances of all relatives to 1
Each iteration (with variable j), as you go up one house #, the number of relatives below increases by street[j1].
Also, the variable 'here' becomes street[j] and
above decreases by street[j] (since the people in the current house belonged to 'above', but now belong to the 'here' house)
Lastly, sum = sum + below  (here + above)
since, effectively, you've moving everybody below you away, and everybody above you closer.
Keep the minimum value of sum, and output it. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Sort the relatives' house numbers and find the median. Vito will go in the median house (round if necessary, either up or down). Calculate the distance between Vito's house and all the rest and output it. 
#10042  Smith NumbersSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math searching
 Solution Description:  This is fairly straightforward. Generate the prime numbers up to 10^5 or so using the Sieve of Eratosthenes. For each input, search every number higher than it until you find a Smith number. 
#10044  Erdos NumbersSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  other graph strings
 Solution Description:  This problem isn't theoretically challenging, but there are a few issues to work through.
The idea is to make a graph in which you connect authors that have worked together on the same paper. The paper's name itself is meaningless; you can just discard it.
Once you have this graph, run BFS starting from Erdos, P. to determine the distance to all nodes. Then, for each name you're asked for, print the distance, or infinity if the author wasn't reachable in the graph, or if he never existed in the paper database.
I used a dynamic array rather than an adjacency matrix, though I imagine both would work. In Java the matrix might be too slow, but I'm not sure. Consequently, I used O(V + E) BFS rather than O(V^2). It took 1.6 seconds, so O(V^2) may be too slow.
I also used a hash table to assign numbers to names. That way, you can find out which node in your graph corresponds to each name without having to search a list of names.
Here are some notes:
1) You may be asked for the numbers of authors who were never mentioned in the database. Print "infinity" for them.
2) There may be lines that look like this:
Arthur, B., Apricot: Some crappy book
...where the last author has no initial. In this case, just throw away the last author.
3) 5000 seems to be an upper limit on the number of authors in a given scenario. 
#10048  AudiophobiaSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall
 Solution Description:  This is minimax FloydWarshall. You may need to use BufferedReader in Java. I haven't tried with Scanner, so I'm not sure.
See Problem 534 (Frogger) for more information.
See also:
Problem 534 (Frogger)
Problem 544 (Heavy Cargo) 
#10049  Selfdescribing SequenceSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc math
 Solution Description:  With bounds like 2,000,000,000, you won't be able to have a solution that runs O(n) for each input. But, you can't store the entire sequence naively with O(n) space either.
Luckily, the sequence is nondecreasing, so it suffices to store the different ranges instead. The sequence starts with:
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 ...
So you can store the tuples:
<1,1> (1)
<2,3> (2)
<4,5> (3)
<6,8> (4)
<9,11> (5)
<12,15> (6)
...
Pregenerate all of these tuples. There are around 600,000 of them, so it suffices to search through them linearly for each input. 
#10050  HartalsSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math simulation
 Solution Description:  Keep a count variable, and an array of all the politician hartals.
Iterate from 1 to N inclusive (in variable i), and if any hartal % i == 0 && i % 7 != 6 && i % 7 != 0 then count++
the last two are to omit fridays and saturdays 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  simulation
 Solution Description:  Keep an array where a[i] is the number of parties that go on strike on day i.
For each party's h, iterate through a[] and add 1 to every a[i] where i is a multiple of h.
At the end, iterate through all a[i] and increment a running count whenever a[i] > 0 and i % 7 is not 0 or 6 (Friday or Saturday). 
#10051  Tower of CubesSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dynamic programming other graph
 Solution Description:  There are a few ways to approach this problem. Two slightly naive, but simple ways are LIS and topographical sort. However, this problem can be solved in O(n), much faster than either of these methods, with a fairly straightforward DP.
Keep an array, a[], initially 0, where a[i] is the height of the tallest tower so far with color i on top. Process each block one at a time. For each block, try to improve each tower as per this example:
Say that a[1] = 6, and a[2] = 3, and the next block has color 1 on the top, and color 3 on the bottom. If we put the top face down on the stack that has 6 blocks, then we get a new stack with 7 blocks, and color 2 on top, so set a[2] to 7. We can't change a[1] however, because putting the 2 colored side down only gives us a stack of 4, which isn't taller than 6.
So for each side of each block, see if you can add it to some tower to get a better one. Keep an array of strings, s[], where s[i] is a running log of what blocks are on which tower. At the end, find the tallest tower by iterating over all colours, and output it. 
#10055  Hashmat the Brave WarriorSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Super duper easy.
You don't even need any variables save one.
Normally you would just immediately output:
Math.abs(scan.nextLong()  scan.nextLong())
however the input is a little big. So, use a StringBuffer, and simply append to it instead of System.out.println'ing each time. Then print the string buffer at the very end. Runs in 1.5 secs with Java. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  This is one of the more irritating trivial problems. First, make sure you're using unsigned ints or longs. Next, the problem description is wrong. It says that Hashmat's army will never be greater, but it actually will, so take the absolute value of the difference. Finally, you need to use BufferedReader and StringTokenizer in Java. The input is so massive that it'll take over 2.5 seconds even with fast input. 
#10056  What is the Probability?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Given that the game could go on infinitely, the probability is an infinite series. For the first player, it is:
p + p*(1p)^n + p*(1p)^2n + ...
That is, the chance of the first player winning is the chance that he gets the event on his first try, plus the chance that he gets it on his second try (after n people have failed, him included), plus the chance that he gets it on his third try, ad infinitum.
In general, for player I (1indexed) the probability is:
p*(1p)^(k1) + p*(1p)^(n+k1) + p*(1p)^(2n+k1) ...
Given that the problem requires four digits of precision, you can just keep adding terms until the amount that you would add is too small to make a difference (say, less than 10^8). This doesn't take many iterations, as the terms decrease in size extremely rapidly. 
#10057  A midsummer night's dream.Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math sorting
 Solution Description:  The value A must be the median of the given data. On small data sets, it's easy to get the median by sorting and taking the middle value, but that's O(n log n) and N = 1,000,000 in this case. Luckily though, we are guaranteed that all the numbers are less than 65536, and that lets us find the median quickly by using a psuedoconstant time algorithm. That is, O(K), where K is the largest number in the input.
Let a[i] be the number of times the number i appears in the input. Fill in this array as you take in the input. Afterwards, search through from a[0] to a[65535], summing up all of the values, until you exceed n/2. The bin that puts you over n/2 must be the median. Of course, it's possible that two different values are the median if n is even, so watch out for that.
There are basically two cases for this problem:
Case 1: The median is unique (that is, n is odd, or n is even but the median is still unique)
 A is the median
 The number of numbers in the input that are A is a[A]
 Only 1 distinct integer could possibly be A.
Case 2: n is even, and there is no unique median
 A is the lower of the two medians
 The number of numbers in the input that could be A is a[low median] + a [high median]
 The number of distinct integers that could be A is (high median  low median + 1)
Given that there's a 30 second time limit for this problem, you could probably sort to find the median... but by finding the median in psuedoconstant time, this runs in about 2 seconds in Java, and that's with slow I/O (Scanner, println). 
#10062  Tell me the frequencies!Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  sorting
 Solution Description:  Use an int array, and iterate through your input line  incrementing each element corresponding to the ascii value of the current character.
At the end, use an ArrayList and a Comparator to sort your results based on frequency and ascii value (an arraylist of points, that is), and output. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  sorting strings
 Solution Description:  Keep an array of objects that have an ASCII value and a frequency. Iterate through the string incrementing the frequency of each character you find. At the end, just sort (by frequency ascending, then ASCII value descending) and output any element that has a nonzero frequency. 
#10066  The Twin TowersSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is an LCS (Longest Common Subsequence) problem, and there's a dynamic programming solution for it.
I'd actually forgotten the DP, but I sat down, wrote down a recurrence, and wrote an iterative solution that got AC  so I'm quite pleased with myself.
Recurrence:
Given two strings, astr and bstr,
LCS(a, b) = the LCS of astr.lengthOf(a) and bstr.lengthOf(b)
We need to define p as being the last place in b where the last character in astr.lengthOf(a) occurs last (which is 1 if it doesn't at all).
if(p == 1)
LCS(a, b) = LCS(a1, b)
else
LCS(a, b) = LCS(a1, p1) + 1
To explain:
We look at the last character in astr at its current length of a (the substring of length a that is), and iterate back through the current substring of b to find the last place it occurs.
If it never occurs, then the LCS here is just the LCS when a.length = a.length1, since there's no more length being added to the LCS.
If it does occur, then the LCS here should be the LCS without the last character of a, and without the character that matches in b (and the characters after it of course). This IS just LCS(a1, p1)  but we add 1 'cause we've increased the LCS.
But wait! One thing is missing still  it is possible that LCS(a1, b) > LCS(a1, p1)+1  so we have to redefine our recurrence with a MAX statement.
if(p == 1)
LCS(a, b) = LCS(a1, b)
else
LCS(a, b) = MAX(LCS(a1, p1) + 1, LCS(a1, b))
... and that's it! just replace "LCS" with an array name, iterate, and you're set.
Awesome 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is just a Longest Common Subsequence DP. My solution for Problem 10405 has the recurrence.
See also:
10100 (Longest Match)
10405 (Longest Common Subsequence) 
#10067  Playing with WheelsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  This is a fairly simple BFS problem. Let every number from 0 to 9999 be a node, and draw an edge between any two numbers that are off by only digit from each other. Run BFS on this graph, but make sure not to traverse any of the forbidden nodes. 
#10069  Distinct SubsequencesSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  dynamic programming strings
 Solution Description:  The DP for this problem isn't too hard, but you'll need to use an array of BigIntegers to store everything.
Let X be the sequence, and Y be the subsequence you're looking for.
Let a[i][j] be the number of times the sequence (Y1 ... Yi) appears inside the string (X1 ... Xi).
Initially, a[0][j] = 1 for all j, as the null string appears once in any string. Also a[i][0] = 0 for all i > 0 as a nonempty substring of the subsequence cannot appear in an empty string.
Iterate through a[][] rowbyrow with the following recurrence:
If Yi == Xj, a[i][j] = a[i1][j1] + a[i][j1]
(You have 1 new match for every occurence of Y1...Yi in X1...Xj)
If Yi != Xj, a[i][j] = a[i][j1]
(No new occurence, so copy previous value)
At the end, output the last cell of the array. 
#10070  Leap Year or Not Leap Year and ...Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  Just follow the given rules. Note that the festivals are huluculu and bulukulu and NOT hulukulu or buluculu.
Also, you'll need to use BigInteger for the input (which is why the solve rate for this problem is so low  no bounds are given). 
#10071  Back to High School PhysicsSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Given v and t, output 2*v*t 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  When it says "has initital velocity" it should say "has initial veolcity 0".
From physics, d = vi + (1/2)at^2. Even if you haven't taken physics you should be able to derive this formula knowning that d = integral(v + at) dt.
Given that vi is 0, and that a is v/t, the formula becomes d = 2vt. Be careful not to confuse the t in the first formula with the t in this one. The former is the "doubled" time, and the latter is the time given in the input.

#10074  Take the LandSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force dynamic programming
 Solution Description:  The straight up bruteforce would be O(n^6) so we obviously need to reduce that. Let sum[i][j] be the sum of the subrectangle from (0,0) to (i,j). This table can be completed in O(n^2).
Then, iterate through all possible subrectangles and calculate their sum using this table. The general formula is:
sum[i][j] = a[i][j] + sum[i1][j] + sum[i][j1]  sum[i1][j1]
...assuming that a[i][j] is the value in the cell (i,j).
Now you can "brute force" the subrectangles, but in O(n^4) instead of O(n^6). 
#10077  The SternBrocot Number SystemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc math searching
 Solution Description:  The easiest thing to do here, I find, is to look for a pattern. Notice that whenever you traverse to a right child, you add the first fraction on the path back to the root that requires going to the right (and the same works for left).
For example, say we're at 3/5 and the fraction we're looking for is less than 3/5. We must traverse to the left, so we search back towards the root until we have to go left. The first time we go left is when we go to 1/2, so we add 1/2 to 3/5 and get 4/7 (obviously this isn't proper fraction addition, but addition in the m+m' / n+n' sense).
So, keep track of your path as you traverse the tree, and at each step search backwards to find the fraction to add. 
#10078  The Art GallerySolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry math
 Solution Description:  This problem boils down to determining whether or not a given set of points forms a convex polygon.
For each set of three consecutive points A, B, and C, create two vectors P = AB and Q = AC. Take the cross product of P and Q, and check the sign (positive or negative). If the sign is the same for all n sets of three consecutive vertices, then the polygon is convex, so print "No". Otherwise, print "Yes". 
#10079  Pizza CuttingSolved By:  peter  Theory Difficulty:  medium  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  A little mathy for my liking, but still doable.
For each cut, you are guaranteed to be able to intersect all the previous cuts. If you sketch out the first few cuts, you'll see that:
p(n) = p(n1) + (n1) + 1
that is, for any given pizza with n cuts, the maximum number of slices is equal to a pizza with n1 cuts, plus one slice for every cut that is intersected by the nth cut ( we know that to be n1 ), plus 1.
From this, you get a recurrence that can be solved to give a constant time function:
p(n) = p(n1) + n
p(n) = (n*(n+1))/2 + 1 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  On the ith cut, you can cut through i pieces of pizza. Therefore the total number of cuts is the triangular number sequence. As you start with one piece, you must add one to all the terms.
So for each input n, output n*(n+1)/2 + 1. 
#10080  Gopher IISolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  2D geometry max flow
 Solution Description:  This is a maximum matching problem. We want to match each gopher to a hole, if possible, and we want to match as many as we can.
Maximum matching can be solved with maximum flow, so set up a flow network with the following edges:
 an edge between the source and each gopher, with capacity 1
 an edge between each hole and the sink with capacity 1
 an edge between each gopher G and each hole H where the dist(G, H) <= s*v
Run maximum flow on this network to get the number of gophers that can be saved, and output (n  saved). Don't make the mistake of outputting the number of saved gophers! 
#10081  Tight WordsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  It should be clear that you can only construct a longer tight word from a shorter one. That leads to a fairly straightforward DP solution.
Let a[i][j] be the number of tight words of length i that end in digit j.
a[1][i] = 1 for all i
[Any length 1 word is tight]
a[i][j] = a[i1][j1] + a[i1][j] + a[1i][j+1]
[You can attach a digit to the end of a tight word if it is within 1 of the digit the word ended with]
Obviously, there are edge cases:
a[i][0] = a[i1][j] + a[i1][j+1]
a[i][k] = a[i1][j] + a[i1][j1]
You can't add 1 or k+1 to the end of a word.
It works well to make a[][] and array of doubles, because you may be storing some very large numbers, and you only need double precision anyways.
At the end, sum up a[n][i] for all i. This is the total number of tight words. Divide this by the total number of words, k^n, to get your solution. 
#10082  WERTYUSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Setup two strings, that will 'map' one character to another. Here are mine:
String one = "`1234567890QWERTYUIOP[]ASDFGHJKL;ZXCVBNM,. ";
String two = "1234567890=WERTYUIOP[]\\SDFGHJKL;'XCVBNM,./ ";
You have to be careful of the escape character that will pop up.
Then just loop through, not outputting each time  but rather adding to a Stringbuffer called 'output' and then printing it at the VERY end.
Your solution boils down to iterating through each line and:
output.append(one.charAt(two.indexOf(in.charAt(i)))); 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Keep two strings:
IN = " 1234567890=WERTYUIOP[]\\SDFGHJKL;'XCVBNM,./"
OUT = " `1234567890QWERTYUIOP[]ASDFGHJKL;ZXCVBNM,."
For each character in the input, find its index in IN and output the character at that index in OUT. 
#10093  An Easy Problem!Solved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  brute force
 Solution Description:  Wow, this was definitely one of the most annoying problems I've ever struggled through. Do everything normally, like you think it should be done in the problem description and:
so it doesn't TLE, run through the input once before hand and find the largest number used > then start check your bases up from there+1
accommodate stupid input like... +++0, +0, ;, *, by ignoring everything except alphanumeric characters
make sure an input of 0 outputs 2, and an input of 2 outputs 3.
either use doubles / BigIntegers to store your converted into decimal number numbers, or be tricky and know that you can just sum the digits without multiplying by Math.pow(base, digitindex) 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Not quite as easy as the title would lead you to believe, but mostly because of the input formatting.
Determine the smallest base that the given number could be in by taking its largest digit + 1. Then search from that base to base 62 to see if the number is divisible by N1. If it is, print out the lowest base, if it isn't, print out that it's impossible.
No bounds are given on the size of the number, so you must use BigInteger, or use the handy theorem that a baseN number is divisible by (N1) iff the sum of its digits are divisible by (N1).
Be warned that for some reason the input might contain "+" in front of the number. 
#10098  Generating FastSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  Sort the string, and use PETER'S Algorithm to find each of the next permutations. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  Sort the string ascending, then use Dijkstra's permutation algorithm to get every permutation in lexicographical order (see Problem 146  ID Codes).
In Java, use StringBuffer to hold all the output, and then print it all at once at the end. You may be printing up to 10! lines for each test case, so you definitely don't want to be calling System.out.println() that many times. 
#10099  The Tourist GuideSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall
 Solution Description:  This is a maximin FloydWarshall problem. See problem 544 if you need the algorithm.
Let k be the number of people you can take on the optimal root, and let p be the number of people you have to move. Output ceil(p / (k1)). The k1 term encodes the fact that the tour guide must also fit on the bus.
See Also:
Problem 544 (Heavy Cargo)
Problem 534 (Frogger) 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
