Usaco Hol10

The special holiday bonus contest for the 2009-2010 competition year of USACO.

**********************************************************************
GOLD PROBLEMS
**********************************************************************
Four problems numbered 1 through 4
**********************************************************************

Problem 1: Cow Politics [Andre Kessler, 2009]

Farmer John's cows are living on N (2 <= N <= 200,000) different
pastures conveniently numbered 1..N. Exactly N-1 bidirectional cow
paths (of unit length) connect these pastures in various ways, and
each pasture is reachable from any other cow pasture by traversing
one or more of these paths (thus, the pastures and paths form a
graph called a tree).

The input for a particular set of pastures will specify the parent
node P_i (0 <= P_i <= N) for each pasture. The root node will specify
parent P_i == 0, which means it has no parent.

The cows have organized K (1 <= K <= N/2) different political parties
conveniently numbered 1..K. Each cow identifies with a single
political party; cow i identifies with political party A_i (1 <=
A_i <= K). Each political party includes at least two cows.

The political parties are feuding and would like to know how much
'range' each party covers. The range of a party is the largest
distance between any two cows within that party (over cow paths).

For example, suppose political party 1 consists of cows 1, 3, and
6, political party 2 consists of cows 2, 4, and 5, and the pastures
are connected as follows (party 1 members are marked as -n-):

-3-
|
-1-
/ | \
2  4  5
|
-6-

The greatest distance between any two pastures of political party
1 is 3 (between cows 3 and 6), and the greatest distance for political
party 2 is 2 (between cows 2 and 4, between cows 4 and 5, and between
cows 5 and 2).

Help the cows determine party ranges.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 64MB

PROBLEM NAME: cowpol

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
and P_i

SAMPLE INPUT (file cowpol.in):

6 2
1 3
2 1
1 0
2 1
2 1
1 5

OUTPUT FORMAT:

* Lines 1..K: Line i contains a single integer that is the range of
party i.

SAMPLE OUTPUT (file cowpol.out):

3
2

**********************************************************************

Problem 2: Rocks and Trees [Long Fan, 2007]

My country's bigger than most
'Cause I'm really proud
So I shout it loud
Though our numbers are few
We will welcome you

Although we don't have history
Gold medal winning teams
Heroes or prisoners
World famous volcanoes
Still what we've got's glorious

'Cause we've got
Rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And water

After moving across the 49th parallel to Canada, the land of rocks
and trees, Farmer John's cows invented a game to spend their leisure
time on the pasture; naturally, it involved the rocks and trees!
Cowboy Ted likes this game very much, but so poor is his luck that
he always loses to other cows. This time, he is going to seek your
help.

The game's rules are simple. It is played with a tree that has both
N (2 <= N <= 10,000) nodes conveniently numbered 1..N and also N-1
branches. Node 1 is the root of this tree; except for node 1, node
i has parent P_i (1 <= P_i < i). Initially, Each node contains some
rocks (except the root node, which has no rocks). In particular,
non-root node i has exactly R_i (1 <= R_i <= 1,000) rocks at the
beginning of the game.

Two players alternate turns to play this game in turn, with Ted
going first. In each turn, the current player can choose a non-root
node i and move at most L (1 <= L <= 1,000) rocks from this node
one branch closer to the root (i.e., move these rocks to the parent
node). He must move at least one rock, and, of course, he cannot
exceed the current number of rocks on this node. The game ends when
a player can't make a legal move (i.e., when all the rocks are on node 1);
that player loses.

Ted needs your help. He has given you the initial configuration of
the game, and he will then make T (1 <= T <= 10,000) changes to the
step, if he can win the game beginning from this configuration,
assuming both he and his opponent use the best possible strategy.

Ted's changes are specified as two integers A_j (1 < A_j <= N) and
B_j (1 <= B_j <= 1,000), meaning that Ted will change the number
of rocks on node A_j to B_j (this is a 'set' not a 'subtract' or
'add'), and will then ask you whether he can win. Changes accumulate;
node A_j's rocks stay at B_j until another change for A_j appears.

Consider this example with three nodes numbered as shown and the
shape shown in Board 0.

Initially, there are 5 rocks on node 2 and 3 rocks on node 3; see
Board 1.

