Usaco Open10 Silver

Part of USACO Open10

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

Problem 6: Cows in Trees [MIT, 2010]

Bessie the cow and Farmer John have
gone traveling to the city of
Mootreepolis, but they were separated
and now Bessie is lost. Farmer John has
organized a search party to find her.
For better or worse, the only way they
have to locate her is by the direction
of Bessie's moo (which is loud enough as
to be heard anywhere in the city).

True to its name, Mootreepolis
transportation is organized as a tree. In
particular, the city has N (1 <= N <=
100,000) locations conveniently numbered
0..N-1 and connected by N-1 bidirectional walkways such that there
is a unique path between any pair of locations. Bessie is located
at one of the N locations in Mootreepolis.

The search party has fanned out so that one member of the search
party is located at each of the N locations. Farmer John can call
any of them to get a report on the direction from which they heard
Bessie's moo (i.e., which walkway leaving that location is in the
direction of Bessie -- or perhaps that Bessie was actually found
at that location).

However, Farmer John has an expensive mobile phone plan and wants
to minimize the number of calls he makes. Your task is to tell
Farmer John which locations to call in order to minimize the number
of calls he has to make. In particular, Farmer John wants to ensure
that he has to make no more than 20 calls before he can report
Bessie's location.

NOTE: In 50% of inputs, N will be at most 1000.

Your program should read the Mootreepolis map description from the
file cowtree.in and then interact with the grader program via
standard input and output (the console). The file cowtree.in will
contain a description of Mootreepolis, such that each line contains
a list of the walkways touching a given location. You should think
of this list as having a zero-based index (relevant later for
interaction with the grading program).

The first line of cowtree.in contains N. The second and subsequent
lines of of cowtree.in describe the neighbors of locations in
Mootreepolis (starting with location 0). The first integer on each
line is K (1 <= K <= N), the number of neighbors of the location.
This integer is followed by K more integers N_0, N_1, ..., N_K-1
that are the zero-based indices of those neighbors. Two locations
are neighbors if they are connected by a walkway.

Your program should print a sequence of locations to standard output.
Each time you print a location to standard output, the grader program
will respond with the index of the walkway in the direction of
Bessie. The walkway will be given by its index on the relevant input
line in cowtree.in. You should read this response from standard
input.

If at any point you print the location at which Bessie is located,
your program will be terminated. This will happen automatically,
so you don't have to worry about doing it yourself.

