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.

#10100 - Longest Match

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
strings
Solution Description: This is a fairly straightforward Longest Common Subsequence problem. There are a couple of things that aren't stated clearly in the problem description though. First, the longest match does not have to be continguous in either string. For example:

bob ate cake
bob likes cake

The longest match is 2 (bob, cake) even though it isn't contiguous.

Secondly, exactly which characters count as non-letter punctuation isn't given. For the sake of convenience, it's these:

!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

Make sure to escape any characters if necessary (like slash and quote for Java and C++).

After that, just run Longest Common Subsequence on both strings. Wikipedia has a nice implementation and description of it.


#10101 - Bangla Numbers

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:recursion
Solution Description: Stupid problem, horrible description.

You need to offset each result, so that the test case index is right aligned in a column of spaces 4 width.

Don't show any zeros. At all - unless the number you're given is 0. Then you show just it.

Define your basic conversion function as a method, and then do a small recusive call for when kuti >= 100.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
simulation
Solution Description: This problem is basically the opposite of Problem 486 (English-Number Translator).

The trickiest part is calculating how many kuti there are. Where n is the input:

kuti = n / 10000000
n -= kuti * 10000000

Now you need a set of statements to parse how many kuti there are. Something like this:

lakh = kuti / 100000
kuti -= lakh * 100000

hajar = kuti / 1000
kuti -= hajar * 1000

shata = kuti / 100
kuti -= shata * 100

Make sure that you only print out a type of number if there is more than 0 of it. Once you've calculated how many kuti there are, use the same sort of setup with what remains in n to calculate the other numbers.

Two tricky cases to watch out for:

0 (output = "0")
100000000000001 (output = "1 kuti kuti 1")

Also, there may be leading zeroes in the input, but if you're reading the input as a number, that shouldn't be a problem.


#10102 - The path in the colored field

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: When taking in the input, keep a list of all 1-nodes and all 3-nodes. For each 1-node, find the distance to the closest 3-node. Use abs(1.x - 3.x) + abs(1.y - 3.y). Output the greatest distance amongst all 1-nodes.


#10104 - Euclid Problem

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Given A and B, use the extended Euclidean algorithm to determine not only gcd(A,B) but also the solutions (X, Y) to AX + BY = gcd(A,B).

The extended Euclidean algorithm already guarantees that |X| + |Y| is minimal, and that X <= Y after that, so you don't need to worry about those conditions.

In Java, you'll need to use BufferedReader and StringTokenizer. Also, it may help to use the iterative form of the algorithm instead of the recursive form to reduce overhead from function calls. All in all, mine is just barely within the time limit at 2.870s.


#10105 - Polynomial Coefficients

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: While the answer to this problem is quite simple, the derivation is not. For a complete derivation, see:

http://www.comp.nus.edu.sg/~stevenha/programming/volC1.html#10105%20-%20Polynomial%20coefficients

Here's a quick overview:

Let n(k) be the power of the kth term in the monomial we're asked to examine.

Given the polynomial (x1 + x2 + ... + xl)^n, we can break it up using the binomial theorem:

((x1 + ... + xk-1) + xk)^n

[sum from i = 1 to k] (n C i) * (x1 + ... + xk-1)^n-i * xk^i

The only term we care about is where i = n(xk), so we can through away the rest. We keep breaking this down recursively until we end up with a product of Chooses, which we can then simplify into a simple final form:

n! / (n(1)! * n(2)! * ... * n(k)!)


#10106 - Product

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Really easy. Use BigIntegers and multiply them. Output.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just multiply two BigIntegers together.


#10107 - What is the Median?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
sorting
Solution Description: You'll need some sort of data structure that keeps an ordered list of elements. It doesn't have to be fancy. I just used an array and used linear search to find where to put the next element, and then swapped all other elements out of the way.

Keep track of how many elements are in your array. Call this n. Let x and y be the indices of the two numbers that make up the median. If x and y are the same, then there is just one number that is the median. Assuming a o-indexed array:

x = (n-1)/2
y = n/2

Output (a[x] + a[y]) / 2 at every iteration. Make sure that you're using unsigned int, or long, as 2^31 + 2^31 won't fit in an unsigned int.