For the first change, Ted removes 2 rocks from node 2 (thus leaving
3); see Board 2.  For the second change, Ted removes 2 rocks from
node 3 (thus leaving 1).  Note that node 2 still has 3 rocks; see
Board 3.

1            -         -         -
/ \          / \       / \       / \
2   3        5   3     3   3     3   1

Board 0      Board 1   Board 2   Board 3

Your program should determine in each case who wins.

For about 30% of the test cases, N <= 10, and T <= 100, and no tree
node will have more than 5 rocks on it after any of Ted's changes.

Partial feedback will be provided for your first 50 submissions.

PROBLEM NAME: rocks

INPUT FORMAT:

* Line 1: Three space-separated integers: N, T, and L

* Lines 2..N: Line i contains two space-separted integers: P_i and R_i

* Lines N+1..N+T: Line j+N describes Ted's next change using two
space-separated integers: A_j and B_j

SAMPLE INPUT (file rocks.in):

3 2 10
1 5
1 3
2 3
3 1

OUTPUT FORMAT:

* Lines 1..T: Line i contains "Yes" if Ted can win the game after
change i; and "No" otherwise.

SAMPLE OUTPUT (file rocks.out):

No
Yes

**********************************************************************

Problem 3: Driving Out the Piggies [Brian Hamrick, 2009]

The Cows have constructed a randomized stink bomb for the purpose
of driving away the Piggies. The Piggy civilization consists of N
(2 <= N <= 300) Piggy cities conveniently numbered 1..N connected
by M (1 <= M <= 44,850) bidirectional roads specified by their
distinct endpoints A_j and B_j (1 <= A_j <= N; 1 <= B_j <= N).
Piggy city 1 is always connected to at least one other city.

The stink bomb is deployed in Piggy city 1. Each hour (including
the first one), it has a P/Q (1 <= P <= 1,000,000; 1 <= Q <=
1,000,000; P <= Q) chance of polluting the city it occupies. If it
does not go off, it chooses a random road out of the city and follows
it until it reaches a new city.  All roads out of a city are equally
likely to be chosen.

Because of the random nature of the stink bomb, the Cows are wondering
which cities are most likely to be polluted. Given a map of the
Piggy civilization and the probability that the stink bomb detonates
in a given hour, compute for each city the probability that it will
be polluted.

For example, suppose that the Piggie civilization consists of two
cities connected together and that the stink bomb, which starts in
city 1, has a probability of 1/2 of detonating each time it enters
a city:

1--2

We have the following possible paths for the stink bomb (where the last
entry is the ending city):

1: 1
2: 1-2
3: 1-2-1
4: 1-2-1-2
5: 1-2-1-2-1
etc.

To find the probability that the stink bomb ends at city 1, we can
add up the probabilities of taking the 1st, 3rd, 5th, ... paths
above (specifically, every odd-numbered path in the above list).
The probability of taking path number k is exactly (1/2)^k - the
bomb must not remain in its city for k - 1 turns (each time with a
probability of 1 - 1/2 = 1/2) and then land in the last city
(probability 1/2).

So our probability of ending in city 1 is represented by the sum
1/2 + (1/2)^3 + (1/2)^5 + ... . When we sum these terms infinitely,
we will end up with exactly 2/3 as our probability, approximately
0.666666667. This means the probability of landing in city 2 is
1/3, approximately 0.333333333.

Partial feedback will be provided for your first 50 submissions.

PROBLEM NAME: dotp

INPUT FORMAT:

* Line 1: Four space separated integers: N, M, P, and Q

* Lines 2..M+1: Line i+1 describes a road with two space separated
integers: A_j and B_j

SAMPLE INPUT (file dotp.in):

2 1 1 2
1 2

OUTPUT FORMAT:

* Lines 1..N: On line i, print the probability that city i will be
destroyed as a floating point number. An answer with an
absolute error of at most 10^-6 will be accepted (note that
you should output at least 6 decimal places for this to take
effect).

SAMPLE OUTPUT (file dotp.out):

0.666666667
0.333333333

**********************************************************************

Problem 4: Cow War [Michael Cohen, 2009]

Farmer John has long had a dispute with neighbor Farmer Tom over a
group of V (1 <= V <= 1,000) pastures conveniently numbered 1..V.
Both farmers currently graze their cows on the pastures; each pasture
might be empty or might have a single cow which is owned by either
Farmer John or Farmer Tom.

