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 Paths

Solved 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 Floyd-Warshall with edge weights of -1 to solve this. Obviously there are many other faster algorithms, such as Dijkstra or DP on a DAG, but Floyd-Warshall is the fastest to code by far.


#10002 - Center of Masses

Solved 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 y-coordinate, with ties broken by lowest x-coordinate. Sort the remaining points by increasing angle from the x-axis. 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 x-axis, 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 PN-1. 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 Sticks

Solved 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,j-1](dp[i][k] + dp[i+k][j-k]) + (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][j-k] is the minimum. To this minimum, add (a[i+j]-a[i]) which is the length (and therefore cost) of the stick.


#10004 - Bicoloring

Solved 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 depth-first search or a breadth-first 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 Numbers

Solved 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 non-prime 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 n-1)
{
res *= a;
res %= n;
}

It may take 2 minutes or so to determine the 15 Carmichael numbers.


#10007 - Count the Trees

Solved 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[n-1] + a[1]*a[n-2] + ... + a[n-1]*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 Floyd-Warshall.

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 x-coordinate of the center points of each one and do a sort of mini-DP:

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 sums

Solved 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 Calculations

Solved 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 = (An-1 + An+1) / 2 - Cn

Or rearranging:

2An = An-1 + An+1 - 2Cn

We can use this to solve for An-1:

3An-1 = 2An-2 + An+1 - 2Cn - 4Cn-1

And so on:

4An-2 = 3An-3 + An+1 - 2Cn - 4Cn-1 - 6Cn-2

So at the end we get:

(n+1)A1 = nA0 + An+1 - 2Cn - 4Cn-1 - 6Cn-2 - ... - (2n)C1


#10015 - Joseph's Cousin

Solved 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 Hanoi

Solved 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 N-1 disks to the spare, then move the biggest peg to the goal, and then move the N-1 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(N-1, source, spare, goal)
- hanoi(1, source, goal, spare)
- hanoi(N-1, 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 Add

Solved 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 Method

Solved 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 root

Solved 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 Newton-Raphson method works. It's a *very* fast algorithm for finding roots.


#10025 - The ? 1 ? 2 ? ... ? n = k problem

Solved 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 Problem

Solved 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 - Interpreter

Solved 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 - Freckles

Solved 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 union-find to implement Kruskal is probably the easiest way.


#10035 - Primary Arithmetic

Solved 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 - Divisibility

Solved 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[i-1] 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 Jumpers

Solved 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 (current-last) 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 n-2, 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 Family

Solved 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[j-1].

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 Numbers

Solved 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 Numbers

Solved 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 - Audiophobia

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: This is minimax Floyd-Warshall. 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 - Self-describing Sequence

Solved 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 non-decreasing, 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 - Hartals

Solved 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 Cubes

Solved 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 Warrior

Solved 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*(1-p)^n + p*(1-p)^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 (1-indexed) the probability is:

p*(1-p)^(k-1) + p*(1-p)^(n+k-1) + p*(1-p)^(2n+k-1) ...

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 mid-summer 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 psuedo-constant 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 psuedo-constant 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 non-zero frequency.


#10066 - The Twin Towers

Solved 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(a-1, b)
else
----LCS(a, b) = LCS(a-1, p-1) + 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.length-1, 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(a-1, p-1) - but we add 1 'cause we've increased the LCS.

But wait! One thing is missing still - it is possible that LCS(a-1, b) > LCS(a-1, p-1)+1 - so we have to redefine our recurrence with a MAX statement.

if(p == -1)
----LCS(a, b) = LCS(a-1, b)
else
----LCS(a, b) = MAX(LCS(a-1, p-1) + 1, LCS(a-1, 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 Wheels

Solved 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 Subsequences

Solved 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 non-empty substring of the subsequence cannot appear in an empty string.

Iterate through a[][] row-by-row with the following recurrence:

If Yi == Xj, a[i][j] = a[i-1][j-1] + a[i][j-1]
(You have 1 new match for every occurence of Y1...Yi in X1...Xj)

If Yi != Xj, a[i][j] = a[i][j-1]
(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 Physics

Solved 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 Land

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
dynamic programming
Solution Description: The straight up brute-force 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[i-1][j] + sum[i][j-1] - sum[i-1][j-1]

...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 Stern-Brocot Number System

Solved 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 Gallery

Solved 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 Cutting

Solved 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(n-1) + (n-1) + 1

that is, for any given pizza with n cuts, the maximum number of slices is equal to a pizza with n-1 cuts, plus one slice for every cut that is intersected by the nth cut ( we know that to be n-1 ), plus 1.

From this, you get a recurrence that can be solved to give a constant time function:

p(n) = p(n-1) + 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 II

Solved 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 Words

Solved 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[i-1][j-1] + a[i-1][j] + a[1-i][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[i-1][j] + a[i-1][j+1]
a[i][k] = a[i-1][j] + a[i-1][j-1]

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 - WERTYU

Solved 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 = "`1234567890-QWERTYUIOP[]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 = " `1234567890-QWERTYUIOP[]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 N-1. 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 base-N number is divisible by (N-1) iff the sum of its digits are divisible by (N-1).

Be warned that for some reason the input might contain "+" in front of the number.


#10098 - Generating Fast

Solved 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 Guide

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: This is a maximin Floyd-Warshall 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 / (k-1)). The k-1 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 PHPGraphLib - Click For Official Site