#10110 - Light, more light

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: given a, a java long, that is your n

if(Math.pow((int)Math.sqrt(a), 2) == a)
-----print yes
else
-----print no

We can figure out that if there are an odd number of factors, then the light is on, and the vice versa.

But, since an odd number of factors implies that one pair of the factors, which are sides of the square with area a, must be the same, you can just determine if its a perfect square to get the solution.

O(sqrt(n)) seems to be too slow for this problem.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: There are two ways of approaching this problem. The O(sqrt(n)) is to search from 1 to sqrt(n) looking for any number that divides n evenely. The number of divisors below sqrt(n) is the same as the number of divisors above it, so you only need to find the first half. Then, just print "yes" if you get an odd number, or "no" if you get an even number.

During this process however, you may realize that the only way a number can have an odd number of factors is if it's a perfect square. So the O(1) solution is to just print "yes" if the number is a perfect square, and "no" otherwise.

Note: You must use an unsigned int (or a Java long).


#10111 - Find the Winning Move

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:ad hoc
dynamic programming
recursion
Solution Description: The main factor in this problem is efficiency. After three attempts, I got it to run in Java in just over 2.7 seconds.

With 4 moves already done, the search space for each game is on the order of 12! ~= half a billion. Obviously, many of these states are invalid, but it's still a lot, and is definitely way too many states to search for each game. So, you'll want to store. As you're playing the same game each time, the results you store from one game will help you speed up the next game.

The number of valid states for the game is less than 5 million, so it's quite reasonable to store a good majority of them.

I keep 4 hash tables to store different results. The keys for the hash tables are game states where the rows are concatenated into one string. So, the state

....
.xo.
.ox.
....

becomes the string ".....xo..ox.....".

The most important hash table is a mapping from states where X is guaranteed to win to Point objects that say where X should play. The other hash tables are just HashSets of states where X is guaranteed to not win, states where Y is guaranteed to force a draw or win, and states where Y is guaranteed to not force a draw or win.

There's not much else to do except write a solver for the game recursively, and store all the results you can. Try to be as efficient as possible, especially if you're using Java. Use StringBuffers rather than Strings to construct the states.


#10112 - Myacm Triangles

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
brute force
Solution Description: Brute force all possible combinations of points that make triangles. For each triangle, find the area with the given formula (which is just the cross product / 2). If the area is greater than the best are you've found so far, check that all other points are outside the triangle.

To check whether a point P is inside a triangle ABC, find the angle between all pairs of vectors AP, BP, and CP using the dot product. The angle between two vectors A and B is:

acos((A dot B) / (|A|*|B|))

If the sum of the three angles is 2*pi, then the point is inside (or on an edge of) the triangle. If the sum is less than 2*pi, then the point is outside the triangle.


#10115 - Automatic Editing

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Just follow the directions as given. Exhaust one rule completely before moving on to the next.

If you use the built-in string methods of your programming language, it should be very easy to code. Use StringBuffer, indexOf(), and replace() in Java.


#10116 - Robot Motion

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep an array of integers where a[i][j] is the number of steps it takes to get to (i,j). By default, all of these values will be 0 except for your starting location which will be 1.

At every iteration, change the current row and column according to the letter the robot is standing on. Let (x,y) be the new co-oridinates, and let (ox,oy) be the old co-ordinates.

If the robot leaves the grid, print the last number is was standing on (that is, a[ox][oy]). If the robot moves to a cell that has a number greater than 0, then it has entered a loop. The robot must have traveled (a[ox][oy]-1) steps before entering the loop, and the loop is (a[x][y] - a[ox][oy] + 1) steps long.

If the robot remains on the grid and moves into a cell that has not been traversed, then a[x][y] = a[ox][oy] + 1.


#10125 - Sumsets

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
sorting
Solution Description: It's possible to do this problem in as little as O(n^2), but O(n^3) seems to be fine (< 0.6s in Java).

First, store all the input in an array, and sort it. Also, store every element in a HashSet, because we'll want constant time retrieval in a moment.

Iterate through all possible pairs of data, and store each pair (a, b) in a list. Only store pairs where a != b.

