More Math Practice Problems

1 Introduction

The way to learn how to solve problems is to practice. Here are a few problems, including
the entire February 2003 contest!

2 The Algorithm

Some things in life change, but not good contest strategy. First, and most importantly, read
the problem. Make sure you understand it thoroughly, and note the limits. As you think
about an algorithm, think about three things: run time, memory usage, and coding time.
There is a working solution; if your solution doesn’t quite work in time, keep looking! While
an incorrect solution may get significant partial credit, you really rack up points when you
get a full solution, since those last three cases might be worth a third or half of the problem.

3 The Problems

1. (Dwarve’s Casino, UMD 2004 (sort of)) Farmer John wants to gamble with the cows.
But since the cows don’t have opposable thumbs, they can’t do much. So they agreed
that Farmer John will bet some integer amount of money, and the cows will tell him if
he wins or loses. However, out of the N rounds played the cows can only
make FJ lose L times Help FJ maximize his winnings given his initial
amount of money D

2. (Prisoner, USACO sometime) Bessie has been a bad cow, and FJ wants to put her in
as secure a prison as possible. A prison consists of a set of concentric nonintersecting
closed loops of fences around Bessie, and its security is defined by the number of fences
enclosing her. However, FJ only has a fixed set of N posts that he
can build fences between. Given Bessie’s position and these posts, find the maximum
security prison FJ can build around Bessie.

3. (Cow Math USACO Feb 2003)
Taking their cue from the builders of the USA’s Interstate Highway system, the cows
have introduced the Interpasture Path numbering system. They have already numbered
the N (2 ¡= N ¡= 25) pastures with the integers 1..N and now are numbering
each path between two pastures with its own distinct Interpasture Path number in the
range 1..2000 (e.g., I-9 and I-16).

In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are
connected by Interpasture Paths I-3, I-6, I-9, and I-16:

Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system.
During each walk, she never visits the same pasture twice, so possible walks on the
sample map above are 1-4-2 and 1-3-2.

Over the years, Bessie has developed an amazing mathematical skill that she likes to
exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the
Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches
I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into
16 and 6 but no larger integer does).

As she walks the pastures day after day, she takes all the possible routes from pasture
1 to pasture 2 and remembers each of the GCFs. After she has taken every possible
walk once, she computes the least common multiple (LCM) of all the GCFs. For this
example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the
LCM is 6.

For large networks of paths, Bessie might get tired of all the walking, but she really
wants to know the LCM for every map. Calculate that number for her.

4. (Cow Imposters, USACO Feb 2003)
FJ no longer uses the barbaric custom of branding to mark the cows that he owns.
Instead, he creates a binary code of B (1 ¡= B ¡= 16) bits for each cow and embosses
it onto a metal strip that is fastened to each cow’s ear.

The cows have taken in a stray and wish to create an ID strip for it. Unknown to FJ,
they have created a machine that can make a new ID strip by combining two existing
ID strips using the XOR operation (ID strips are not consumed by this machine, and
the same ID strip can be used for both inputs).

The cows wish to create a specific ID strip for the stray or at least get as close to a
desired ID as possible – with the smallest possible number of bits differing between the
goal ID strip and the best possible new ID strip.

Given a set of E (1 ¡= E ¡= 100) existing ID strips, the goal ID strip, and a large
number of blank ID strips to hold intermediate results, calculate the closest possible
ID strip that can be created from the existing ID strips.

If more than one ID is closest, choose the one that can be created in the fewest steps.
If there is still a tie, choose the ‘smallest’ ID (i.e., if you sorted all the IDs, the one
that is first).

5. (Traffic Lights, USACO Feb 2003)
The cows are going downtown! Just like everyone else, they want to optimize their
driving time.

They have noted that when driving on a straight road with traffic lights, the best
strategy to get to their destination as quickly as possible is not necessarily to drive
as fast as possible to the next traffic light, brake if it’s red, wait for a green light,
accelerate, and then drive on. It is often better to approach a traffic light more slowly
in order to have some speed when the light turns green.

The cows have observed the traffic lights for a very long time. They know that each
traffic light behaves in the following way: * it is green for a certain amount of time Tg,
* then it is red for an amount of time Tr, * then green again, * and so on.

Given * the integer length of the road L (1 ¡= L ¡= 100) * the number of traffic lights
N (0 ¡= N ¡= L+1) along with information about each light: * the unique position (0
¡= position ¡= L) * Tg (1 ¡= Tg ¡= 10) * Tr (1 ¡= Tr ¡= 10) * color at t=0 (R or G)
* Tc (the integer amount of time since the light last changed)

write a program to determine the minimal amount of time needed to get to the end of
the road. Note that at each discrete time (starting at t=0), a car may either change
its speed (expressed in positional units per time unit) by one or keep it constant. The
speed is always 0 or positive, of course. No driving backwards!

The car starts at position zero has has speed zero. The car must complete its trip at
position L, also with speed zero. The car must stop at all lights that are red when
encountered – be sure its speed is 0 at the red light’s position if it encounters a red
light. The car may move when the light changes from red to green, but not when it
changes from green to red.

6. (Farm Tour, USACO Feb 2003)
When FJ’s friends visit him on the farm, he likes to show them around. His farm
comprises N (1 ¡= N ¡= 1000) fields numbered 1..N, the first of which contains his
house and the Nth of which contains the big barn. A total M (1 ¡= M ¡= 10000) paths
that connect the fields in various ways. Each path connects two different fields and
has a nonzero length smaller than 35,000.

To show off his farm in the best way, he walks a tour that starts at his house, potentially
travels through some fields, and ends at the barn. Later, he returns (potentially
through some fields) back to his house again.

He wants his tour to be as short as possible, however he doesn’t want to walk on any
given path more than once. Calculate the shortest tour possible. FJ is sure that some
tour exists for any given farm.