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.

#100 - The 3n + 1 problem

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
simulation
Solution Description: Create a function that will take n, and run the simulation, then return the number of turns used. Create a results array, and have the function use and store values from the array to save time. So, for example, for f(3) - if you've already calculated f(10) (3*3 + 1) before - just return array[10] instead of doing the whole simulation again.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
simulation
Solution Description: Define an array where a[i] is the number of steps it takes to get to 1 from i, using the Collatz function (i's "collatz value"). For instance:

a[1] = 1 (1)
a[2] = 2 (2, 1)
a[3] = 8 (3, 10, 5, 16, 8, 4, 2, 1)
a[22] = 16 (as per the problem statement)

Create a recursive collatz(i) function that returns the collatz value for i. The base case should be to return a[i] whenever a[i] has already been found. Otherwise, a[i] should be updated with the newly found value.


#101 - The Blocks Problem

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: This is just straight simulation. I used a two dimensional int array to hold where the blocks where, and then made all the moveonto, moveover, etc functions to work on the array. a[0][0] would start with the value 0, since a[0][0] is the floor level of the 0th column in 'space'.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Use a two dimensional array where a[i][j] is the jth block in the ith stack. a[i][0] = i for all i, and a[i][j] = -1 for all j > 0.

Then just implement the four functions carefully.


#102 - Ecological Bin Packing

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Brute force loops.

Test all combos of B, G, and C, and for each combo get the moves needed to satisfy that combo.

output the best.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: There are only 6 possible ways of arranging the bottles (BCG, BGC, etc.) so just brute force all combinations.

For example, the amount you would have to move for BCG is the sum of the brown bottles in bins 2 and 3, the clear bottles in bins 1 and 3, and the green bottles in bins 1 and 2.


#103 - Stacking Boxes

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:dynamic programming
Solution Description: A DP.

For each box, store it's info in a Box object, which has an array of ints that holds the side lengths of the box. Sort these lengths.

Then, when you have all the boxes, sort the boxes.

keep a dist[] array, and a from[]array. dist[0] = 1; from[*] = -1 by default.

iterate from the smallest box to the largest, and for each box x, iterate back to the smallest box, and grab the best dist[] of those boxes that fit inside the current x. make dist[x] = that best dist + 1, and make from[x] = the index of that best box.

You'll also need an 'index' value for each box, and set it as you're taking the inputs in. that way when you sort the boxes, their original identifying number is saved.

output the best dist[] that you've calculated, and pathfind backwards from the best box using the from[] array.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
other graph
Solution Description: DP Solution:

Sort all boxes by their smallest dimension (ties broken by further dimensions if necessary). Find the largest increasing subsequence (O(n^2) is fine) where the sequence is "increasing" from i to j if box i fits into box j.

Graph Solution:

Create a directed graph where nodes are boxes, and i points to j if i can contain j. Then do a DFS to find the maximum depth. Put all boxes that don't fit into any other boxes into the stack first.


#104 - Arbitrage

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
floyd warshall
Solution Description: If the problem was to find the most profitable path, then it would be very simple to use Floyd-Warshall, but with the updating line:

a[i][j] = Math.max(a[i][j], a[i][k]*a[k][j])

...but, we need to find the shortest path that yields a 1% profit. I'd recommend using an O(n^4) all-pairs shortest-path algorithm that updates based on path length. Of course, we'll use it for maximum product rather than shortest length. For instace:

a[i][j][s] is the maximum product from i to j in s steps.

for s from 2 to n
for i from 1 to n
for j from 1 to n
for k from 1 to n
--- a[i][j][s] = max(a[i][j][s], a[i][j][s-1]*a[j][k][1])

At the end, find the smallest s (and any i) such that a[i][i][s] > 1.01


#105 - The Skyline Problem

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: The easy part of this problem is getting the proper heights of the skyline at each point. The hard part is 'traversing' your skyline at the end properly.

I used a one dimensional int array, 10000 long, to hold the heights for my skyline at each point in the possible map. Then, as I'm given the buildings, I iterate through the array from left to right (from l to r MINUS ONE <<<--- Important), setting the array value = Math.max(skyline[i], newheight). The minus one will be explained in a second.

The hard part is at the end -> you have to be very careful that you're thinking of the values in the array as such: skyline[0] is the height going from 0 to 1, and not just the height >>at<< 0. Make sure you traverse accordingly. This is so that when you have a building end at 23, and a new one start at 24, you'll be able to distinguish when there's a gap between the two. If you just use the array values to represent heights at those indexes, you will loose the information about the gaps between the buildings and think that the skyline goes straight from the building ending at 23 to the one that starts at 24.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: Keep an array of 20,000 elements (as x <= 10000) where a[i] is maximum height across buildings at x = i/2. If you only have an array of 10,000 elements, you risk missing gaps between two buildings side by side, such as (1,5,3) and (4,5,5).

Just iterate i from 0 to 20,000, printing out i and a[i] whenever a[i] changes.


#106 - Fermat vs. Pythagoras

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: This is a bit of an obscure problem...

Euclid has a formula for uniquely generating Pythagorean triples:

- Pick two positive integers, m and n such that m > n, one of m and n is even, and m and n are coprime
- a = m^2 - n^2
- b = 2mn
- c = m^2 + n^2

(a,b,c) will be a unique triple with a<c, and b<c. You are not guaranteed that a<b, so you may need to swap them (though it doesn't matter in this problem).

For this problem, generate all primitive triples for c <= N. This can be done by going over all pairs (m,n) where m^2 <= N. For each primitive triple, find all the multiples (up to c <= N) and strike off every component of every multiple from an array of booleans (indexed from 1 to N).

Output the number of primitive triples found, and the number of unmarked integers in the array. Remember, you need to mark off numbers for *all* triples, not just primitive ones, but you only *count* primitive triples.


#107 - The Cat in the Hat

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
simulation
Solution Description: You can just try different values of N from 1 upwards, and see which one works. Keep dividing the height by N+1 to make sure that it's a power of N+1 (you can use logarithms too, but you need to be very careful with precision). Then, make sure that that value of N results in the given number of workers.


#108 - Maximum Sum

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: Define a 2-dimensional array where v[i][j] is the sum of the submatrix from (0,0) to (i,j).

- Populate v brute force.
- Run a 4-loop deep nested for loop (x1,y1,x2,y2) where you compute the sum of the submatrix from (0,0) to (i,j) using the values from v.

Both of these steps should run in O(n^4). This is good enough given the small bounds, but there *is* a better solution:

- Populate v using the perviously calculated values of v
- Run a 3-loop deep nested for loop (i,j,k) where you compute the best submatrix between rows i and j (k iterates through columns)

Both of these steps run in O(n^3) when done properly.

You can compute the best subarray in a 1-dimensional array in O(n), and you can compute the best submatrix between rows i and j in the same way.


#109 - SCUD Busters

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
math
Solution Description: This is a really good computational geometry problem as it covers convex hull, finding a point in a convex polygon, and finding the area of a convex polygon.

I use Kingdom objects for simplicity. Each one holds an array of points as per the input, an array of points representing its convex hull, its area, and a boolean marking whether or not it has been hit by a missile.

For each kingdom, find the convex hull, and then find the area of the convex hull. Then for each missile, check its location against all convex hulls. If it lies inside one of them, then mark that kingdom as being hit. At the end, output the sum of the areas of all hit kingdoms. Use the given formula to get the area, as it's very simple.

I like Graham's Scan for finding the convex hull as it's quite intuitive and runs in O(n log n). If you're not quite sure about how it works, try Problem 478 (Points in Figures: Rectangles, Circles, Triangles) to get a feel for using the cross product.

The problem description isn't completely clear on what constitutes "inside", so to clarify, a missile is inside a kingdom even if it lands on an edge or corner (non-strict inequality).


#111 - History Grading

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: I hate this problem. I've always hated this problem. Every time I look at it, it takes me a good half hour to figure out what they REALLY want - and it doesn't help that if you are successfully mislead by the problem description - the sample output is ALMOST IDENTICAL to the correct one!

So: When you get the input, remember that what you are given are the POSITIONS of the numbers (yes, stupid - I know). So:

3 1 2 4 9 5 10 6 8 7
means '1' at position 3, '2' at position 1, ie:
2 3 1 4 6 8 10 9 5 7

The student submissions are given in the same way.

Aside from the annoying input, the rest is just the lowest common subsequence DP. See our solution to problem #10405 for a full description and breakdown of the algorithm.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a simple Longest Common Subsequence problem that is hidden by a bit of tricky wording.

The part to be careful about is understanding that the given sequences represent where each event belongs. They are not lists of events. That means that this input...

10
3 1 2 4 9 5 10 6 8 7
4 7 2 3 10 6 9 1 5 8

...should be interpreted as follows:

The correct order of events is:

2 3 1 4 6 8 10 9 5 7

(the 1st event is 3rd, the 2nd event is 1st, etc.)

And the student has given the events in this order:

8 3 4 1 9 6 2 10 7 5

*These* are the sequences that LCS must be preformed upon. In this case, 5 is the answer. (3 1 6 10 7) is one possibility.

Note: The sample output given in the PDF file is wrong. Use the output in the problem description.


#112 - Tree Summing

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
strings
Solution Description: I don't see how you can do this in Java. I tested just reading the input with a Buffered Reader, and not doing anything else, and it TLE'D on me.

My solution -> which works for the sample input, is... well the whole problem is parsing. As you're parsing the tree, set each node to have an accumulated value, which is equal to the accumulated value of its parent plus its own value.

When you reach a child node, check to see if its accumulated value is equal to the n you're looking for. Set you boolean accordingly.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
recursion
sorting
strings
Solution Description: The only really tricky part about this problem is parsing the input. After that, it's fairly simple to get the sum of every root-to-leaf path.

Use a stack to keep track of your current path. Whenever you reach a number in the string, push it onto the stack and add its value to a running sum. Whenever you reach the end of a node, pop it off the stack and detract its value from the running sum. If it was a leaf, then add the sum to a list of root-to-leaf sums before detracting its value. At the end, just check if the given value is in your list of sums.

You can use recursion instead of a stack if you wish, but I think the stack's easier.

Note that there may be negative numbers, both as the sum you're searching for, and as the nodes in the tree.

While this problem used to TLE in Java just by reading in the input, it appears that the judge data has changed, so it's now quite possible to use Java to solve this problem. I'd still suggest using BufferedReader.


#113 - Power of Cryptography

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:searching
Solution Description: This is a fun easy one to do.

Given n and p, you want to find K such that K^n = p. N <= 10^9

Do a binary search, with lower bound 0, high bound 10^9, and binary search for K that satisfies the equation. You'll need a BigInteger to hold p, and another to do comparisons.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: If k^n = p, then k = 10^((log p) / n).

Take p in as a double, do the calculation, and round at the end as the answer may be slightly off after about 7 decimal places. Make sure not to do a straight-up int cast, as sometimes you need to round up and the cast will round down.


#114 - Simulation Wizardry

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Wow, annoyingly vague problem description. Just code out the simulation as you normally would - it's almost exactly what it appears to be. Just keep in mind:

In ADDITION to loosing life from walls and bumpers, you loose ONE life for the 'move' FIRST (before you do anything concerning the bumper or wall... so check your life is still > 0)

The outer layer of the grid is wall, so... if the grid is 4 x 3, the moving space is actually 2 x 1

Aside from that the rest is straightforward. You can do some nice efficient coding by having two arrays, one val and one cost (so no OOP), and working off of those... (DIR = DIR + 3) %4 to turn clockwise

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Just a simulation problem, but the problem description is a little bit funny. It says that you lose life when you move a grid space, but as it turns out, you also lose life when you hit a wall or bumper, even if the wall or bumper has no cost. This isn't explicitly stated. So to be safe, just decrease your life by 1 every iteration regardless of what happens.

Something else very important: When your life is 0, you cannot get points from bumpers, even if you hit them. This means that you also cannot get life back from negative-cost bumpers.


#115 - Climbing Trees

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: I'd recommend using a hash table that maps names to Node objects, though it isn't necessary as the bounds are quite small.

For each query pair, get a list of ancestors for each person. First, see if either person shows up in the other's ancestor list. If so, you have a child-parent relationship (possibly with a few greats tacked on). If not, look for the least common ancestor between the two lists. If one exists, you have a cousin (or sibling) relationship.

If neither case holds, then there is no relation.


#116 - Unidirectional TSP

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:dynamic programming
Solution Description: Create two arrays in addition to the input array. One is the DP array, and one is the path array. dp[i][j] = in[i][j] + min(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]). Make sure that you wrap around the top and bottom of the matrix (use modulo, or just an if statement).

For the path, you must keep an array of strings (or whatever you like) to hold the current path to that point. Prefer lexicographically shorter paths when two DP cells have the same value. Note that lexicographically shorter in this problem means that you minimize the row number, and not the ASCII value of the string. For example:

1 10 10 10
1 2 3 4

In ASCII terms, and normal string comparison terms, the first string is lexicographically earlier. But in this problem, they want the latter.

Use BufferedReader in Java, as there's lots of input.


#117 - The Postal Worker Rings Once

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dijkstra
floyd warshall
other graph
Solution Description: This is a fun one to do, but you need a little first year univ. graph theory to do it.

since you're either looking for an euler path or an euler cycle variation, the result is:

(two odd degree vertices -> output sum of edges + shortest path between the odd vertices)
or
(no odd degree vertices -> output sum of edges)

Use dijkstra or warshall to find the shortest path should you need it.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
other graph
Solution Description: The problem guarantees that you have a connected graph where no more than two vertices have odd degree. This means that there's an Euler path, and possibly a cycle. If you know that you have an Euler cycle, then the distance to travel across every road (edge) is just the sum of all of the edges.

If you only have an Euler path, and not an Euler cycle, then the shortest path is to travel from one odd node to the other, traversing every edge, and then taking the shortest path back to the beginning. So take the sum of all of the edges, then run Floyd-Warshall to find the shortest path back to the start, and add that to your sum.


#118 - Mutant Flatworld Explorers

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Straight simulation. You'll need a wxh array to hold a 1 if a robot died from there, and a 0 if a robot hasn't so far.

If you go off the edge and the last square you were in had a 1, you are allowed to 'backtrack' onto the grid. If it had a 0, mark it as 1 and output that you're lost.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Use a two-dimensional array to hold the robot scents, and then just simulate the problem. Notice that a scent works regardless of which direction the robot fell off. So if one robot drops off the map from (0,0) to (0,-1), another robot that attempts to fall off from (0,0) to (-1,0) will not fall off.


#119 - Greedy Gift Givers

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:greedy
Solution Description: Just use some Object Oriented programming... one person class solves all your problems:

class person
-----int ratio
-----int money
-----string name

make an array of them, and take all the information in. When it comes time to take a person's (a) friends in, just loop through your list of people (p) and:

person(a).ratio -= person(a).money/friends(a)
person(p).ratio += person(a).money/friends(a)

go through the people array once more, outputting the ratio and their name.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Make an array of people objects that each hold their name, their starting and ending money, and their friends. Then just do the simulation, making sure that you transfer only an integer amount. Just use integer division, and the remainder will be left behind naturally.


#120 - Stacks of Flapjacks

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
strings
Solution Description: find the largest pancake that is not in it's correct position.

flip it to the top of the stack (so, flip from its current position)

flip from where it's supposed to be (to put it there)

loop while not finished

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: Essentially a sorting problem with a unique algorithm. After every iteration, you should have one more pancake sorted.

- At iteration i, find the ith largest pancake (this will be the largest pancake in the unsorted section from 0 to length-i-1)
- If it isn't at the top of the stack, flip it to the top
- Then flip the pancake into it's proper location (on top of the previously sorted pancakes)


#121 - Pipe Fitters

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: All math.

You have to check when the box is a x b, and b x a, and take the maximum of the pipes fitted in each of those rotations.

You have to do some Pythagoras to get the height difference when adding a new layer of pipes to the box. With this, you can multiply by the width and depending on whether a - (int)a < 0.5 or is >= 0.5, get a number of pipes fitted.

Rotate and repeat.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The maximum grid packing is just (int)a * (int)b. The skew packing is a little trickier, but nothing beyond Pythagoras. If the width ends in .5 or greater, then the grid pattern has the same number of pipes in each row. Otherwise, every other row has one pipe less. The number of rows is equal to (b-1) / sqrt(3/4) + 1.

Make sure that you calculate the skew pattern twice. once for a-by-b, and once for b-by-a. Don't forget to handle the case where a or b < 1.


#122 - Trees on the level

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
Solution Description: Make the tree out of a linked list. Each node should hold its value, and a pointer to each of its children.

For each node in the input, traverse the given path from the root, and modify that node's value. If you encounter a dead end, put a new node in with value -1. For instance, with the given input:

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

At the beginning, you have no nodes. When you encounter (11,LL), create a root with value -1, give it a left child with value -1, and give that left child a left child with value 11. When you encounter (7,LLL), traverse down to to the node that you just put 11 in, and give it a left child with value 7.

While you're building the tree, if you are asked to put a value into a node that doesn't have -1, then the tree is not complete.

Once you've built the tree, use a queue to do the level-order traversal (which is basically a BFS). If you encounter a node that has a -1 in it, then the tree is not complete. Otherwise, output the level-order traversal.


#123 - Searching Quickly

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
sorting
strings
Solution Description: Go through all of the titles once to collect all of the non-ignored words. Then, go through the titles a second time, capitalizing as necessary.

Make sure that you capitalize a word only if you come across the word by itself, and not as merely a substring. So for example:

the
::
dog
dogcatcher

You should return:

DOG
DOGCATCHER

and not:

DOG
DOGcatcher
DOGCATCHER


#124 - Following Orders

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
recursion
Solution Description: This problem boils down to printing out every possible topological sorting of a directed acyclic graph. I would suggest doing this recursively:

Have an array where a[i] is true if the letter i hasn't been used yet, and let b[j][i] be true if j < i.

At each recursive step, find (in lexicographic order) an i such that a[i] is true, and there is no j such that b[j][i] and a[j] are both true. Append i to a string, mark a[i] as false, recurse on the remaining array, and then mark a[i] as true again.

When a[i] is false for all i, output the current string.


#127 - "Accordian" Patience

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Create an ArrayList of Stacks. You can easily manipulate this data structure as per the specifications of the problem to simulate.

To make things go faster, when you perform a move from i to i-1, or from i to i-3, don't go back to the very beginning. Just go back i-1 or i-3 (as is suitable). Just make sure you don't go to -1, and make sure that you decrement to i-4 or i-2, since when the loop resumes it will add one.

TLE's in Java

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Make an array of strings, 52x52, and use it to simulate the card game. The general feel of this problem is quite similar to Problem 101 (The Blocks Problem).

At first, set a[i][0] to the ith card. Then, keep running through the array from left to right looking for a valid move. Whenever you find one, go back to the beginning and go again.

As far as I can tell, this problem is impossible to do in Java because of the sheer input size, even if you use BufferedReader. I got AC at Peking University's judge site in less than 0.200s with Scanner, though, so try their site out to see if you've got it correct. Looking at the forums, this problem is hard to do in time even for C++ users.


#128 - Software CRC

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Solvable in Java, you have to use a BufferedReader to take the input, and mod as you go.

There is so much sample data, that you cannot afford to do some of the normal java functions like string addition, etc... practically, for any ACM problem, this is not a normal issue.

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The basic idea is to convert the ASCII string into a numerical value, and determine how much you would need to add to make it divisible by 34943. Obviously the bounds are far too large for any basic datatype (~2^8192), so you'll need to use modular arithmetic as you calculate the value to keep it manageable.

Keep a running sum that starts at 0. For each character, shift the sum left 8 bits (multiply by 256), add the ASCII value of the current character, and take mod 34943. At the end, shift over 16 bits (to leave room for the 2-byte CRC), and mod 34943 again. Now we need to choose a CRC that makes our current sum divide evenly by 34943. So, the answer is (34943 - current sum) % 34943. The extra mod operator is there in case the current sum is 0. Return this number in hexadecimal.


#130 - Roman Roulette

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
simulation
Solution Description: This problem isn't too tricky, but it's easy to make mistakes. A dynamic array works well, though you can use a normal array too.

A handy formula: If X is the number of the person that survives when i = 1, then the safe location is N-X+2. The exception is that if X is 1, then the safe location is of course 1.


#133 - The Dole Queue

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep an array of n booleans, where a[i] is true once person i has been sent off.

Keep two pointers, one starting at 1 and one starting at N. These are the two people that walk aroud the circle. At each step, make the first person go k%r to the right, and the second person go m%r to the left, where r is the number of people remaining. Obviously, skip over any people who've already been sent off.

You may find it handy to move r rather than 0 if k % r == 0. Otherwise, your pointer will be stuck on an eliminated person and you'll have to code a special case for k % r == 0.

And of course, make sure you get your spacing right. Every number is right-justified in a field of size 3.


#136 - Ugly Numbers

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: It took me a good while to get this solution, since I couldn't really see why every ugly number can be generated by multiplying a previous ugly number by 2, 3, or 5.

Make an array that will hold your ugly numbers. Array[0] = 1, and we want element 1499.

Fill the rest of the Array with Integer.MAX_VALUE, and iterate up throught it. For each element, iterate up through all the previous numbers, and find the smallest number (gained by multiplying any of the ugly numbers by 2, 3, or 5) that's larger than the last ugly number you generated. Add that number to the array at the current element and continue.

I want to rate this problem as easy-medium, but I can tell from UVa's statistics that I should probably round down on that verdict...

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: Seeing as how there's no real time limit on this problem save your own patience, you can brute force the answer if you wish. The answer is less than 100 million, so you can generate the first 100 million primes and then go about brute forcing all numbers. This will take a couple hours though I believe, judging by how slowly it starts going.

Here's a more efficient solution:

If we factor out all the 2's, 3's, and 5's from a given number, then what's left over must decompose into all the other prime factors of that number. If we get a 1 left over, then 2, 3, and 5 must be the only prime factors. So:

while(num % 2 = 0)
---num /= 2
while(num % 3 = 0)
---num /= 3
while(num % 5 = 0)
---num /= 5

if(num = 1)
---Found one!

This solution runs in under a minute.


#138 - Street Numbers

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This wasn't too bad - but UVa was more annoying.

Count up from one, keeping track of the sum from 1 to where you are currently. Then, when you're counting (and are at number n, let's say), count upwards from n until the sum going up is no longer smaller than your running sum.