Now, iterate through the data from highest to lowest. These will be our d's. For each d, check each pair (a, b) to compute c = d - a - b. Use the HashSet to confirm that c is a valid data point, and then make sure that all of a, b, c and d are distinct. If so, you have an answer.


#10127 - Ones

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Use BigIntegers. Create the following BigInts:

zero := 0
one := 1
ten := 10
n := input
s := string of len(input) of 1's

keep adding a 1 to s and checking if s mod n == zero. Add the 1 by multiplying by 'ten' and adding 'one'. If you hold a string s, add a 1, and convert it to a BigInteger each time you check, this problem will TLE.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: If you try to brute force the solution using BigInteger, it'll take far too long. So instead, we need to simulate long division.

Take 7 for example, and imagine we have an infinite amount of 1's to divide by 7. At the first step we do 11 / 7 as 11 is the shortest string of 1's that isn't less than 7.

11 / 7 gives us a remainder of 4, which in long division would drop down to the next line. And of course, we'd continue to drop 1's down until we have a number larger or equal to 7 again. In this case, that's 41. So we do 41 / 7, get a remainder of 6, and try again with 61.

We keep going until we get a remainder of 0 and have therefore finished the process. So where your starting number is n, keep a variable rem that is initialized to the shortest string of 1's that isn't less than n. Then:

while(rem > 0)
{
while(rem < n)
---append 1's to rem
rem = rem % n
}

Every time you append a 1, increment a running count. At the end, output this count. Don't forget to include the 1's you used to initialized rem in the first place.


#10128 - Queue

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: There are two important observations to start with. Firstly, the tallest person will always be seen from both sides. Secondly, if there is a total ordering amongst all of the people, then any subset also has a total ordering.

Knowing that the tallest person will be seen from both sides, and will always be the *last* person seen from both sides, we can remove him and deal with the left and right sides separately.

Let a[i][j] be the numbers of ways you can arrange i people in a row such that you can see j of them if you look at them from a given direction. If our input is N P R, then we want the following value:

a[0][P-1]*a[N-1][R-1]*C(N-1, 0) + a[1][P-1]*a[N-2][R-1]*C(N-1, 1) + ... + a[N-1][P-1]*a[0][R-1]*C(N-1, N-1)

Now for some explanation... after we take out the tallest person, we have to choose how many people to put in front of him, and how many to but behind. We can try putting 0 in front, 1 in front, etc. up to N-1 in front. If we choose to put X people in front, then N-X-1 people go behind, and we calculate the following value:

a[X][P-1] * a[N-X-1][R-1] * C(N-1, X)

The first term is how many ways we can arrange the people in the front, the second term is how many ways we can arrange the people in the back, and the third term is how many ways we can choose *who* goes in the front and who goes in the back. (To be clear, C(n, k) is the combinatorial choose function)

So, we sum up this value for all X, and return the result. However, calculating a[i][j] takes some work of its own.

Obviously, if i < j, a[i][j] = 0. If i == j, a[i][j] = 1. Otherwise:

a[i][j] = a[X][j-1] * (j - X - 1)! * C(i-1, j - X - 1)

This is similar to what we did above. The tallest person in the group will be seen no matter what, so we have to choose who goes in front, and who goes behind. X iterates from i-1 to j-1 (inclusive) and is the number of people who go in front of the tallest. So...

a[X][j-1] is how we arrange the X people so that j-1 can be seen (recursive step). (j-X-1)! is the number of ways we can arrange the unseen people standing behind the tallest person. C(i-1, j-X-1) is the number of ways we can choose who goes in behind.


#10129 - Play on Words

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This problem boils down to finding a Euler path in a directed graph.

Make a graph with 26 nodes, where each node is a letter of the alphabet. For each word in the input, create a directed edge from the first letter of the word to the last letter of the word. Because you just want to determine the existence of an Euler path, you don't need to keep track of the entire graph. Just keep two arrays, one for in-degree, and one for out-degree, where in/out[i] is the in/out-degree of the ith node.

A directed graph has an Euler path under these conditions:

- All nodes have in-degree = out-degree (Euler circuit)
OR
- All but two nodes have in-degree = out-degree. Of these two nodes, one has in-degree = out-degree + 1 and the other has out-degree = in-degree + 1.

