codeforces-scrape

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

484.md (6038B)


      1 Source: https://codeforces.com/blog/entry/14592
      2 
      3 [485A - Factory](/contest/485/problem/A "Codeforces Round 276 (Div. 2)")
      4 
      5 Production will stops iff exists integer *K* ≥ 0 such *a*·2*K* is divisible by *m*. From this fact follows that *K* maximum will be about *O*(*log*2(*m*)). So if we modeling some, for example, 20 days and production does not stop, then it will never stop and answer is "No". Otherwise answer is "Yes".
      6 
      7 [485B - Valuable Resources](/contest/485/problem/B "Codeforces Round 276 (Div. 2)")
      8 
      9 Let us find minimum length needed to cover points by *Ox*. It is *Maximum*(*x**i*) - *Minumum*(*x**i*). The same in *Oy* — *Maximum*(*y**i*) - *Minumum*(*y**i*). Since we need a square city to cover all the mines, then we need to set length of this square to the maximum from those two values.
     10 
     11 [484A - Bits](/contest/484/problem/A "Codeforces Round 276 (Div. 1)")
     12 
     13 Let us define function *f*(*L*, *R*), that gives answer to the query. It looks follows:
     14 
     15 * if *L* = *R* then *f*(*L*, *R*) = *L*;
     16 * else if 2*b* ≤ *L*, where *b* — maximum integer such 2*b* ≤ *R*, then *f*(*L*, *R*) = *f*(*L* - 2*b*, *R* - 2*b*) + 2*b*;
     17 * else if 2*b* + 1 - 1 ≤ *R* then *f*(*L*, *R*) = 2*b* + 1 - 1;
     18 * else *f*(*L*, *R*) = 2*b* - 1.
     19 
     20 Total complexity is *O*(*logR*) per query.
     21 
     22 [484B - Maximum Value](/contest/484/problem/B "Codeforces Round 276 (Div. 1)")
     23 
     24 Let us iterate over all different *a**j*. Since we need to maximize ![](https://espresso.codeforces.com/fab6bb390f875e9dbc8692275347ad1e68de8347.png), then iterate all integer *x* (such *x* divisible by *a**j*) in range from 2*a**j* to *M*, where *M* — doubled maximum value of the sequence. For each such *x* we need to find maximum *a**i*, such *a**i* < *x*. Limits for numbers allow to do this in time *O*(1) with an array. After that, update answer by value ![](https://espresso.codeforces.com/fab6bb390f875e9dbc8692275347ad1e68de8347.png). Total time complexity is *O*(*nlogn* + *MlogM*).
     25 
     26 [484C - Strange Sorting](/contest/484/problem/C "Codeforces Round 276 (Div. 1)")
     27 
     28 Note, that *d*-sorting is just a permutation (call it *P*), because it does not depends on characters in string. Look at shuffling operation in different way: instead of going to the next substring and sort it, we will shift string to one character left. It remains to understand that shift of string the permutation too (call it *C*). Now its clear, we need to calculate *S*·*P*·*C*·*P*·*C*... = *S*·(*P*·*C*)*n* - *k* + 1. And after that shift string for *k* - 1 character to the left for making answer to the shuffling operation. Here we use the multiplication of permutations. Since they are associative, that we can use binary algorithm to calculate (*P*·*C*)*n* - *k* + 1. Total time complexity is *O*(*nmlogn*).
     29 
     30 [484D - Kindergarten](/contest/484/problem/D "Codeforces Round 276 (Div. 1)")
     31 
     32 Let us note, that in optimal answer any segment that making a group contains their minimum and maximum values on borders. Otherwise it will be better to split this segment to two other segments. Another note that is every segment in optimal solution is strictly monotonic (increasing or decreasing). Paying attention to the interesting points in sequence which making local maximums (i. e. *a**i* - 1 < *a**i* > *a**i* + 1), local minimums (*a**i* - 1 > *a**i* < *a**i* + 1), and point adjacent to them. Solve the problem by dynamic programming: *D**i* is the answer in the prefix *i*. To calculate *D**i* we need to look at no more than three previous interesting points and to previous *D**i* - 1. Total time complexity is *O*(*n*).
     33 
     34 [484E - Sign on Fence](/contest/484/problem/E "Codeforces Round 276 (Div. 1)")
     35 
     36 Let us note that we can use binary search to find answer to the one query. Suppose at some moment was fixed height *h* and need to know will fit the rectangle with width *w* and height *h* to the segment of fence from *l*-th to *r*-th panel. Let us build data structure that can answer to this question. This will be persistent segment tree with unusual function inside: maximum number of consecutive ones in segment (*maxOnes*). In leaves of segment tree will be only numbers 0 and 1. To calculate this function need to know some other values, specifically:
     37 
     38 *len* — length of the segment in vertex of segment tree, *prefOnes* — length of prefix that consists only of ones, *sufOnes* — length of the suffix consist only of ones.
     39 
     40 These functions are computed as follows:
     41 
     42 *maxOnes* is equal to *max*(*maxOnes*(*Left*), *maxOnes*(*Right*), *sufOnes*(*Left*) + *prefOnes*(*Right*));
     43 
     44 *prefOnes* equals *prefOnes*(*Right*) + *len*(*Left*) in case of *len*(*Left*) = *prefOnes*(*Left*), and *prefOnes*(*Left*) otherwise;
     45 
     46 *sufOnes* equals *sufOnes*(*Left*) + *len*(*Right*) in case of *len*(*Right*) = *sufOnes*(*Right*), and *sufOnes*(*Right*) otherwise;
     47 
     48 *len* = *len*(*left*) + *len*(*Right*);
     49 
     50 *Left* и *Right* — it is left and right sons of vertex in segment tree.
     51 
     52 As mentioned above, tree must be persistent, and it must be built as follows. First, builded empty tree of zeros. Next in position of highest plank need to put 1. The same doing for planks in decreasing order. For example if fence described with sequence [2, 5, 5, 1, 3] then bottom of segment tree will changed as follows:
     53 
     54 [0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] -> [0, 1, 1, 0, 0] -> [0, 1, 1, 0, 1] -> [1, 1, 1, 0, 1] -> [1, 1, 1, 1, 1].
     55 
     56 And we need to remember for all *h**i* their version of tree. Now to answer the question we need to make query in our segment tree (that corresponding to height *h*) on segment [*l*, *r*]. If *maxOnes* form this query less than *w*, then rectangle impossible to put (otherwise possible).
     57 
     58 Building of tree will take *O*(*nlogn*) time and memory. Time complexity to the one query will take *O*(*log*2*n*) time.