If you find Bessie, your program will be assigned a non-zero score:
10 if you used no more than 20 queries (including the current one),
0 if you used 30 queries or more. Otherwise, your score will be
30-(#queries made).

As a sample, suppose that Bessie is located at node 5 for the map
below of Mootreepolis; the input descriptor is shown on the right:

                               Node Count Neighbors
                0   1            0      1 3
                |   |            1      1 4
             2--3---4--5(B)      2      1 3
                |   |            3      4 0 2 6 4
                6   7            4      4 3 7 1 5
                                 5      1 4
                                 6      1 3
                                 7      1 4

One possible interaction sequence is shown in the table below, where
the query column indicates data sent to standard out, the response
column indicates data read from standard in, and the location column
contains the actual location that the response indicates. The details
column shows the full ordered list of locations connected to the
queried location along with the interpretation of the response (with
<>'s):

Query   Response    Location     Neighbor list details 
  2        0           3          <3>
  6        0           3          <3>
  3        3           4          0 2 6 <4>
  4        3           5          3 7 1 <5>
  5        Done; program will be terminated

From locations 2 and 6, location 3 is the closest neighbor to Bessie
(and also the only neighbor). From location 3, location 4 is the
closest neighbor to Bessie. From location 4, location 5 is the
closest neighbor to Bessie. Bessie is in fact located at location
5, so the grading system terminates the program after it outputs
5.

---------------- Reactive Programs ----------------------

In order to ensure that your program's output is not buffered inside
your program; you must 'flush' your output.

For C and C++ users, if you're using stdio.h, include the line

       setbuf(stdout, 0);

near the top of your program.

If you're using C++ iostream style I/O, flush each output line like
this:

cout << line << "\n" << flush;

For Pascal, add the following statement after each writeln statement:

flush(stdout);

For Java, add the following after each output statement:

    System.out.flush();

If your program 'times out' after you wrote a reply, it probably
is not properly flushing the output.

---------------- JAVA USERS ----------------------

Here is (we hope) the skeleton of input/output statements you will
need:

import java.io.*;
import java.util.*;

public class cowtree {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new
                                          InputStreamReader(System.in));
    /* write ... */
        System.out.println(...);
        System.out.flush();

    /* read a reply */
        response = in.readLine();
        ...

PROBLEM NAME: cowtree

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+2 contains multiple space-separated integers
        that describe the neighbors of location i in Mootreepolis: K,
        N_0, ..., N_K-1

SAMPLE INPUT (file cowtree.in):

8
1 3
1 4
1 3
4 0 2 6 4
4 3 7 1 5
1 4
1 3
1 4

OUTPUT FORMAT:

* Line none: write to standard out, not the output file.

SAMPLE OUTPUT (file cowtree.out):

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

Problem 7: Mountain Watching [Jeffrey Wang, 2009]

One day, Bessie was gazing off into the distance at the beautiful
Wisconsin mountains when she wondered to herself: which mountain
is the widest one?

She decided to take N (1 <= N <= 100,000) equally-spaced height
measurements H_i (1 <= H_i <= 1,000,000,000) sequentially along the
horizon using her new Acme Long Distance Geoaltimeter.

A mountain is defined to be a consecutive sequence of H_i values
which increases (or stays the same) and then decreases (or stays
the same), e.g., 2, 3, 3, 5, 4, 4, 1. It is possible for a mountain
on the edge of her field of vision only to increase or only to
decrease in height, as well.

The width of a mountain is the number of measurements it encompasses.
Help Bessie identify the widest mountain.

Here's a simple example of a typical horizon:

           *******                   *
          *********                 ***
          **********               *****
          ***********           *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaaa                   ccccccccccccccccccccc eeeeeee    ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd ffffffffff  hhhhhhhhh

The mountains are marked 'a', 'b', etc. Obviously, mountain b is
widest with width 28. The mountain on the left has width 6 for the
purposes of this task.

PROBLEM NAME: smount

INPUT FORMAT:

* Line 1: A single integer: N

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

SAMPLE INPUT (file smount.in):

7
3
2
3
5
4
1
6

INPUT DETAILS:

The height measurements are 3, 2, 3, 5, 4, 1, 6.

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the width of the
        widest mountain.

SAMPLE OUTPUT (file smount.out):

5

OUTPUT DETAILS:

The widest mountain consists of the measurements 2, 3, 5, 4, 1. Other
mountains include 3, 2 and 1, 6

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

Problem 8: Time Travel [Traditional / MIT, 2010]

Farmer John has purchased an Acme Time Machine. He can now travel
forward in time normally (without using the machine) or else jump
back to an arbitrary point in the past, at which point time will
start to go forward again, but potentially with events unfolding
in a new, different way. FJ can never travel forward in time in his
time machine.

FJ wants to raise the best possible cow herd, so he is going to try
several different ideas, keeping track of various statistics of his
cow herd through different possible time and event paths.

One statistic FJ cares about is the ID number of the cow he has had
for the shortest period of time. Please help him out by writing a
program to keep track of his herd and, after each command, reporting
the ID of the most recently acquired cow of the cows he owns (or
-1 if he has no cows).

FJ has a set of N (1 <= N <= 80,000) queries Q_i, conveniently
numbered 1..N, which represent consecutive updates from the point
of view of FJ's personal timeline.

Each query is a single line of input. The line begins with a single
character c (one of 'a', 's', or 't'). If c = 'a' or c = 't', then
c is followed by a space and an integer K (1 <= K <= 1,000,000).

  * If c = 'a', then FJ acquires a cow with ID K; add the cow to
    the herd.

  * If c = 's', then FJ sold his most recently acquired cow (it is
    guaranteed that FJ will have at least one cow whenever this
    type of query appears); remove the cow from the herd.

  * If c = 't', then FJ traveled back in time to just before the
    Kth query. Note that this means that FJ can potentially travel
    between parallel time paths (see sample input for clarification).
    Revert to the herd that was present just before query K.

By way of example, consider a series of 12 queries, shown below
along with the cow name list and the resulting output for each
query.

    Q#   Query   Owned Cows    Output      Comments
     1   a 5  -> [5]        => 5        Add a new cow with ID 5
     2   a 3  -> [5,3]      => 3        Add a new cow with ID 3
     3   a 7  -> [5,3,7]    => 7        Add a new cow with ID 7
     4   s    -> [5,3]      => 3        Sell recent cow 7
     5   t 2  -> [5]        => 5        Revert time to before query 2
     6   a 2  -> [5,2]      => 2        Add a new cow with ID 2
     7   t 4  -> [5,3,7]    => 7        Revert time to before query 4
     8   a 4  -> [5,3,7,4]  => 4        Add a new cow with ID 4
     9   s    -> [5,3,7]    => 7        Sell recent cow 4
    10   t 7  -> [5,2]      => 2        Revert time to before query 7
    11   s    -> [5]        => 5        Sell recent cow 2
    12   s    -> []         => -1       Sell recent cow 5

PROBLEM NAME: ttravel

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1: query Q_i

SAMPLE INPUT (file ttravel.in):

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

OUTPUT FORMAT:

* Lines 1..N: Line i: The ID of the most recently purchased cow after
        query i takes effect (-1 if no cows are owned).

SAMPLE OUTPUT (file ttravel.out):

5
3
7
3
5
2
7
4
7
2
5
-1

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