Farmer John's patience is at an end, and he wishes to settle the
dispute with Farmer Tom by tipping over Tom's cows. Of course, he
wants to strike first and to tip as many of Farmer Tom's cows as
possible.

A total of E (1 <= E <= 5,000) bidirectional cowpaths connect pairs
of pastures. No two pastures are connected by more than one cowpath;
each path connects exactly two distinct pastures. Paths are described
by their endpoints P1_i and P2_i (1 <= P1_i <= V; 1 <= P2_i <= V).

During his offense, each of Farmer John's cows can traverse a single
cowpath if she wishes. Whether or not she chooses to traverse a
cowpath, she can then (if she wishes) launch a cow tipping attack
to a pasture connected to her pasture by a single cowpath, thus
tipping the enemy cow on that pasture. Note that a cow can move and
then attack -- but she is not able to attack and then move.

Each pasture can hold exactly one cow at a time; no cow can move to
a pasture occupied by another cow, especially if it has been tipped.
Of course, if a pasture is vacated, another cow can later move in
to take its place. A tipped cow cannot be tipped again.

Farmer John wants to know two things:

* How many of Farmer Tom's cows he can tip in the first salvo
of the war

* How to command his cows to move and attack so as to tip
that maximal number of Farmer Tom's cows in that first salvo

Find the maximum number of cows that can be tipped and construct a
sequence of move and attack commands to his cows that then obey the
rules and tip that number of cows. Any such sequence is acceptable,
as long as it tips the maximum number of Farmer Tom's cows.

Consider, for instance, a group of 5 pastures arranged in a line,
with each pasture connected (via '--'; see diagram below) to its
left and right neighbors (if they exist). In other words, there is
a cowpath from Pasture 1 to Pasture 2, Pasture 2 to Pasture 3, etc.
Farmer Tom ('T') has 2 cows, standing on pastures 1 and 4, while
Farmer John ('J') has 2 cows standing on pastures 3 and 5 ('E' means
empty):

1    2    3    4    5
T -- E -- J -- T -- J

In this case, Farmer John can tip both of Farmer Tom's cows by first
moving his cow on Pasture 3 to Pasture 2, so that the pastures in
order are now TJETJ. Farmer John can then have both of his cows
attack to the left.  Note that although the cow in Pasture 3 could
have attacked to the right without moving, the rightmost cow would
then be unable to attack. The only valid solutions thus have the
same move and attacks, although the order in which Farmer John
commands his cows can vary slightly.

If you compute the correct maximum number but do not provide a
sequence (or your sequence is wrong), you will get 50% of the points

Partial feedback will be provided for your first 50 submissions.

PROBLEM NAME: cowwar

INPUT FORMAT:

* Line 1: Two space separated integers: V and E

* Line 2: A string of V characters (no spaces); character #i indicates
whether pasture #i is empty ('E') or has a cow owned by Farmer
John ('J') or Farmer Tom ('T')

* Lines 3..E+2: Line i+2 contains two space separated integers: P1_i
and P2_i

SAMPLE INPUT (file cowwar.in):

5 4
TEJTJ
1 2
2 3
3 4
4 5

OUTPUT FORMAT:

* Line 1: A single integer, the maximum number of enemy cows Farmer
John can have tipped

* Lines 2.....: One of Farmer John's instructions to his cows (to be
executed in the order given):

MOVE A B
or
ATTACK A B

where A is the vertex the cow occupies before taking the action and
B is the vertex it is moving to or attacking, respectively. Note
that when instructing a cow that has already moved to attack, the
instruction specifies the location the cow is currently standing,
not where it was originally.

SAMPLE OUTPUT (file cowwar.out):

2
MOVE 3 2
ATTACK 2 1
ATTACK 5 4

OUTPUT DETAILS:

The other valid outputs are:

2
MOVE 3 2
ATTACK 5 4
ATTACK 2 1

and

2
ATTACK 5 4
MOVE 3 2
ATTACK 2 1

which are just reorderings of the output shown.  This might not be true on
other testdata.

**********************************************************************
page revision: 2, last edited: 10 Jan 2010 03:39