Codeforces Round #368 (Div.2) разбор

Codeforces Round #368 (Div.2) разбор

By zloyplace35, 7 years ago, translation,

Thanks all participants. I hope, you liked problems.

A — Brain's photos

We need to do exactly what is written in the task: to consider all of the characters, and, if there is at least one of the set {C, M, Y} print "#Color" else — "#Black&White"

B — Bakery

Note that it makes no sense to choose the city for bakeries and the city with the warehouse so that had more than one way between them, as every road increases the distance over which you have to pay.

So, the problem reduces to the following: select two neighboring cities so that one is a warehouse, and in the other & mdash; no. For doing this, simply iterate through all the city with the warehouse, among the neighbors of each town without looking for a warehouse and update the answer. If there is such a pair of cities, print -1.

C — Pythagorean triples

D — Persistence bookcase

Solution №1:

Note that the data is delivered all at once (offline). Then we can build a tree of versions, then run out of the DFS root and honestly handle each request in the transition from the top to the top.

Solution №2:

Note that Alina uses operations that relate to the columns. We can make an array of versions of the shelves, and each version of the cabinet to provide an array of indices and the corresponding shelves to store it explicitly. Then, for the operation, such as changing wardrobe, shelves, a new version which has been changed, this version of the index is recorded on the same shelf position. This approach eliminates the decision on the use of extra memory for storing unnecessary information.

E — Garlands

Let us handle each request as follows:

Let's go for a "frame" request and remember lamp garlands, which lies on the boundary. Then, in order to find concrete garland, what part of it lies within the query, sum all of its segments, the ends of it are lamps that lie on the "frame".

Also, do not forget the garland wich lies entirely within the request. Each garland at the beginning we find the extreme points, and to check whether it lies entirely within the query, check whether the lie inside its extreme points.