You will also need to confirm that the graph is connected, so use union find to join together all nodes that are connected by an edge (direction doesn't matter for connectivity here). Because not all of the letters may be used in any graph, pick an arbitrary node in your graph that was definitely used, and confirm that its set leader is the same as all other set leaders of used nodes. You can tell a node was used if in[i] + out[i] > 0.


#10130 - SuperSale

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is the classic DP (dynamic programming) knapsack problem!

I've never actually done one of these before, and although I have read about the recurrence, I'd pretty much forgotten the whole solution, so my DP might be a little different from the norm.

Now that I think about it, I just wrote a full explanation of the DP for LCS, so... I'll let wesley explain the details of this algo (Google will also tell you).

I want to rate this as easy-medium for theory.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a 0-1 Knapsack problem. Keep an array of integers where a[i][j] is the maximum value you can get with weight j, using items up to i. For convenience, label the items from 1 to n instead of 0 to n-1.

The maximum weight per person is 30, so just complete the table for j up to 30.

Let vi and wi be the value and weight of the ith item respectively. Then the recurrence is:

a[0][j] = 0 (There can't be any value with no items)
a[i][0] = 0 (There can't be any value with no weight)

a[i][j] = a[i-1][j] (if j < wi)
(You can't fit the ith item, so take the best value with i-1 items)

a[i][j] = max(a[i-1][j], a[i-1][j-wi] + vi) (if j >= wi)
(You can fit the ith item, so take the best of using it and not using it)

At the end, iterate through each person. Where n is the number of items, and wi is the weight the ith person can carry, add a[n][wi] to a running total. Output the total after you've finished with all the people.


#10131 - Is Bigger Smarter?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
sorting
Solution Description: Keep an array of elephant objects that hold a weight, IQ, and index (the number of the elephant). Sort this array by increasing size, and then by decreasing IQ. Then run Longest Increasing Subsequence (actually Decreasing in this case) on the array looking only at IQ.

Keep an array of ints where p[i] is the previous elephant in the chain ending in elephant i, so that you can reconstruct the path once you're done.


#10137 - The Trip

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
Solution Description: For convenience (and to avoid using doubles), store all values as cents. So multiply dollars by 100, and add cents. Store all of the input values in an array, and sort them ascending.

Now, take the sum of the values, and calculate these two quantites (where n is the number of people):

average = sum / n
pennies = sum % n

The average is the amount that everybody must have at a minimum, and the pennies are the leftover cents. The number of pennies is also the number of people who will have 1 cent more than the others at the end.

Now start at the end of the array (the highest values), and for each element, transfer money to whoever needs it (search from the low side). For each person that has lots of money, transfer as much as will bring them down to the average, or to (average+1) if there are pennies remaining (and then decrement pennies). In this way, the people with the most money will be the ones that keep the extra pennies. Make sure to keep track of how much money is being transferred.

At the end, when everybody has at least the average amount of money, if there are still some pennies remaining, add them to your running total of transferred funds.


#10139 - Factovisors

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Let P(x) be the multiset of prime factors of x. So, P(24) = {2, 2, 2, 3}

If m divides n!, then P(m) is a subset of P(n!). So for each prime factor in m, we need to make sure there are at least that many of that prime factor in n!

Factorizing m is easy, but obviously we can't factorize n! How do you determine how many times a certain prime factor appears in n!?

Take the case of finding all the prime factors in 10!

10! = 10*9*8*7*6*5*4*3*2*1
10! = (2*5) * (3*3) * (2*2*2) * 7 * (2*3) * 5 * (2*2) * 3 * 2 * 1

Obviously, there's a 2 in every second element of 10!, and there's a 3 in every third, etc. Now, in every fourth element of 10! there's a second 2. And in every eighth element, there's a third 2.

This gives us the following pseudocode to count how many times a prime p appears in n! :

count = 0;
pow = p;
while(pow < n)
--- count += n / p; (integer division)
--- pow *= p;

Don't forget the special case of m=0. 0 does not divide anything.


#10141 - Request for Proposal

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: This problem can be made a lot easier by recognizing that the requirement names have absolutely no bearing on the problem. You're guaranteed that all requirements in each proposal will come from the requirements list and won't be duplicated. This means that all you need to care about is the number of met requirements, and not what they are.

Run through the list of proposals, keeping track of the best one (by number of requirements met, and then by price). Discard all lines that have requirement names on them. At the end, just print out the best company.


#10142 - Australian Voting

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep an array of strings with the candidates names, and array of booleans where e[i] is true if candidate i has been eliminated, and an array of integers where v[i] is the number of votes that candidate i has (in a given round).

Take in the ballots as Ballot objects that each have an array of integers (representing the preferences on the ballot), and an index that points to the highest non-eliminated candidate on that ballot.

At each round in the voting process, reset v[] to all zeroes and iterate through all of the ballots, counting how many votes each candidate has.

After, iterate through the candidates and find the minimum and maximum number of votes. If the maximum is greater than (number of ballots / 2) then find the candidate who has the maximum; that's the winner. If the minimum and maximum are the same, then all remaining candidates are tied, so print out the names of every non-eliminated candidate.

If neither of these situations are the case, then eliminate every candidate who has the minimum number of votes (set e[i] to true). Then, iterate through all of the ballots, advancing the index counter for each to the next non-eliminated candidate.

You may need to use BufferedReader in Java. I haven't tried it with Scanner, so I'm not sure.


#10150 - Doublets

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:other graph
strings
Solution Description: This is a highly optimized BFS problem. Here are the optimizations that need to occur:

1) Use BufferedReader and StringBuffer in Java.

2) Use a hash table (HashMap in Java) to map the dictionary strings to an integer representing their node number in the graph.

3) When making the adjacency matrix, don't do the standard O(n^2) pairwise comparison. Instead, iterate through all possible doublets of the given word as there can be no more than 400 per word (25 letters * length of 16) and check the hash table for these doublets.

4) When doing BFS, do the sparse graph version that runs O(|E|) instead of O(|V^2|). I used an array of ArrayLists as my adjacency matrix, where a[i] is the list of nodes that node i is connected to.