Once this loop breaks, if they're equal, you've found a new pair.

The even nicer way to do this, is to also keep a 'sum of above' variable. Each time you visit a new n, you minus the n you're at and start counting up with the same conditions - that way you're not doing this:

(5) - sum below is 10 -> 6 + 7 is...
(6) - sum below is 15 -> 7 + 8 is...

you can just keep a sum of what's above you to a certain range, and take away your current (n) from it each iteration so that you're still counting >>above<< you.

Oh yes, and annoyingly enough, this last solution runs in less than 1 second on my home computer, but TLE's on UVa's judge. So... catch the output, and just regurgitate it for the submission.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Iterate through all house numbers i until you find 10 solutions. You need to keep track of three values: The sum of all houses less than i ("undersum"), the sum of all houses greater than i until such time that it exceeds undersum ("oversum") and the house number that caused oversum to exceed undersum ("last").

At the ith iteration, add (i-1) to undersum, and then if oversum is now less than undersum, add numbers to oversum starting with (last+1). Keep updating last whenever necesssary. In this way, you can run through the houses in O(n).


#140 - Bandwidth

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: With only 8 characters, you can try all 8! permutations of the ordering. Just get all the permutations lexicographically and return the minimum bandwidth across each one.

The input format leaves something to be desired, but if you pass the sample case, your input parser should be fine.


