codeforces-scrape

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

253.md (3370B)


      1 Source: https://codeforces.com/blog/entry/6073
      2 
      3 Sorry for the short tutorial: we are too busy preparing and conducting school competition.
      4 
      5 [253A - Boys and Girls](/contest/253/problem/A "Codeforces Round 154 (Div. 2)")
      6 
      7 Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB.
      8 
      9 [253B - Physics Practical](/contest/253/problem/B "Codeforces Round 154 (Div. 2)")
     10 
     11 For each *x* from 1 to 5000 calculate *count*(*x*) — the number of measurements equal to *x*. The iterate over all possible minimal values *m* (from 1 to 5000). For a fixed *m* we can easily figure out which numbers we have to erase: we should erase every number *k* that *k* < *m* or *k* > 2·*m*. To find out the number of such values in the given sequence, we should sum up values *count*(*k*) for all such *k*.
     12 
     13 [253C - Text Editor](/contest/253/problem/C "Codeforces Round 154 (Div. 2)")
     14 
     15 One of the solutions to the problem is breadth-first-search (BFS). Vertices of the graph correspond to all possible pairs (*r*, *c*), denoting the row and the position of the cursor. Each vertex has at most four arcs leaving it (these arcs correspond to pressing the buttons). So we need to find the shortest path from one vertex to the other. There are at most 107 vertices and at most 4·107 arcs. This problem can also be solved with some greedy observations.
     16 
     17 [253D - Table with Letters - 2](/contest/253/problem/D "Codeforces Round 154 (Div. 2)")
     18 
     19 Lets iterate over all pairs of rows *i*, *j* (*i* < *j*), that bounds the sub-table from the top and from the bottom. Then for each character *ch* make a list of such column numbers *k* that *T*[*i*, *k*] = *T*[*j*, *k*] = *ch*. Consider such list for some fixed character *ch*. All we need to count is the number of pairs *l*, *r* (*l* < *r*) in this list such that the sub-table with corners at (*i*, *l*) and (*j*, *r*) contains not more than *k* characters "*a*". This can be done using two standard techniques: two-pointer method and calculating partial sums.
     20 
     21 [253E - Printer](/contest/253/problem/E "Codeforces Round 154 (Div. 2)")
     22 
     23 First lets learn how to simulate the process with all priorities known. We will keep the priority queue of tasks. The task enters the queue when the printer receives this task, and leaves the queue when the printer finishes it. Then every change in the queue happens when one of the two possible events occurs: the printer receives some task or finishes printing some task. Between the consecutive events printer just prints pages from the tasks with the highest priority. So, if we maintain a set of events, the simulation can be done in *O*(*NlogN*).
     24 
     25 To solve the problem, make an obvious observation: the higher priority the task has, the sooner the printer finishes it. Then the required missing priority can be found using binary search. Also we can search the missing priority among *O*(*N*) values. The overall complexity is *O*(*Nlog*2(*N*)).
     26 
     27 This problem also has *O*(*NlogN*) solution, which will be described later.