#10152 - ShellSort

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Search the stack of turtles from the bottom to the top. Let X be the number of turtles that need to be moved, initially 0. For each turtle, determine the distance between its current position, and where it should be in the final stack. If it is exactly X places higher than it should be, ignore it and move on. Otherwise, add this turtle to a list of turtles that must be moved, and increment X.

At the end, sort the list of turtles that need to be moved by ascending stack position, and output them.

Example (2nd test case):

The turtles are arranged as such from top to bottom (indices are the position they must end up in):

1 4 3 5 6 2 7 8 9

From the bottom, we see that turtles 9, 8 and 7 are in the right locations, so we skip them. Turtle 2, however, is not. So we add 2 to a list, and set X to 1.

Turtles 6 and 5 are both 1 position higher than they should be, but X = 1, so we skip them. Turtle 3 is not 1 position higher than it needs to be, so we add 3 to a list and set X to 2.

Turtle 4 is 2 positions higher, so skip it. Turtle 1 is not 2 positions higher, so add it to a list.

At the end, output the turtles in the list in ascending position, so output 3, then 2, then 1.



Note: There is a fair bit of input, so you may need to use a hash table (in Java at least) to match names to positions.


#10161 - Ant on a Chessboard

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Where n is the input, let sr = (int)sqrt(n).

To find the co-ordinates in constant time, start from the nearest square root less than your final position.
For example, if the input is 14, then start from 9 and walk to 14. If the input is 26, start from 25 and walk to 26.

Notice that if sr is odd, then the initial position is (1,sr). If sr is even, then the initial position is (sr,1).

Now, subtract sr*sr from n, and you have the number of steps left to walk. If sr is odd, one step must be spent walking up, and if sr is odd, one step must be spent walking right.

After this, if sr is odd, up to sr steps can be spent walking right, and then sr steps can be spent walking down. If sr is even, then you go up and then left instead.

Handle even and odd sr separately. Here's a complete example of the even case:

x = sr
y = 1
n -= sr*sr

if(n > 0) //move right
{ x++ n--
}

if(n > 0) //move up
{
go = min(sr, n)
y += go
n -= go
}

if(n > 0) //move left
{
x -= n
}


