codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

707.md (2177B)


      1 Source: https://codeforces.com/blog/entry/46662
      2 
      3 Thanks all participants. I hope, you liked problems.
      4 
      5 A — Brain's photos
      6 
      7 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"
      8 
      9 B — Bakery
     10 
     11 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.
     12 
     13 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.
     14 
     15 C — Pythagorean triples
     16 
     17 D — Persistence bookcase
     18 
     19 Solution №1:
     20 
     21 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.
     22 
     23 Solution №2:
     24 
     25 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.
     26 
     27 E — Garlands
     28 
     29 Let us handle each request as follows:
     30 
     31 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".
     32 
     33 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.