#144 - Student Grants

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Just simulate the process using a queue of objects that hold a student number and an amount of money remaining.

At each iteration, take the first student from the queue and subtract from their money and from the store the minimum of how much they need and how much the store has. If the store has 0 money, increase the limit and put that much money in the store (wrapping around to 1 when the limit exceeds k). If the student requires more money, put him at the back of the queue.


#145 - Gondwanaland Telecom

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
simulation
Solution Description: This problem isn't too hard, just make sure that your spacing is correct, and that you handle boundary cases.

For instance, a call that goes from 13:45 - 13:45 is a 24-hour call, not a 0-hour call. Also, try things like 23:59 - 00:00.


#146 - ID Codes

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: This is a fun solution. I totally did this without knowing dijkstra's algorithm for this. I call it -> PETER'S Algorithm

Loop back from the right (a)
Loop back from the right (b)
if a > b
swap a and b
sort from position(a)+1 up
break
output result

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: This problem uses one of Dijkstra's less known algorithms:

Given an array of objects a[] that represents a permutation, the next permutation can be found as follows:

- Let i be the greatest index where a[i] < a[i+1]
- Let j be the greatest index where a[j] > a[i]
- Swap a[i] and a[j]
- Reverse all elements from i+1 to the end of the array*

*for example, if the array is 8 items long, and i = 3, then swap a[4] and a[7], and swap a[5] and a[6].