#10162 - Last Digit

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: There are a few simple observations right away. 1^1, 1^11, 1^21, etc. will all end in 1. Similarly, all powers of 5 and 6 end in 5 or 6. What about the other numbers? It turns out that if you look at i^i, i^(10+i), i^(20+i), etc. you can find a cycle for the last digit of each 0 <= i <= 9. The cycles are as follows:

0 - 0, 0, 0...
1 - 1, 1, 1...
2 - 4, 6, 4...
3 - 7, 3, 7...
4 - 6, 6, 6...
5 - 5, 5, 5...
6 - 6, 6, 6...
7 - 3, 7, 3...
8 - 6, 4, 6...
9 - 9, 9, 9...

All these cycles are of length at most 2, so for every 10*2 = 20 elements in your sequence, the last digit must increase by a certain amount.

If you add up the last digits of the first 20 elements, you get 94, which is to say, the last digit of the sum of the sequence increases by 4 for every 20 elements. This itself is a cycle:

n = 0 --> Last digit is 0
n = 20 --> Last digit is 4
n = 40 --> Last digit is 8
n = 60 --> Last digit is 2
n = 80 --> Last digit is 6
n = 100 --> Last digit is 0

So every 100 elements, the last digit doesn't change at all. Now, for a given n, you can take n % 100 and get the same answer. Just precompute the first 100 answers, and read them off.


#10165 - Stone Game

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: This is exactly the game of Nim. There's a theorem that you will win Nim iff the XOR of the sizes of all the piles is not 0.

The pile sizes are all nice signed 32-bit integers, so there's nothing special here. Just XOR all the numbers and return "Yes" unless the XOR is 0.


#10167 - Birthday Cake

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
brute force
Solution Description: You know that the integers A and B lie inside the range [-500, 500] so just brute force all combinations.

If you evaluate Ax + By for a given point (x,y), the sign of the answer tells you which side of the line the point lies on. So, make sure that you get n positive answers, and n negative answers (and no 0 answers).


#10168 - Summation of Four Primes

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
recursion
Solution Description: This problem can be solved quickly with smart backtracking.

Use the Sieve of Eratosthenes to generate the primes up to 10,000,000. Define a function f(n,d) that returns true if n can be written as the sum of d primes. f(n,1) is true iff n is prime.

For f(n,d) where d > 1, try calling f(n-p[i], d-1) for every prime p[i] less than n. Start with the largest primes first and work your way down. You'll find that you search very few numbers for any input this way.


#10169 - Urn-ball Probabilities !

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: The probability of drawing two red balls on the ith draw is (1/i * 1/(i+1)). The probability of drawing two red balls at least once is:

1 - (probability of never drawing two red balls)

1 - [(1 - (1/1 * 1/2)) * (1 - (1/2 * 1/3)) * ... ]

You can pregenerate this. Let p[i] be:

(1 - (1/1 * 1/2)) * ... * (1 - (1/i * 1/(i+1)))

You can then calculate p[i+1] from p[i]. When you're asked for the ith draw, output (1 - p[i]).

Now for the next part... the probability of drawing two red balls every step is:

(1/1 * 1/2)(1/2 * 1/3)(1/3 * 1/4) ...

We want the number of zeroes in this expansion, which is (almost) equivalent to taking the negative base 10 logarithm. So:

-log[ (1/1 * 1/2)(1/2 * 1/3) ... ]

-[log(1/1) + log(1/2) + log(1/2) + log(1/3) + ...]

Let l[i] be log(1/1)+log(1/2) + ... + log(1/i)log(1/(i+1))

Again, you can easily use dynamic programming to calculate l[i+1] from l[i].

At the end, output Math.ceil(-l[i]) - 1.


#10170 - The Hotel with Infinite Rooms

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:math
searching
Solution Description: The day on which guests leave follows a familiar pattern:

1 guest leaves on day 1
2 guests leave on day 3
3 guests leave on day 6
4 guests leave on day 10
...

It's the triangular number sequence, T[n] = n(n+1)/2

You can solve the quadratic equation:

n(n+1)/2 <= d

...or you can just use binary search to find the answer.

Now, all of this presumes that the starting group has 1 person, but if S > 1, then just modify d accordingly to account for the missing people:

