codeforces-scrape

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

359.md (5209B)


      1 Source: https://codeforces.com/blog/entry/9425
      2 
      3 **I'm not good in English. So, if you find an mistake in editorial, please, send me a private message.**
      4 
      5 ## [359A - Table](/contest/359/problem/A "Codeforces Round 209 (Div. 2)")
      6 
      7 If there are some good cell, which is located in the first row or in the first column, the answer is two. Similarly, if If there are some good cell, which is located in the last row or in the last column, the answer is two. Otherwise, the answer is four.
      8 
      9 Авторское решение: [4968279](/contest/359/submission/4968279 "Submission 4968279 by gridnevvvit")
     10 
     11 ## [359B - Permutation](/contest/359/problem/B "Codeforces Round 209 (Div. 2)")
     12 
     13 The answer is a slightly modified permutation 1, 2, ..., 2*n*. Let's reverse numbers 2*i* - 1 and 2*i* for each 1 ≤ *i* ≤ *k*. It's not hard to understand, that this permutation is good.
     14 
     15 Авторское решение: [4968385](/contest/359/submission/4968385 "Submission 4968385 by gridnevvvit")
     16 
     17 ## [359C - Prime Number](/contest/359/problem/C "Codeforces Round 209 (Div. 2)")
     18 
     19 Obviously, the answer is *x**v*. Let *sum* = *a*1 + *a*2 + ... + *a**n*. Also let *s**i* = *sum* - *a**i* (the array of degrees). After that let's find value *v* by the following algorithm: Let's consider a sequence of degrees as decreasing sequence. Now we will perform the following operation until it's possible to perfom it. Take the minimum degree *v* from the array of degrees and calculate the number of elements *cnt*, which have the same degree. If *cnt* multiples of *x*, then replace all *cnt* elements by *cnt* / *x* elements of the form *v* + 1. Since the sequence of degrees is a decreasing sequence, we can simply assign them to the end. If *cnt* is not a multiple of *x*, then we found the required value *v*. Also you need to check, that *v* is not greater then *sum*. Otherwise, *v* will be equals to *sum*.
     20 
     21 Авторское решение: [4968346](/contest/359/submission/4968346 "Submission 4968346 by gridnevvvit")
     22 
     23 ## [359D - Pair of Numbers](/contest/359/problem/D "Codeforces Round 209 (Div. 2)")
     24 
     25 Quite simple note: if the pair (*l*, *r*) satisfies the condition 1 from the statements, then *min*(*l*, *r*) = *GCD*(*l*, *r*), where *min*(*l*, *r*) is smallest number *a**i* from the segment (l, r) and *GCD*(*l*, *r*) is a GCD of all numbers from the segment (l, r). Calculate some data structure that will allow us to respond quickly to requests *GCD*(*l*, *r*) and *min*(*l*, *r*). For example, you can use Sparce Table. Solutuions, that uses segment tree, is too slow. So I think, you should use Sparce Table. So, now our task quite simple. Let's use binary search to find greatest value of *r* - *l*:
     26 
     27 ```
     28 lf = 0;  //left boundary of binary search
     29 rg = n;  //right boundary of binary search
     30 while (rg - lf > 1) {
     31   int mid = (lf + rg) / 2;
     32   if (ok(mid))   //ok(mid)
     33     lf = mid;
     34   else
     35     rg = mid;
     36 }
     37 ```
     38 
     39 *ok*(*mid*) is the function, that determines, is there some segment where *min*(*l*, *r*) = *GCD*(*l*, *r*) and *mid* = *r* - *l* (*mid* — is fixed value by binary search). If there is some good segment, you should update boundaries of binary search correctly. After that, it's very simple to restore answer.
     40 
     41 [Some information about Sparce Table](http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static)
     42 
     43 Авторское решение: [4968587](/contest/359/submission/4968587 "Submission 4968587 by gridnevvvit")
     44 
     45 ## [359E - Neatness](/contest/359/problem/E "Codeforces Round 209 (Div. 2)")
     46 
     47 You should write recursive function, that will turn on the light in all rooms, where it's possible. Also this function will visit all rooms, which it may visit. Let this function is called paint(x, y), where x, y is the current room. *Paint*(*x*, *y*) will use following idea: Let's look at all neighbors. If there is a light in the current direction (rule 3 from the statement), and the room (*nx*, *ny*) (current neighbor) has not yet visited, we will call our recursive function from (*nx*, *ny*). Also, we will turn on the light in all rooms, were we were. If some room is not visited by *paint*(*x*, *y*) and lights is on in this room, the answer is "NO". Otherwise, the answer is "YES". After that let's calculate value *dist*(*x*, *y*) by using bfs. *dist*(*x*, *y*) — is a minimal possible distance from the start to the current position (*x*, *y*). It's possible to use in our bfs only rooms, where lights is on. After that we will write the same function *repaint*(*x*, *y*). *Repaint*(*x*, *y*) will use following idea: Let's look at all neighbors. If there is a light in the current neighbor (*nx*, *ny*) and *dist*(*nx*, *ny*) > *dist*(*x*, *y*) ((*x*, *y*) — current room), let's call our recursive function from (*nx*, *ny*).After that we will come back to room (*x*, *y*). If there is no such neigbor (*nx*, *ny*), turn off the light in the room (*x*, *y*). Also you should look at my solution for more details.
     48 
     49 Авторское решение: [4968657](/contest/359/submission/4968657 "Submission 4968657 by gridnevvvit")