codeforces-scrape

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

446.md (7336B)


      1 Source: https://codeforces.com/blog/entry/13036
      2 
      3 The editorial is updated.
      4 
      5 ### [447A - DZY любит хэши](/contest/447/problem/A "Codeforces Round FF (Div. 2)")
      6 
      7 We just need an array to store the numbers inserted and check whether a conflict happens. It's easy.
      8 
      9 ### [447B - DZY любит строки](/contest/447/problem/B "Codeforces Round FF (Div. 2)")
     10 
     11 Firstly the optimal way is to insert letter with maximal *w**i*. Let ![](https://espresso.codeforces.com/a92f06ec2ae3bc4053c8950ce73a3239d905fb8f.png){*w**i*}. If we insert this character into the *k*'th position, the extra value we could get is equal to ![](https://espresso.codeforces.com/839e4ceaae79055597505d02743b5389ebc452d4.png). Because of *w**s**i* ≤ *num*, when *k* = *n* + 1, we can get the largest extra value.
     12 
     13 So if we insert the k letters at the end of *S*, we will get the largest possible value.
     14 
     15 ### [446A - DZY любит последовательности](/contest/446/problem/A "Codeforces Round FF (Div. 1)")
     16 
     17 We can first calculate *l**i* for each 1 ≤ *i* ≤ *n*, satisfying *a**i* - *l**i* + 1 < *a**i* - *l**i* + 2 < ... < *a**i*, which *l**i* is maximal.
     18 
     19 Then calculate *r**i*, satisfying *a**i* < *a**i* + 1 < ... < *a**i* + *r**i* - 1, which *r**i* is also maximal.
     20 
     21 Update the answer ![](https://espresso.codeforces.com/ea6916e0b112eb2dbf8d0c132fcbc58907c0d301.png), when *a**i* - 1 + 1 < *a**i* + 1.
     22 
     23 It's easy to solve this problem in *O*(*n*).
     24 
     25 ### [446B - DZY любит модификации](/contest/446/problem/B "Codeforces Round FF (Div. 1)")
     26 
     27 If *p* = 0, apperently the best choice is choosing the row or column which can give greatest pleasure value each time.
     28 
     29 Ignore *p* first,then we can get a greatest number *ans*. Then if we choose rows for *i* times, choose columns for *k* - *i* times, *ans* should subtract (*k* - *i*) × *i* × *p*.
     30 
     31 So we could enumerate i form 0 to k and calculate *ans**i* - (*k* - *i*) * *i* * *p* each time, max {*ans**i* - (*k* - *i*) * *i* * *p*} is the maximum possible pleasure value DZY could get.
     32 
     33 Let *a**i* be the maximum pleasure value we can get after choosing *i* rows and *b**i* be the maximum pleasure value we can get after choosing *i* columns. Then *ans**i* = *a**i* + *b**k* - *i*. We can use two priority queues to calculate *a**i* and *b**i* quickly.
     34 
     35 ### [446C - DZY любит числа Фибоначчи](/contest/446/problem/C "Codeforces Round FF (Div. 1)")
     36 
     37 As we know, ![](https://espresso.codeforces.com/b9e3e5165d4f1bca53ed1c9d2c05a1a7da40e85b.png)
     38 
     39 Fortunately, we find that ![](https://espresso.codeforces.com/278edfe7094dd98b14ba89bb856d666c7cda43c8.png)
     40 
     41 So, ![](https://espresso.codeforces.com/5ded954972b8454d73cb4407df81f5cc56ae00f1.png)
     42 
     43 With multiplicative inverse, we find,
     44 
     45 ![](https://espresso.codeforces.com/74165c03ee99a48531f2884923fb0eca0a3ed95c.png)
     46 
     47 ![](https://espresso.codeforces.com/361b5ddb32a2f6e6b7b08c37529cbfaba4c557e8.png)
     48 
     49 ![](https://espresso.codeforces.com/261f2243be0a4f58452af0d5fff1574eb2cfa21c.png)
     50 
     51 Now, ![](https://espresso.codeforces.com/e4bbec8d92a9d8f2793a6c676e7bdb4b9861febc.png)
     52 
     53 As you see, we can just maintain the sum of a Geometric progression ![](https://espresso.codeforces.com/c352243018dddc1b13fef4dff1aec018f2346882.png)
     54 
     55 This is a simple problem which can be solved with segment tree in ![](https://espresso.codeforces.com/bc388b4749e955d570e54c39371c71da3833854a.png).
     56 
     57 ### [446D - DZY любит игры](/contest/446/problem/D "Codeforces Round FF (Div. 1)")
     58 
     59 Define important room as the trap room. Let *w*(*u*, *v*) be equal to the probability that DZY starts at *u* (*u* is a important room or *u*=1) and *v* is the next important room DZY arrived. For each *u*, we can calculate *w*(*u*, *v*) in *O*(*n*3) by gauss elimination.
     60 
     61 Let *A**i* be equal to the *i*'th important room DZY arrived. So *A**k* - 1 = *n*, specially *A*0 = 1. Let *ans* be the probability for DZY to open the bonus round. Easily we can know ![](https://espresso.codeforces.com/4bec8112327906f3fa98fcfc878e11a10fdb0fe4.png). So we can calculate ans in ![](https://espresso.codeforces.com/ed70f516d4c49d0ef6343de94d6745402167eacc.png)(*a* is equal to the number of important rooms) by matrix multiplication.
     62 
     63 So we can solve the problem in ![](https://espresso.codeforces.com/57adebfccd8c96a1f8c6b8845970c6288517ff40.png). we should optimize this algorithm.
     64 
     65 We can find that each time we do gauss elimination, the variable matrix is unchanged. So we can do gauss elimination once to do preprocessing in *O*(*n*3). Then for each time calculating *w*(*u*, *v*), the only thing to do is substitute the constants. In this way we can calculate *w*(*u*, *v*) in *O*(*n*3).
     66 
     67 In this way, we can solve this problem in ![](https://espresso.codeforces.com/879e176ccdc7bca5daa89998eaa4b51fd8b4ca6f.png)
     68 
     69 ### [446E - DZY любит мосты](/contest/446/problem/E "Codeforces Round FF (Div. 1)")
     70 
     71 Let *n* = 2*m*. For convenience, we use indices 0, 1, ..., *n* - 1 here instead of 1, 2, ..., *n*, so we define *a*0 = *a**n*.
     72 
     73 Obviously this problem requires matrix multiplication. We define row vector ![](https://espresso.codeforces.com/d8ee612303fbff4dc4c6acf6ea5c620f7f915cc0.png), and matrix ![](https://espresso.codeforces.com/99b4ab3a9ba325e66dbd59b6f4db366428472415.png), where *b**ii* = 1, ![](https://espresso.codeforces.com/b505c545e4c445e6b4f4d39056fa62d3c2af5fb2.png). The answer is row vector ![](https://espresso.codeforces.com/e592e144133418f3f6162a10dd3d8463a5c1a102.png).
     74 
     75 Since *n* can be up to 3 × 107, we need a more efficient way to calculate. Let ![](https://espresso.codeforces.com/642eb16568a1dd9c1b96df0092c33064614c0c24.png) denote the matrix ![](https://espresso.codeforces.com/de776aa2e035581b1f2e881483c3fb7168854a50.png) when *m* = *k*. For example, ![](https://espresso.codeforces.com/9f94143a5ea97df0c1cf3cb4e26f38b2e652f1e7.png)
     76 
     77 Define ![](https://espresso.codeforces.com/762ea027255574db71a84d088a454c277e0401ba.png), then we can easily find that
     78 
     79 ![](https://espresso.codeforces.com/de32074351c480b6f35ac873da8895dd53b907bd.png)
     80 
     81 where ![](https://espresso.codeforces.com/c273659e4e66e4b8e5f533bc582ff3ae25c0ca06.png) denotes the identity matrix.
     82 
     83 For an *n* × *n* matrix ![](https://espresso.codeforces.com/54605f7ec9dfeb8fb9b3d436e6d7669771017734.png) and a constant *r*, we can prove by induction that ![](https://espresso.codeforces.com/4c05980181cacd5634a45aaad31641116e66489a.png)
     84 
     85 Let α1, α2 be two 1 × *n* vectors, then we have ![](https://espresso.codeforces.com/ce2e6b8a58331f3e8ece0015fad89a478340d3ee.png)
     86 
     87 This result seems useful. Suppose we want to find ![](https://espresso.codeforces.com/11adf4b68c80ca6ecdd87a9e894cc8b3b9b09059.png), where ![](https://espresso.codeforces.com/5460d8a5ad7a4cef2333af6bae493f8cc867477e.png), we have
     88 
     89 ![](https://espresso.codeforces.com/ebd6d6a92c4b3c2811f42bbedc1bb81bc568379a.png) so we just need to find ![](https://espresso.codeforces.com/93f55020acc340e6f2873761950b3fdb3b7173f5.png), which is a self-similar problem. By recursion, it can be solved in time *T*(*n*) = *T*(*n* / 2) + *O*(*n*) = *O*(*n*).