Usaco Dec11 Silver

Part of USACO Dec11

**********************************************************************
                           SILVER 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: Roadblock [Brian Dean, 2011]

Every morning, FJ wakes up and walks across the farm from his house to the
barn.  The farm is a collection of N fields (1 <= N <= 100) connected by M
bidirectional pathways (1 <= M <= 10,000), each with an associated length. 
FJ's house is in field 1, and the barn is in field N.  No pair of fields is
joined by multiple redundant pathways, and it is possible to travel between
any pair of fields in the farm by walking along an appropriate sequence of
pathways.  When traveling from one field to another, FJ always selects a
route consisting of a sequence of pathways having minimum total length.

Farmer John's cows, up to no good as always, have decided to interfere with
FJ's morning routine.  They plan to build a pile of hay bales on exactly one
of the M pathways on the farm, doubling its length.  The cows wish to
select a pathway to block so that they maximize the increase in FJ's
distance from the house to the barn.  Please help the cows determine
by how much they can lengthen FJ's route.

PROBLEM NAME: rblock

INPUT FORMAT:

* Line 1: Two space-separated integers, N (1 <= N <= 100) and M (1 <=
        M <= 10,000).

* Lines 2..1+M: Line j+1 describes the jth bidirectional pathway in
        terms of three space-separated integers: A_j B_j L_j, where
        A_j and B_j are indices in the range 1..N indicating the
        fields joined by the pathway, and L_j is the length of the
        pathway (in the range 1...1,000,000).

SAMPLE INPUT (file rblock.in):

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

INPUT DETAILS:

There are 5 fields and 7 pathways.  Currently, the shortest path from the
house (field 1) to the barn (field 5) is 1-3-4-5 of total length 1+3+2=6.

OUTPUT FORMAT:

* Line 1: The maximum possible increase in the total length of FJ's
        shortest route made possible by doubling the length of a
        single pathway.

SAMPLE OUTPUT (file rblock.out):

2

OUTPUT DETAILS:

If the cows double the length of the pathway from field 3 to field 4
(increasing its length from 3 to 6), then FJ's shortest route is now 1-3-5,
of total length 1+7=8, larger by two than the previous shortest route length.

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

Problem 3: Umbrellas for Cows [Alex Chen, 2011]

Today is a rainy day! Farmer John's N (1 <= N <= 5,000) cows, numbered
1..N, are not particularly fond of getting wet. The cows are standing in
roofless stalls arranged on a number line. The stalls span X-coordinates
from 1 to M (1 <= M <= 100,000). Cow i stands at a stall on coordinate X_i
(1 <= X_i <= M). No two cows share stalls.

In order to protect the cows from the rain, Farmer John wants to buy them
umbrellas. An umbrella that spans coordinates X_i to X_j (X_i <= X_j) has a
width of X_j - X_i + 1. It costs C_W (1 <= C_W <= 1,000,000) to buy an
umbrella of width W.  Larger umbrellas do not necessarily cost more than
smaller umbrellas.

Help Farmer John find the minimum cost it takes to purchase a set of
umbrellas that will protect every cow from the rain.  Note that the set of
umbrellas in an optimal solution might overlap to some extent.

PROBLEM NAME: umbrella

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer: X_i.

* Lines N+2..N+M+1: Line N+j+1 contains a single integer: C_j.

SAMPLE INPUT (file umbrella.in):

6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19

INPUT DETAILS:

There are 12 stalls, and stalls 1, 2, 4, 8, 11, and 12 contain cows. An
umbrella covering one stall costs 2, an umbrella covering two stalls costs
3, and so on.

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum cost needed to purchase
        umbrellas for all the cows.

SAMPLE OUTPUT (file umbrella.out):

9

OUTPUT DETAILS:

By purchasing a size 4 umbrella, a size 1 umbrella, and a size 2 umbrella,
it is possible to cover all the cows at a cost of 4+2+3=9:

UUUUUUUUUU           U        UUUU
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

C represents a cow and U represents a part of an umbrella.

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License