2019年B1

A fire has broken out on the farm, and the cows are rushing to try and put it out!

The farm is described by a 10×1010×10 grid of characters like this:

..........

..........

..........

..B.......

..........

.....R....

..........

..........

.....L....

..........

The character 'B' represents the barn, which has just caught on fire. The 'L' character represents a lake, and 'R' represents the location of a large rock.

The cows want to form a "bucket brigade" by placing themselves along a path between the lake and the barn so that they can pass buckets of water along the path to help extinguish the fire. A bucket can move between cows if they are immediately adjacent in the north, south, east, or west directions. The same is true for a cow next to the lake --- the cow can only extract a bucket of water from the lake if she is immediately adjacent to the lake. Similarly, a cow can only throw a bucket of water on the barn if she is immediately adjacent to the barn.

Please help determine the minimum number of '.' squares that should be occupied by cows to form a successful bucket brigade.

A cow cannot be placed on the square containing the large rock, and the barn and lake are guaranteed not to be immediately adjacent to each-other.

INPUT FORMAT (file buckets.in):

The input file contains 10 rows each with 10 characters, describing the layout of the farm.

OUTPUT FORMAT (file buckets.out):

Output a single integer giving the minimum number of cows needed to form a viable bucket brigade.

SAMPLE INPUT:

..........

..........

..........

..B.......

..........

.....R....

..........

..........

.....L....

..........

SAMPLE OUTPUT:

7

In this example, here is one possible solution, which involves the optimal number of cows (7):

..........

..........

..........

..B.......

..C.......

..CC.R....

...CCC....

.....C....

.....L....

..........

Problem credits: Brian Dean

The key insight into solving this problem is that the answer can be computed easily using just the locations of the three objects in the scene.

To simplify things, imagine there is no rock. In this case, the answer is just the difference in x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-1-Frame">xx coordinate between the barn and lake, plus the difference in y" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-2-Frame">yy coordinate (minus one, since the endpoints don't count). This is sometimes known as "Manhattan" distance, since in downtown Manhattan the streets form a grid and you can only get from one location to another by moving along the x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-3-Frame">xx or y" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-4-Frame">yy directions following the grid, not diagonally.

If we add the rock back to the picture, this actually rarely affects the answer, since we can always route around the rock unless the rock is in the same vertical or horizontal line as the barn and lake and lies between the two, in which case our path takes two additional steps to route around the rock.

My C++ code for solving the problem is below. It should be straightforward to translate to other languages.

#include 

#include 

#include 

using namespace std;

int barn_i, barn_j, rock_i, rock_j, lake_i, lake_j;

int main(void)

{

  ifstream fin ("buckets.in");

  for (int i=0; i<10; i++) {

    string s;

    fin >> s;

    for (int j=0; j<10; j++) {

      if (s[j] == 'B') { barn_i = i; barn_j = j; }

      if (s[j] == 'R') { rock_i = i; rock_j = j; }

      if (s[j] == 'L') { lake_i = i; lake_j = j; }

    }

  }

  ofstream fout ("buckets.out");

  int dist_br = abs(barn_i - rock_i) + abs(barn_j - rock_j);

  int dist_bl = abs(barn_i - lake_i) + abs(barn_j - lake_j);

  int dist_rl = abs(rock_i - lake_i) + abs(rock_j - lake_j);

  // Check for special case where rock is between barn and lake  

  if ((barn_i==lake_i || barn_j==lake_j) && dist_bl == dist_br + dist_rl)

    fout << dist_bl + 1 << "\n";

  else

    fout << dist_bl - 1 << "\n";

  return 0;

}

2019年B2

The milk business is booming! Farmer John's milk processing factory consists of NN processing stations, conveniently numbered 1…N1…N (1≤N≤1001≤N≤100), and N−1N−1 walkways, each connecting some pair of stations. (Walkways are expensive, so Farmer John has elected to use the minimum number of walkways so that one can eventually reach any station starting from any other station).

To try and improve efficiency, Farmer John installs a conveyor belt in each of its walkways. Unfortunately, he realizes too late that each conveyor belt only moves one way, so now travel along each walkway is only possible in a single direction! Now, it is no longer the case that one can travel from any station to any other station.

However, Farmer John thinks that all may not be lost, so long as there is at least one station ii such that one can eventually travel to station ii from every other station. Note that traveling to station ii from another arbitrary station jj may involve traveling through intermediate stations between ii and jj. Please help Farmer John figure out if such a station ii exists.

INPUT FORMAT (file factory.in):

The first line contains an integer NN, the number of processing stations. Each of the next N−1N−1 lines contains two space-separated integers aiai and bibi with 1≤ai,bi≤N1≤ai,bi≤N and ai≠biai≠bi. This indicates that there is a conveyor belt that moves from station aiaito station bibi, allowing travel only in the direction from aiai to bibi.