d <-- d + T[s-1]

And now treat d as though there was 1 person in the first group.


#10176 - Ocean Deep ! - Make it shallow !!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: Just take in the number as a BigInteger, and use the BigInteger mod function. The only mildly tricky part is the parsing. I'm not sure if blank lines appear in the input, but I'd watch out just in case.


#10179 - Irreducable Basic Fractions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Basically, for a given integer n, we want to know how many numbers < n are co-prime with n. Luckily, there's a function that does exactly that: Euler's totient (phi) function.

phi(n) = n * [(1 - 1/p) for all primes p such that p|n]

So, factor n, and use the prime factors to computer phi(n).


#10182 - Bee Maja

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
sorting
Solution Description: First, determine the ring that the given cell belongs to. Note that the ith ring has i*6 cells. Treat cell 1 as a special case.

Where n is the given cell number:

r = 0
k = 1

while(n > k)
{
r++
k += r*6
}

r is now the ring number that the cell belongs to, and k is the last cell in that ring. Keep two variables, x and y, to hold the coordinates. Initially, x = r, and y = 0.

Now, backtrack around the ring counterclockwise until k = n. This can be done with 6 while loops where each one modifies the co-ordinates in a different way.

For example, let n = 8:

After running the first part, we will get k = 19, x = 2, y = 0. Note that (2,0) is cell 19. In the first part of the backtracking, we decrease y until x = -y (going up). Then we decrease x until x = 0 (going up and left). Then we decrease x and increase y until y = 0 (going down and left) ...etc...

At every iteration, decrease k as well. Once k = n, x and y hold the co-ordinates of cell n.


#10183 - How Many Fibs?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: There are less than 500 Fibonacci numbers under 10^100. So pregenerate the first 500 with BigIntegers, and for each set of input, iterate through all of them and count how many are between a and b.


#10188 - Automated Judge Script

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
strings
Solution Description: First, compare the strings for equality. If they match, give AC. If not, extract the numeric characters from each set of strings, and see if they all appear in the same order. If they do, give PE, and if not, give WA.


#10189 - Minesweeper

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:matrices
Solution Description: This is a quick, satisfying little problem.

As you take the input, keep a grid array of ints that start at zero. If you encounter a *, make that grid element -1000000, and add one to all the elements around it. You can pad your grid array to avoid throwing exceptions.

Output the grid array, and whenever you encounter an element < 0, just output a * instead!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:searching
Solution Description: Use an array of characters to hold the input. Iterate through it, and whenever you encounter a '.', search the 8 squares around it and count the number of '*' cells. Store this number (as a character) back into the array, overwriting the period.


#10190 - Divide, But Not Quite Conquer!

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: If n or m are less than 2, then the sequence is boring. Otherwise, while n > 1, check if n % m == 0, and then divide n by m. If at any point n % m != 0, then the sequence is boring. Otherwise, print out every number generated.


#10191 - Longest Nap

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Take in all of the appointments, sort them, and look for the longest gap between them. Don't forget to check the gap between 10:00 and the first appointment, and between the last appointment and 18:00.

Alternatively, you can make an array of 481 booleans to represent every minute between 10:00 and 18:00, colour the cells wherever appointments lie, and find the longest sequence of uncoloured cells.


#10192 - Vacation

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is just a Longest Common Subsequence DP. See Problem #10405 for the algorithm.

However, be warned that blank lines are legitimate input and must be handled (obviously if one parent suggests that you go to no cities, then 0 is the maximum).


See Also:
Problem #111 (History Grading)
Problem #531 (Compromise)
Problem #10066 (The Twin Towers)
Problem #10100 (Longest Match)
Problem #10405 (Longest Common Subsequence)


#10193 - All You Need Is Love

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Take in the first binary #, and put into int a using Integer.parseInt(scan.next, 2);

Do the same for the second #, putting it into b.

Use a gcd (greatest common divisor) function, and:

if(gcd(a, b) == 1)
----print 'you need more than love'
else
----print 'all you need is love'

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: The hardest part of this problem is deciphering what they really want from you. All you need to do is read in two numbers (albeit in base 2), and then determine whether or not their greatest common divisor is 1.