#147 - Dollars

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a coin change DP problem. See my solution for Problem 357 (Let Me Count The Ways) for the recurrence.

See Also:
Problem 357 (Let Me Count The Ways)
Problem 674 (Coin Change)
Problem 11137 (Ingenuous Cubrency)


#151 - Power Crisis

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
simulation
Solution Description: Pretty straightforward. Just brute force your value for m, by starting at m = 1 and increasing m by 1 every time the sequence fails to end at 13 (or 12, if you're zero indexed).

Just be careful not to get sloppy, and 'move' from power station at index+tr % n all at once without checking to make sure that stations within that distance haven't already been powered off.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
simulation
Solution Description: Start with m = 1 and simulate the process. If you eliminate 13 before getting to the end, increment m and try again. I use an array of booleans to keep track of which cities have been powered off. You could use a dynamic array as well, but it'll be a little bit slower as you'll need to remake it every time you increment m.


#153 - Permalex

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:recursion
strings
Solution Description: Obviously it will be too slow to generate every permutation until you hit the given one, as you may have to go through 2^31 permutations.

So instead, we'll try to find the number of permutations less than the given one.

Example: bacaa

Now, any string that starts with a letter less then 'b' will come before "bacaa". So for all letters less than 'b', how many permutations start with that letter? In this case, we only check strings starting with 'a', in which case we get 4! / 2! = 12 possible arrangements of "aabc".

Now, we check strings that start with the given character, but come earlier in the sequence. That is, strings that begin with 'b', but come before "bacaa". So, we recursively call our function on "acaa" and eventually it returns 2.

Knowing that 14 strings come before "bacaa", this one must be in the 15th place.


#154 - Recycling

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: For each city, iterate through every other city, and count the number of differences. So, keep a counter, and if city[i]'s red bin != city[j]'s red bin, add one to the count.

Output the city with the fewest differences.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Make an array of chars [100][5] where a[i][0] is the color of the plastic bin, a[i][1] is the color of the glass bin, and so on. Then compare each city brute force against all other cities, and return the most optimal one.


#155 - All Squares

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
recursion
Solution Description: Let (x,y) be the given point. Let cx and cy be the center of the current square, initially 1024 and 1024.

While k > 1:

- If (x,y) is inside the current square, increment a running total.
- If (x,y) is up and to the right of (cx,cy), then (cx,cy) <- (x+k, y+k)
- If (x,y) is up and to the left of (cx,cy), then (cx,cy) <- (x-k, y+k)
- If (x,y) is down and to the right of (cx,cy), then (cx,cy) <- (x+k, y-k)
- If (x,y) is down and to the left of (cx,cy), then (cx,cy) <- (x-k, y-k)
- Divide k by 2

Output the running total at the end.

While it's not stated explicitly in the problem description, a point is inside a square even if it lies on the edge.


#156 - Ananagrams

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: Create a function check(a, b) that takes two strings and determines if they're anagrams.

then, for each word a
for each word b
if(a and b aren't the same && check(a, b))
mark as anagram in some array

for each word c
if not marked as anagram output

just make sure you're outputting in alphabetical order. I had two arrays that held the words - one was an arraylist I sorted at the end.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: Just brute force all combinations of strings. If for a given string, none of the others "matches", then add it to a list of output.

The "match" function between two strings is:

- Translate both strings to lower case.
- Keep an array of 26 numbers for each string, where a[i] is the number of times that the letter i appears in the first string (b[i] for the second string).
- Iterate through both strings, counting the number of letters.
- Iterate through the arrays, comparing a[i] to b[i].
- If a[i] = b[i] for all i, the strings "match" (are anagrams of each other), otherwise they don't.

At the end, sort the list of output, and then print it.


#160 - Factors and Factorials

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: You don't need to calculate the factorials for this one.

You know that since 100! (for example) is 2x3x4x5x6x....x99x100, you can just total the number of times each prime occurs for each of those numbers from 2-100, and then when you get a factorial just sum up your results. Example:

6! - 2x3x4x5x6
I know that 2 contains 2 - 1 time
I know that 3 contains 3 - 1 time
I know that 4 contains 2 - 2 times
I know that 5 contains 5 - 1 time
I know that 6 contains 2 - 1 time
3 - 1 time

Sum them up:

6! contains 4 two's, 2 three's, and 1 five.

This does entail making a two dimensional array for counting (so count[2][3] would be the number of times that the number 2 contains the 3rd (or 4th if you're zero indexed) prime numer), which might be a >>little<< tricky to work with. You'll also need a prime sieve and a string buffer for the formatting.

I'd rate the coding difficulty for this as high easy as well.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: First, generate all of the prime numbers up to 100.

Notice that every successive factorial has all the factors of the previous one as it's a multiple of the previous one.

For each number from 2 to 100, keep track of how many of each prime factor it has. Start with 2! having just one 2. Now iterate i from 3 to 100, and build the rest of the array. Copy all the factors from (i-1)!, and then add all the factors of i.

Now for every input n, just output the number of each factor that appears in the list. Put a newline before printing the number of 53's. Even at 100!, you won't need more than 2 lines to do the output.


#161 - Traffic Lights

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: With the small bound of 5 hours (18,000 seconds), just simulate the waiting process. Every second, see if all of the lights are green at the same time.

Let n be the waiting time for a light. If (t % 2n) < (n-5), then the light is green at time t.


#167 - The Sultan's Successors

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
recursion
Solution Description: The 8 Queens problem can be solved very efficiently by backtracking. Write a recursive function that places a queen in the next available column, and backtracks when 8 queens have been placed, or no spot is unthreatened in that column.

Take the maximum value across all possible solutions.


#170 - Clock Patience

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
simulation
Solution Description: Simulate the card game, using stacks for the piles of cards. The main things to watch out for are that the deck is presented to you from the bottom up, and that you must print a leading 0 if less than 10 cards are revealed.


#190 - Circle Through Three Points

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: Read my solution for Problem 438 (The Circumference of the Circle) to get the core of the problem.

Once you have the center of the circle (h,k) and the radius r from the previous step, you can calculate c, d, and e as follows (simple expanding and regrouping):

c = -2h
d = -2k
e = h^2 + k^2 - r^2

Make sure that you pay attention to the output formatting. Any time you would print a double negative, you must make it positive. Also, I believe that zeroes should always be printed with positive signs. Watch out for negative zero in your output. It comes in Java; I'm not sure about C++.


#191 - Intersection

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: There are quite a few ways of doing this problem, but I find the following to be the easiest to code:

First, check whether or not either of the inputs lies inside the rectangle. If so, output "T".

Next, calculate the cross product of the line segment with each corner of the rectangle. If the sign of each cross product is the same (i.e. all positive or all negative) then output "F", as the rectangle is entirely on one side of the line.

If you reach this point, then we know that the line that the line segment desribes goes through the rectangle, but we need to determine if just the line segment does. Determine the shadow of the rectangle and the line segment against the X and Y-axes. If the shadows overlap on both axes, output "T". Otherwise, output "F".


#195 - Anagram

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:sorting
strings
Solution Description: This is a slightly harder version of Problem 10098, on the grounds that the problem goes against the natural ordering of characters. Instead of ordering them as ABC...YZabc...yz, they want AaBbCc...YyZz, so you'll need to write a new comparator, or even your own sort function. I did selection sort and it ran in time.

Use Dijkstra's permutation algorithm to get all of the permutations "alphabetically" with no repetitions.





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