OUTPUT FORMAT (file factory.out):

If there exists a station ii such that one can walk to station ii from any other station, then output the minimal such ii. Otherwise, output −1−1.

SAMPLE INPUT:

3

1 2

3 2

SAMPLE OUTPUT:

2

Problem credits: Dhruv Rohatgi

2. If x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-10-Frame">xx is the unique sink, then all nodes in the tree can reach x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-11-Frame">xx. Suppose some node y" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-12-Frame">yy cannot reach x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-13-Frame">xx. We know y" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-14-Frame">yy has an outgoing edge since it isn't a sink, so let's follow such an edge. This lands us on another node (say, z" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-15-Frame">zz) which if not a sink must also have an outgoing edge, so let's follow such an edge. If we keep following outgoing edges until we no longer can, we inevitably must get stuck at a sink, since this is the only node with no outgoing edges (and we can't go around in cycles since a tree has no cycles). This means we have reached x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-16-Frame">xx, since x" role="presentation" style="word-wrap: normal;max-width: none;max-height: none; min-width: 0px;min-height: 0px;float:none;word-spacing:normal" id="MathJax-Element-17-Frame">xx is the only sink.

My code for solving this problem is below.

#include 

#include 

using namespace std;

int N, incoming[101], outgoing[101];

int main(void)

{

  ifstream fin ("factory.in");

  fin >> N;

  for (int i=0; i

    int a, b;

    fin >> a >> b;

    outgoing[a]++;

    incoming[b]++; 

  }

  ofstream fout ("factory.out");

  int answer = -1;

  for (int i=1; i<=N; i++) {

    if (outgoing[i]==0 && answer != -1 ) { answer = -1; break; } // found two sinks -- bad!

    if (outgoing[i]==0) answer = i;  // found first sink; remember it

  }

  fout << answer << "\n";

  return 0;

}  

2019年B3

It is the year 3019, and a surprising amount of bovine evolution has transpired in the past thousand years, resulting in cows with all sorts of interesting features.

The bovine evolutionary record can be described as a tree, starting with a basic ancestral cow at the root with no special features. At each descendant level in the tree, either all cows evolve a new feature (such as fire breathing, below, where all cows with spots ended up breathing fire), or there is a divergent split in the bovine population where some of the cows evolve a new feature (e.g., flying) and some do not.

The leaves at the bottom of the tree indicate all the resulting sub-populations of cows in the year 3019. No leaves (sub-populations) contain identical sets of features. For example, sub-population #1 contains cows with no special features, while sub-population #3 contains telepathic flying cows. Sub-population #2, by contrast, has flying cows that are not telepathic. Sub-population #3 is unique in its combination of flying and telepathic cows.

An evolutionary tree like the one above is called "proper" if each newly evolved feature originates in exactly one edge of the tree (e.g., it evolved into being at a single point in history). For example, a tree would not be proper if spots evolved into being in two separate branches. Given a description of the sub-populations of cows in the year 3019, please determine if these can be described by a proper evolutionary tree.

INPUT FORMAT (file evolution.in):

The first line of input contains the number of sub-populations, NN (2≤N≤252≤N≤25). Each of the next NN lines describes a sub-population. The line starts with an integer KK (0≤K≤250≤K≤25), then KK characteristics of all the cows in that sub-population. Characteristics are strings of up to 20 lowercase characters (a..z). No two sub-populations have exactly the same characteristics.

OUTPUT FORMAT (file evolution.out):

Please output "yes" if it is possible to form a proper evolutionary tree explaining the origin of these sub-populations, and "no" otherwise.

SAMPLE INPUT:

4

2 spots firebreathing

0

1 flying

2 telepathic flying

SAMPLE OUTPUT:

yes

This example input corresponds to the proper tree shown in the diagram above.

Problem credits: Brian Dean

his is probably the hardest bronze problem we've asked all season, befitting the fact that it's on the US Open contest (for which there is a longer time limit). It takes a good bit of thought to figure out the right solution structure, after which coding isn't too bad. I'll go through a couple of solution ideas in detail below. Hopefully you found this and the other bronze problems fun and challenging this season!

First, it may help to think of an instance where we cannot form a proper evolutionary tree. This would be an instance such that no matter how we form the tree, it would be inevitable that some characteristic would evolve in two distinct places in the tree. It turns out that the minimal such bad example looks like this:

population1: A

population2: B

population3: A B

In other words, we have a population with just trait A, a population with just trait B, and a population with both. If we want to build a tree out of this input, we would need to split on either A or B at the root, but then the remaining two subtrees would both need to have an edge that adds the other characteristic. For example, if the root split into "A" and "not A" branches, then both branches would need to contain an edge that adds the "B" trait.

It will help to actually look at things from the viewpoint of the characteristics instead of from the viewpoint of the populations, so let's "transpose" the input above:

A: population1 population3

B: population2 population3

