codeforces-scrape

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

492.md (4403B)


      1 Source: https://codeforces.com/blog/entry/14957
      2 
      3 [492A - Vanya and Cubes](/contest/492/problem/A "Codeforces Round 280 (Div. 2)").
      4 
      5 In fact need to do what is asked in the statement. We need to find in a cycle the maximum height *h*, counting, how many blocks must be in *i*-th row and adding these values to the result. Iterate until the result is not greater than *n*.
      6 
      7 Jury's solution: [8924831](/contest/492/submission/8924831 "Submission 8924831 by Wild_Hamster")
      8 
      9 [492B - Vanya and Lanterns](/contest/492/problem/B "Codeforces Round 280 (Div. 2)").
     10 
     11 Sort lanterns in non-decreasing order. Then we need to find maximal distance between two neighbour lanterns, let it be *maxdist*. Also we need to consider street bounds and count distances from outside lanterns to street bounds, it will be (*a*[0] - 0) and (*l* - *a*[*n* - 1]). The answer will be *max*(*maxdist* / 2, *max*(*a*[0] - 0, *l* - *a*[*n* - 1]))
     12 
     13 Time complexity *O*(*nlogn*).
     14 
     15 Jury's solution: [8924823](/contest/492/submission/8924823 "Submission 8924823 by Wild_Hamster")
     16 
     17 [492C - Vanya and Exams](/contest/492/problem/C "Codeforces Round 280 (Div. 2)").
     18 
     19 Sort (*a**i*, *b**i*) in non-decreasing order for number of essays *b**i*, after that go from the beginning of this sorted pairs and add greedily the maximal number of points we can, i.e. add value *min*(*avg* * *n* - *sum*, *r* - *a**i*), while total amount of points will not be greater, than *avg* * *n*.
     20 
     21 Time complexity *O*(*nlogn*).
     22 
     23 Jury's solution: [8924807](/contest/492/submission/8924807 "Submission 8924807 by Wild_Hamster")
     24 
     25 [492D - Vanya and Computer Game](/contest/492/problem/D "Codeforces Round 280 (Div. 2)").
     26 
     27 Let's create vector *rez* with size *x* + *y*, in which there will be a sequence of Vanya's and Vova's strikes for the first second. To do this, we can take 2 variables *cntx* = *cnty* = 0. Then while *cntx* < *x* and *cnty* < *y*, we will check 3 conditions:
     28 
     29 1) If (*cntx* + 1) / *x* > (*cnty* + 1) / *y*, then add into the vector word “Vova”, *cnty*++.
     30 
     31 2) If (*cntx* + 1) / *x* < (*cnty* + 1) / *y*, then add into the vector word “Vanya”, *cntx*++.
     32 
     33 3) If (*cntx* + 1) / *x* = (*cnty* + 1) / *y*, then add into the vector word “Both” 2 times, *cntx*++, *cnty*++.
     34 
     35 Then we are able to respond on each query for *О*(1), the answer will be *rez*[(*a**i* - 1)*mod*(*x* + *y*)].
     36 
     37 Time complexity *O*(*x* + *y*).
     38 
     39 Jury's solution: [8924773](/contest/492/submission/8924773 "Submission 8924773 by Wild_Hamster")
     40 
     41 [492E - Vanya and Field](/contest/492/problem/E "Codeforces Round 280 (Div. 2)").
     42 
     43 As long as *gcd*(*dx*, *n*) = *gcd*(*dy*, *n*) = 1, Vanya will do full cycle for *n* moves. Let's group all possible pathes into *n* groups, where 1 - *th*, 2 - *nd*, ... , *n* - *th* path will be started from points (0, 0), (0, 1), …, (0, *n* - 1). Let's look on first path: (0, 0) - (*dx*, *dy*) - ((2 * *dx*) *mod* *n*, (2 * *dy*) *mod* *n*) - ... - (((*n* - 1) * *dx*) *mod* *n*, ((*n* - 1) * *dy*) *mod* *n*). As long as *gcd*(*dx*, *n*) = 1, among the first coordinates of points of the path there will be all the numbers from 0 to *n* - 1. So we can write in the array all relations between the first and second coordinate in points for the path, that starts in the point (0, 0), i.e. *y*[0] = 0, *y*[*dx*] = *dy*, ... , *y*[((*n* - 1) * *dx*) *mod* *n*] = ((*n* - 1) * *dy*) *mod* *n*. Now we know, that all points with type (*i*, *y*[*i*]), where 0 ≤ *i* ≤ *n* - 1, belong to the group with start point (0, 0). In that case, points with type (*i*, (*y*[*i*] + *k*)*modn*) belong to the group with start point (0, *k*). Then we can add every point (*x**i*, *y**i*) to required group *k* for *О*(1): (*y*[*x**i*] + *k*) *mod* *n* = *y**i*, *k* = (*y**i* - *y*[*x**i*] + *n*) *mod* *n*. Then we need just to find group with the maximal amount of elements, it will be the answer.
     44 
     45 Time complexity *O*(*n*).
     46 
     47 Jury's solution: [8924746](/contest/492/submission/8924746 "Submission 8924746 by Wild_Hamster")
     48 
     49 P.S. Sorry for my bad English, I hope, I will correct this editorial as much, as possible.