Contest: FEB08 SILVER Division

ANALYSIS MODE
Submit solutions for your own enjoyment.

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Game of Lines [Neal Wu, 2007]

Farmer John has challenged Bessie to the following game: FJ has a
board with dots marked at N (2 <= N <= 200) distinct lattice points.
Dot i has the integer coordinates X_i and Y_i (-1,000 <= X_i <=
1,000; -1,000 <= Y_i <= 1,000).

Bessie can score a point in the game by picking two of the dots and
drawing a straight line between them; however, she is not allowed
to draw a line if she has already drawn another line that is parallel
to that line. Bessie would like to know her chances of winning, so
she has asked you to help find the maximum score she can obtain.

PROBLEM NAME: lines

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes lattice point i with two
        space-separated integers: X_i and Y_i.

SAMPLE INPUT (file lines.in):

4
-1 1
-2 0
0 0
1 1

OUTPUT FORMAT:

* Line 1: A single integer representing the maximal number of lines
        Bessie can draw, no two of which are parallel.

SAMPLE OUTPUT (file lines.out):

4

OUTPUT DETAILS:

Bessie can draw lines of the following four slopes: -1, 0, 1/3, and 1.

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

Problem 7: Meteor Shower [Jeffrey Wang, 2007]

Bessie hears that an extraordinary meteor shower is coming; reports
say that these meteors will crash into earth and destroy anything
they hit. Anxious for her safety, she vows to find her way to a
safe location (one that is never destroyed by a meteor) . She is
currently grazing at the origin in the coordinate plane and wants
to move to a new, safer location while avoiding being destroyed by
meteors along her way.

The reports say that M meteors (1 <= M <= 50,000) will strike, with
meteor i will striking point (X_i, Y_i) (0 <= X_i <= 300; 0 <= Y_i
<= 300) at time T_i (0 <= T_i <= 1,000). Each meteor destroys the
point that it strikes and also the four rectilinearly adjacent
lattice points.

Bessie leaves the origin at time 0 and can travel in the first
quadrant and parallel to the axes at the rate of one distance unit
per second to any of the (often 4) adjacent rectilinear points that
are not yet destroyed by a meteor.  She cannot be located on a point
at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

PROBLEM NAME: meteor

INPUT FORMAT:

* Line 1: A single integer: M

* Lines 2..M+1: Line i+1 contains three space-separated integers: X_i,
        Y_i, and T_i

SAMPLE INPUT (file meteor.in):

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

INPUT DETAILS:

There are four meteors, which strike points (0, 0); (2, 1); (1, 1); and (0,
3) at times 2, 2, 2, and 5, respectively.
                                                                          
       
    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = meteor impact
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = destroyed pasture
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6 

OUTPUT FORMAT:

* Line 1: The minimum time it takes Bessie to get to a safe place or
        -1 if it is impossible.

SAMPLE OUTPUT (file meteor.out):

5

OUTPUT DETAILS:

Examining the plot above at t=5, the closest safe point is (3, 0)
-- but Bessie's path to that point is too quickly blocked off by
the second meteor. The next closest point is (4,0) -- also blocked
too soon.  Next closest after that are lattice points on the
(0,5)-(5,0) diagonal. Of those, any one of (0,5), (1,4), and (2,3)
is reachable in 5 timeunits.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    Bessie's locations over time
       2|2 . . . . . .    for one solution
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6  

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

Problem 8: Eating Together [Ionescu Victor, 2007]

The cows are so very silly about their dinner partners. They have
organized themselves into three groups (conveniently numbered 1,
2, and 3) that insist upon dining together. The trouble starts when
they line up at the barn to enter the feeding area.

Each cow i carries with her a small card upon which is engraved D_i
(1 <= D_i <= 3) indicating her dining group membership. The entire
set of N (1 <= N <= 30,000) cows has lined up for dinner but it's
easy for anyone to see that they are not grouped by their dinner-partner
cards.

FJ's job is not so difficult.  He just walks down the line of cows
changing their dinner partner assignment by marking out the old
number and writing in a new one. By doing so, he creates groups of
cows like 111222333 or 333222111 where the cows' dining groups are
sorted in either ascending or descending order by their dinner
cards.

FJ is just as lazy as the next fellow. He's curious: what is the
absolute mminimum number of cards he must change to create a proper
grouping of dining partners? He must only change card numbers and
must not rearrange the cows standing in line.

PROBLEM NAME: egroup

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i describes the i-th cow's current dining group
        with a single integer: D_i

SAMPLE INPUT (file egroup.in):

5
1
3
2
1
1

INPUT DETAILS:

Five cows in line: first cow and last two cows prefer dining group 1;
second cow likes group 3; third cow likes group 2.

OUTPUT FORMAT:

* Line 1: A single integer representing the minimum number of changes
        that must be made so that the final sequence of cows is sorted
        in either ascending or descending order

SAMPLE OUTPUT (file egroup.out):

1

OUTPUT DETAILS:

We would need at least two changes to turn this into an increasing
sequence (changing both non-1's to a 1).

However, changing the first "1" to a "3" yields a decreasing sequence with
just one change, which is optimal.

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