The fundamental problem here is that there are populations in A only, populations in B only, and populations in both A and B. If we look at the Venn diagram for the sets A and B, the picture therefore looks like this:

Let's call this situation a "crossing" pair of sets. In general, two sets can be disjoint (no overlap), nesting (one inside the other), or crossing (overlap but not nesting). If any two of the characteristics A and B in our instance represent crossing sets as above, then we cannot build a proper tree. On the other hand, if all the characteristics represent sets that don't cross (they are either disjoint or nested), then we get a Venn diagram like this:

If you look at this picture carefully, hopefully you see a tree formed by the nesting structure of the sets:

A tree like this is easy to convert into a proper evolutionary tree. E.g., if we have three children A, B, and C, we could just make three sequential two-way splits that add the A, B and C characteristics.

So, at the end of the day, we actually don't need to build a proper evolutionary tree, but we just need to test of any of our characteristics represent crossing sets; if so (and only if so), a proper tree is impossible to build. This leads to probably the easiest solution of the problem, shown in my code below where I build all the sets of populations having each characteristic and then just test if any pair of these sets is crossing.

Below this code, I'll discuss an alternate solution that also solves the problem and also builds the tree (if possible).

#include

#include

#include

using namespace std;

 

int N;

vector characteristics[25];

vector all_characteristics;

 

// Do two sets "cross" -- I.e., are there elements in A, B, and A intersect B?

bool crossing(int a, int b)

{

  int A=0, B=0, AB=0;

  for (int i=0; i

    vector &v = characteristics[i];

    bool has_a = false, has_b = false;

    for (int j=0; j

      if (v[j]==all_characteristics[a]) has_a = true;

      if (v[j]==all_characteristics[b]) has_b = true;

    }

    if (has_a && has_b) AB++;

    else if (has_a) A++;

    else if (has_b) B++;

  }

  return AB>0 && A>0 && B>0;

}

 

int main(void)

{

  ifstream fin ("evolution.in");

  fin >> N;

  string s;

  for (int i=0; i

    int K;

    fin >> K;

    for (int j=0; j

      fin >> s;

      characteristics[i].push_back(s);

      bool found = false;

      for (int k=0; k

        if (all_characteristics[k] == s) found = true;

      if (!found) all_characteristics.push_back(s);

    }

  }

  int M = all_characteristics.size();

  bool ok = true;

  for (int a=0; a

    for (int b=a+1; b

      if (crossing(a, b)) ok = false;

 

  ofstream fout ("evolution.out");

  if (ok) fout << "yes\n";

  else fout << "no\n";

  return 0;

}

Another solution approach uses slightly different insight: suppose we have two traits A and B as follows:

A: (4 populations having trait A)

B: (17 populations having trait B)

This means the "+A" edge in the tree (the edge adding trait A) cannot be an ancestor of the "+B" edge, since otherwise every population with the B trait would also have the A trait, contradicting the observation that the size of set A above is smaller than that of B. In general, this means splits on traits involving large sets of populations happen higher in the tree, and in particular the split at the root has to involve the trait with the largest sized set (the set having the most populations).

A method for building the tree therefore is to split on the largest trait, thereby dividing the populations into two groups, and then continuing to divide these groups the same way, always splitting on the largest available trait. If there is ever a tie for the largest trait (say, between traits A and B), some careful thought will convince you that either A or B would be suitable for the split at the root (this is clear if A and B are disjoint, and if A and B are crossing we will get into trouble later no matter what; A and B cannot be nesting if they have the same size). If we ever end up adding the same trait in two different places in the tree, we know that building a proper tree was not possible.

Here's a cool way to think about the approach above. Suppose we wanted to sort a bunch of 3-digit binary numbers. We could first sort them on their leading digit, giving a block of numbers starting with 0 followed by a block starting with 1:

010

000

011

---

110

100

101

Then within each of these two blocks, we can do the same thing, sorting on the second digit. This makes our numbers sorted on their first two digits:

000

---

011

010

---

100

101

---

110

Finally, sorting within each block on the last digit makes everything sorted.

If we write our different populations like this:

            traitA traitB traitC traitD traitE... (in decreasing order of size)

population1   1      0      0      1      0

population2   0      1      1      0      1

population3   1      1      0      0      0

population4   0      1      1      0      1

Then each population is expressed as a binary number whose 1s and 0s reflect its traits. Now sorting these binary numbers the same way as above ends up basically running the tree construction approach we just described. We first sort on the leading digit, which separates the populations having trait A (the largest trait that we wanted to split on at the root) from those not having trait A. Then we split those groups on the second largest trait, and so on. So building the tree is much like sorting if we look at it from this perspective.

Note that this problem is directly applicable to real-world problems facing evolutionary biologists in terms of figuring out the most likely way organisms evolved in the past. The tree structure we are building is often called a "phylogenetic" tree in this area of study.