#10195 - The Knights Of The Round Table

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
math
Solution Description: s = (a + b + c) / 2.0

The radius is

Math.sqrt((s - a)*(s - b)*(s - c)/s)

Just be sure to handle when s == 0.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
Solution Description: The problem boils down to finding the radius of the largest circle that fits inside a given triangle. This circle is known as the incircle of the triangle, and its radius is:

2*A / p

...where A is the area of the triangle, and p is the perimeter of the triangle.

Use Heron's Formula to get the area of a triangle given the length of the sides:

A = sqrt(s * (s-a) * (s-b) * (s-c))

Where a, b, c are the side lengths of the triangle, and s is the semiperimeter ((a+b+c) / 2).

Beware the special case of one or more of the sides having length 0. In this case, just output 0.000.


#10196 - Check The Check

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:searching
Solution Description: Just do as the problem asks, and be very careful. Keep an array of characters where a[i][j] is the character at row i, column j. You may want to pad the array with 2 extra spaces around all sides so that you don't have to check for bounds with the pawn, king, or knight.

Iterate through your array, and for each space that has a piece on it, check all of its possible moves for the enemy king. As soon as you find a king in check, you can stop processing as you're guaranteed that there won't be a configuration with both kings in check.

The main things to watch out for:

- Make sure the pawns move in the proper direction (up for white, down for black)
- Make sure pieces don't attack their own king
- Make sure pieces don't move through other pieces (unless it's the knight)

My solution is just over 300 lines. It could be cleaned up a bit, but you'd be hard-pressed to do this in under 200.


#10197 - Learning Portuguese

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:sorting
strings
Solution Description: Just follow the given rules. There isn't a lot to say. However, this problem doesn't appear to be doable in Java because of the ASCII 243 character.


#10198 - Counting

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:dynamic programming
math
Solution Description: keep a results array, and when you need to get res[i], check if its been set. If it hasn't, iterate up from the last unset element, setting each to:

res[i] = res[i-3] + res[i-2] + 2*res[i-1]

Then output res[i]. Runs in O(n). The upper bound output for this solution uses many many many digits, so you'll have to use BigInteger

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Pregenerate an array where a[i] is the answer to input i, and then just print a[i] for any input.

Hardcode the first three terms:

a[1] = 2
a[2] = 5
a[3] = 13

Now it's just a simple recurrence. Whenever you want to get a sum n, you have three options. You can add a 3 to something with sum n-3, you can add a 2 to something with sum n-2, or you can add a 1 or 4 to something with sum n-1. Therefore, the recurrence is:

a[i] = a[i-3] + a[i-2] + 2*a[i-1]

You'll need to use BigIntegers as this recurrence grows a fair bit faster than the Fibonacci numbers.


#10199 - Tourist Guide

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This problem involves finding the articulation points of a graph. That is, vertices which, if removed, cause an increase in the number of connected components.

In my solution for problem 315 I describe the fairly trivial O(EV) algorithm, so here I'll describe the much nicer O(E+V) algorithm.

Do a depth-first search from an arbitrary vertex, and keep track of two quantites, Num and Low. Num[i] is simply the number of vertex i, in the order you come across it in the DFS. So, the vertex you start from is 0, and the next vertex you go to is 1, and so on. Low[i] is the minimum of Num[i], Num[x] where x is a vertex that connects to i directly, and Low[y], where y is a vertex that connects to i directly and has Num[y] > Num[i].

Intuitively, Low[i] is the lowest Num[x] amongst all vertices x that you can reach from vertex i by only going forwards in the DFS tree.

Now, to find articulation points, look for vertices i that have children, x, in the DFS tree such that Low[x] >= Num[i]. That means that x cannot reach any vertices higher than i in the DFS tree, and therefore it would disconnect x from some part of the graph if it was removed.

There is a special case for the root of the DFS tree. The root is an articulation point iff it has two children in the DFS tree.

See http://www.eecs.wsu.edu/~holder/courses/CptS223/spr08/slides/graphapps.pdf for some nice examples.

Note, however, that you are not guaranteed that this graph is connected to begin with. Therefore, you will need to run this algorithm on each connected component to find all the articulation points.

See Also:
- Problem 315 (Network)





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