Usaco Dec11 Gold

Part of USACO Dec11

``````**********************************************************************
GOLD PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************

Problem 1: Cow Photography [Brian Dean, 2011]

The cows are in a particularly mischievous mood today!  All Farmer John
wants to do is take a photograph of the cows standing in a line, but they
keep moving right before he has a chance to snap the picture.

Specifically, each of FJ's N (1 <= N <= 20,000) cows has a unique
integer ID number.  FJ wants to take a picture of the cows standing in
a line in a very specific ordering, represented by the contents of an
array A[1...N], where A[j] gives the ID number of the jth cow in the
ordering.  He arranges the cows in this order, but just before he can
press the button on his camera to snap the picture, a group of zero or
more cows (not necessarily a contiguous group) moves to a set of new
positions in the lineup.  More precisely, a group of zero or more cows
steps away from the line, with the remaining cows shifting over to
close the resulting gaps in the lineup.  The cows who stepped away
then re-insert themselves at different positions in the lineup (not
necessarily at the locations they originally occupied).  Frustrated
but not deterred, FJ again arranges his cows according to the ordering
in A, but again, right before he can snap a picture, a different group
of zero or more cows moves to a set of new positions in the lineup.

The process above repeats for a total of five photographs before FJ gives
up.  Given the contents of each photograph, see if you can reconstruct the
original intended ordering A.  Each photograph shows an ordering of the
cows that differs from A in that some group of zero or more cows has moved.
However, a cow only moves in at most one photograph: if a cow is part of
the group that moves in one photograph, she will not actively move in any
of the other four photographs (although she could end up at a different
index as a consequence of other cows around her moving, of course).

PROBLEM NAME: photo

INPUT FORMAT:

* Line 1: The number of cows, N (1 <= N <= 20,000).

* Lines 2..5N+1: The next 5N lines describe five orderings, each one a
block of N contiguous lines.  Each line contains the ID of a
cow, an integer in the range 0...1,000,000,000.

SAMPLE INPUT (file photo.in):

5
10
20
30
40
50
20
10
30
40
50
30
10
20
40
50
40
10
20
30
50
50
10
20
30
40

INPUT DETAILS:

There are 5 cows, with IDs 10, 20, 30, 40, and 50.  In each of the 5
photos, a different cow moves to the front of the line (at most one cow
moves in each photo here, but it is possible in other inputs that multiple
cows could move in a particular photo).

OUTPUT FORMAT:

* Lines 1..N: The intended ordering A, one ID per line.

SAMPLE OUTPUT (file photo.out):

10
20
30
40
50

OUTPUT DETAILS:

The correct original ordering A[1..5] is 10, 20, 30, 40, 50.

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

Problem 2: Simplifying the Farm [Nathan Pinsker, 2011]

Farmer John has been taking an evening algorithms course at his local
university, and he has just learned about minimum spanning trees.  However,
Farmer John now realizes that the design of his farm is not as efficient as
it could be, and he wants to simplify the layout of his farm.

The farm is currently arranged like a graph, with vertices representing
fields and edges representing pathways between these fields, each having an
associated length.  Farmer John notes that for each distinct length,
at most three pathways on his farm share this length.  FJ would like to
remove some of the pathways on his farm so that it becomes a tree -- that
is, so that there is one unique route between any pair of fields.  Moreover,
Farmer John would like this to be a minimum spanning tree -- a tree having
the smallest possible sum of edge lengths.

Help Farmer John compute not only the sum of edge lengths in a minimum
spanning tree derived from his farm graph, but also the number of different
possible minimum spanning trees he can create.

PROBLEM NAME: simplify

INPUT FORMAT:

* Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000),
representing  the number of vertices and edges in the farm
graph, respectively.  Vertices are numbered as 1..N.

* Lines 2..M+1: Three integers a_i, b_i and n_i (1 <= a_i, b_i <= N; 1
<= n_i <= 1,000,000)  representing an edge from vertex a_i to
b_i with length n_i.  No edge length n_i will occur more than
three times.

SAMPLE INPUT (file simplify.in):

4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2

OUTPUT FORMAT:

* Line 1: Two integers representing the length of the minimal spanning
tree and the number of minimal spanning trees (mod
1,000,000,007).

SAMPLE OUTPUT (file simplify.out):

4 3

OUTPUT DETAILS:

Picking both edges with length 1 and any edge with length 2 yields a minimum
spanning tree of length 4.

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

Problem 3: Grass Planting [Travis Hance, 2011]

Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1
bidirectional roads, such that there is exactly one path between any two
pastures.  Bessie, a cow who loves her grazing time, often complains about
how there is no grass on the roads between pastures.  Farmer John loves
Bessie very much, and today he is finally going to plant grass on the
roads.  He will do so using a procedure consisting of M steps (1 <= M <=
100,000).

At each step one of two things will happen:

- FJ will choose two pastures, and plant a patch of grass along each road in
between the two pastures, or,

- Bessie will ask about how many patches of grass on a particular road, and
Farmer John must answer her question.

Farmer John is a very poor counter -- help him answer Bessie's questions!

PROBLEM NAME: grassplant

INPUT FORMAT:

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

* Lines 2..N: Two space-separated integers describing the endpoints of
a road.

* Lines N+1..N+M: Line i+1 describes step i. The first character of
the line is either P or Q, which describes whether or not FJ
is planting grass or simply querying. This is followed by two
space-separated integers A_i and B_i (1 <= A_i, B_i <= N)
which describe FJ's action or query.

SAMPLE INPUT (file grassplant.in):

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

OUTPUT FORMAT:

* Lines 1..???: Each line has the answer to a query, appearing in the
same order as the queries appear in the input.

SAMPLE OUTPUT (file grassplant.out):

2
1
2

**********************************************************************```
```
page revision: 0, last edited: 18 Dec 2011 19:00
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License