Usaco Feb10 Gold

Part of USACO Feb10

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

Problem 1: Covering the Corral [Richard Peng, 2009]

The cows are so modest they want Farmer John to install covers
around the circular corral where they occasionally gather. The
corral has circumference C (1 <= C <= 1,000,000,000), and FJ can
choose from a set of M (1 <= M <= 100,000) covers that have fixed
starting points and sizes. At least one set of covers can surround
the entire corral.

Cover i can be installed at integer location x_i (distance from
starting point around corral) (0 <= x_i < C) and has integer length
l_i (1 <= l_i <= C).

FJ wants to minimize the number of segments he must install. What
is the minimum number of segments required to cover the entire
circumference of the corral?

Consider a corral of circumference 5, shown below as a pair of
connected line segments where both '0's are the same point on the
corral (as are both 1's, 2's, and 3's).

Three potential covering segments are available for installation:

           Start   Length
      i     x_i     l_i
      1      0       1 
      2      1       2 
      3      3       3 

        0   1   2   3   4   0   1   2   3  ... 
corral: +---+---+---+---+--:+---+---+---+- ...
        11111               1111
            22222222            22222222
                    333333333333
            |..................|

As shown, installing segments 2 and 3 cover an extent of (at least)
five units around the circumference. FJ has no trouble with the
overlap, so don't worry about that.

PROBLEM NAME: corral

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 contains two space-separated integers: x_i
        and l_i

SAMPLE INPUT (file corral.in):

5 3
0 1
1 2
3 3

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of segments
        required to cover all segments of the circumference of the
        corral

SAMPLE OUTPUT (file corral.out):

2

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

Problem 2: Cows on Ice [Jelle van den Hooff, 2010]

Bessie is ice skating on a large frozen lake modelled as a 2-dimensional
grid with coordinates in the range -1,000,000,000..1,000,000,000.
N (1 <= N <= 20,000) of the lake's grid cells contain rocks
(conveniently numbered 1..N). The other cells contain slippery ice.

Since Bessie is not a very good skater, she traverses the lake's
cells by pushing herself away from her current position near a rock
and sliding continuously in the same direction until she hits another
rock (stopping in the square before she hits the rock, of course).
Never good with complicated angles, Bessie can push herself only
straight north, east, south, or west. She can't push herself through
the rock, of course, and thus generally has only three possible
directions to move.

Sliding is not without risks. Bessie must hit a rock or might end
up sliding for a very long time. She must aim her pushes carefully.

Consider the situation depicted below; Bessie wants to get to
location (x=5,y=1), which is east of her current location (. = ice,
* = rock, B = Bessie, G = goal). If she slides directly to the east,
she will slide past the location since she can stop only by
encountering a rock head on. One way to get to (5,1) is the following:

   (a)              (b)             (c)              (d)
4 .....*.         .....*.         .....*.          .....*.
3 ..*....  slide  ..*....  slide  ..*....   slide  ..*....
2 ......*  north  ..B...*  east   .....B*   south  ......*
1 .*B..G. ------> .*...G. ------> .*...G.  ------> .*...B.
0 *....*.         *....*.         *....*.          *....*.
  0123456

Bessie could slide north, east, or south in situation (a), but only
north has a rock for stopping. For situation (b), she can slide
only east for the same reason.

For the input, rock i is located at cell X_i,Y_i (-1,000,000,000
<= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000),
and no two rocks occupy the same position. Bessie starts at Bx,By
(which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000;
-1,000,000,000 <= By <= 1,000,000,000). Bessie's goal is Gx,Gy
(-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=
1,000,000,000). Bessie can always reach the goal one way or another.

Bessie doesn't mind sliding. However, pushing herself away from a
rock is very tiring. To prepare her, FJ would like to know the
minimum number of pushes Bessie needs to do.

PROBLEM NAME: ice

INPUT FORMAT:

* Line 1: Five space separated integers: N, Bx, By, Gx, and Gy

* Lines 2..N+1: Line i+1 describes a rock location with space
        separated integers: X_i and Y_i

SAMPLE INPUT (file ice.in):

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

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of pushes for
        Bessie to get to her goal

SAMPLE OUTPUT (file ice.out):

3

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

Problem 3: Slowing down [Jelle van den Hooff, 2010]

Every day each of Farmer John's N (1 <= N <= 100,000) cows conveniently
numbered 1..N move from the barn to her private pasture. The pastures
are organized as a tree, with the barn being on pasture 1. Exactly
N-1 cow unidirectional paths connect the pastures; directly connected
pastures have exactly one path. Path i connects pastures A_i and
B_i (1 <= A_i <= N; 1 <= B_i <= N).

Cow i has a private pasture P_i (1 <= P_i <= N). The barn's small
door lets only one cow exit at a time; and the patient cows wait
until their predecessor arrives at her private pasture. First cow
1 exits and moves to pasture P_1. Then cow 2 exits and goes to
pasture P_2, and so on.

While cow i walks to P_i she might or might not pass through a
pasture that already contains an eating cow. When a cow is present
in a pasture, cow i walks slower than usual to prevent annoying her
friend.

Consider the following pasture network, where the number between
parentheses indicates the pastures' owner.

        1 (3)        
       / \
  (1) 4   3 (5)
     / \   
(2) 2   5 (4)

First, cow 1 walks to her pasture:

        1 (3)        
       / \
  [1] 4*  3 (5)
     / \   
(2) 2   5 (4)

When cow 2 moves to her pasture, she first passes into the barn's
pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before
arriving at her own pasture.

        1 (3)
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 3 doesn't get far at all -- she lounges in the barn's pasture, #1.

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

        1* [3]
       / \
  [1] 4*  3*[5]
     / \   
[2] 2*  5* [4]

FJ would like to know how many times each cow has to slow down.

PROBLEM NAME: slowdown

INPUT FORMAT:

* Line 1: Line 1 contains a single integer: N

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

* Lines N+1..N+N: line N+i contains a single integer: P_i

SAMPLE INPUT (file slowdown.in):

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

OUTPUT FORMAT:

* Lines 1..N: Line i contains the number of times cow i has to slow
        down.

SAMPLE OUTPUT (file slowdown.out):

0
1
0
2
1

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