codeforces-scrape

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

518.md (8991B)


      1 Source: https://codeforces.com/blog/entry/16598
      2 
      3 ## [517A — Vitaly and Strings](https://codeforces.com/problemset/problem/517/A)
      4 
      5 To solve this problem we can, for example, find string *next*, which lexicographically next to string *s* and check that string *next* is lexicographically less than string *t*. If string *next* is lexicographically smaller than string *t*, print string *next* and finish algorithm. If string *next* is equal to string *t* print *No* *such* *string*.
      6 
      7 To find string *next*, which lexicographically next to string *s*, at first we need to find maximal suffix of string *s*, consisting from letters '*z*', change all letters '*z*' in this suffix on letters '*a*', and then letter before this suffix increase on one. I.e. if before suffix was letter, for example, '*d*', we need to change it on letter '*e*'.
      8 
      9 Asymptotic behavior of this solution — *O*(|*s*|), where |*s*| — length of string *s*.
     10 
     11 ## [517B — Tanya and Postcard](https://codeforces.com/problemset/problem/517/B)
     12 
     13 To solve this problem at first will count array *cnt*[], where *cnt*[*c*] — how many times letter *c* found in string *t*. We will count two numbers *ans*1 and *ans*2 — how many times Tanya will shouts joyfully *YAY*! and how many times Tanya will says *WHOOPS*.
     14 
     15 Let's iterate on string *s* and if *cnt*[*s*[*i*]] > 0, then increase *ans*1 on one and decrease *cnt*[*s*[*i*]] on one.
     16 
     17 Then let's again iterate on string *s*. Let *c* is letter which equal to *s*[*i*],but in the opposite case for it. I. e. if *s*[*i*] = '*w*', then *c* = '*W*'. Now, if *cnt*[*c*] > 0, then increase *ans*2 on one and decrease *cnt*[*с*] on one.
     18 
     19 Now, print two numbers — *ans*1 and *ans*2.
     20 
     21 Asymptotic behavior of this solution — *O*(|*s*| + |*t*|), where |*s*| — length of string *s* and |*t*| — length of string *t*.
     22 
     23 ## [517C — Anya and Smartphone](https://codeforces.com/problemset/problem/517/C)
     24 
     25 To solve this problem we will store two arrays — *a*[] and *pos*[]. In array *a*[] will store current order of icons, i. e. in *a*[*i*] store number of application, icon which stay on position *i*. In array *pos*[] will store on which place in list stays icons, i. e. in *pos*[*i*] store in which position of array *a*[] stay icon of application number *i*. We will count answer in variable *ans*.
     26 
     27 Let's iterate on applications which we need to open. Let current application has number *num*. Then to *ans* we need add (*pos*[*num*] / *k* + 1). Now, if icon of application number *num* doesn't stay on first position in list of applications, we make the following — swap *a*[*pos*[*num*]] and *a*[*pos*[*num*] - 1] and update values in array *pos*[] for indexes of two icons which numbers *a*[*pos*[*num*]] and *a*[*pos*[*num*] - 1] .
     28 
     29 Asymptotic behavior of this solution — *O*(*n* + *m*), where *n* — number of applications, *m* — number of requests to start applications.
     30 
     31 ## [517D — Ilya and Escalator](https://codeforces.com/problemset/problem/517/D)
     32 
     33 To solve this problem let's use dynamic programming. We will store two-dimensional array *z*[][] with type *double*. In *z*[*i*][*j*] will store the likelihood that after *i* seconds *j* people are on escalator.
     34 
     35 In dynamic will be following transitions. If *j* = *n*, i. e. all *n* people already on escalator then we make transition *z*[*i* + 1][*j*] +  = *z*[*i*][*j*]. Else, or person number *j* go to escalator in *i* + 1 second, i. e. *z*[*i* + 1][*j* + 1] +  = *z*[*i*][*j*] * *p*, or person number *j* stays on his place, i. e. *z*[*i* + 1][*j*] +  = *z*[*i*][*j*] * (1 – *p*).
     36 
     37 Now we need to count answer — it is sum on *j* from 0 to *n* inclusive *z*[*t*][*j*] * *j*.
     38 
     39 Asymptotic behavior of this solution — *O*(*t* * *n*), where *t* — on which moment we must count answer, *n* — how many people stay before escalator in the beginning.
     40 
     41 ## [517E — Arthur and Questions](https://codeforces.com/problemset/problem/517/E)
     42 
     43 At first let's take two sums *a*1 + *a*2 + ... + *a**k* and *a*2 + *a*3 + ... + *a**k* + 1. It is correct that *a*1 + *a*2 + ... + *a**k* < *a*2 + *a*3 + ... + *a**k* + 1. If move from right to left all elements apart from *a**k* + 1, all of them will reduce and will left only *a*1 < *a**k* + 1. If write further all sums we will obtain that sequence disintegrate on *k* disjoint chains: *a*1 < *a**k* + 1 < *a*2*k* + 1 < *a*3*k* + 1..., *a*2 < *a**k* + 2 < *a*2*k* + 2 < *a*3*k* + 2..., ..., *a**k* < *a*2*k* < *a*3*k*....
     44 
     45 We will solve the problem for every chain separately. Let's iterate on first chain and find all pair of indexes *i*, *j* (*i* < *j*), that *a*[*i*] and *a*[*j*] are numbers (not questions) in given sequence, and for all *k* from *i* + 1 to *j* - 1 in *a*[*k*] stay questions. All this questions we need to change on numbers so does not violate the terms of the increase and minimize sum of absolute values of this numbers.
     46 
     47 Between indexes *i* and *j* stay *j* - *i* - 1 questions, we can change them on *a*[*j*] - *a*[*i*] - 1 numbers. If *j* - *i* - 1 > *a*[*j*] - *a*[*i*] - 1, then we need to print *Incorrect* *sequence* and finish algorithm. Else we need to change all this questions to numbers in greedy way.
     48 
     49 Here we have several cases. Will review one case when *a*[*i*] >  = 0 and *a*[*j*] >  = 0. Let current chain (3, ?, ?, ?, 9), *i* = 1, *j* = 5. We need to change questions on numbers in the following way — (3, 4, 5, 6, 9). In other cases (when *a*[*i*] <  = 0, *a*[*j*] <  = 0 and when *a*[*i*] <  = 0, *a*[*j*] >  = 0) we need to use greedy similary to first so does not violate the terms of the increase and minimize sum of absolute values of this numbers.
     50 
     51 Asymptotic behavior of this solution — *O*(*n*), where *n* — count of elements in given sequence.
     52 
     53 ## [517F — Pasha and Pipe](https://codeforces.com/problemset/problem/517/F)
     54 
     55 At first let's count two two-dimensional arrays of prefix sums *sumv*[][] and *sumg*[][]. In *sumv*[*i*][*j*] store how many grids are in column *j* beginning from row 1 to row *i*. In *sumg*[*i*][*j*] store how many grid are in row *i* beginning from column 1 to column *j*.
     56 
     57 Let's count *ans*0 — how many pipes without bending we can pave. Count how many vertical pipes — we can pave. Iterate on *j* from 2 to *m* — 1 and, if *sumg*[*n*][*j*] — *sumg*[*n*][0] = 0 (i. e. in this column zero grids), increase *ans*0 on one. Similary count number of horizontal pipes.
     58 
     59 Let's count *ans*1 — how many pipes with 1 bending we can pave. We need to brute cell, in which will bending. There are four cases. Let's consider first case, others we can count similary. This case — pipe begin in left column, go to current cell in brute and then go to top row. If brute cell in row *i* and column *j* then to *ans*1 we need to add one, if (*sumg*[*i*][*j*] — *sumg*[*i*][0]) + (*sumv*[*i*][*j*] — *sumv*[0][*j*]) = 0.
     60 
     61 Let's count *ans*2 — how many pipes with 2 bendings we can pave. Let's count how many tunes begin from top row and end in top or bottom row and add this number to *ans*2. Then rotate our matrix three times on 90 degrees and after every rotate add to *ans*2 count of pipes, which begin from top row and end in top or bottom row. Then we need divide *ans*2 to 2, because every pipe will count twice.
     62 
     63 How we can count to current matrix how many pipes begin from top row and end in top or bottom row? Let's count four two-dimension arrays *lf*[][], *rg*[][], *sumUp*[][], *sumDown*[][]. If *i* — number of row, *j* — number of column of current cell, then in position (*i*, *lf*[*i*][*j*]) in matrix are nearest from left grid for cell (*i*, *j*), and in position (*i*, *rg*[*i*][*j*]) in matrix are nearest from right grid for cell (*i*, *j*). *sumUp*[*i*][*j*] — how many columns without grids are in submatrix from (1, 1) to (*i*, *j*) of given matrix. *sumDown*[*i*][*j*] — how many columns without grids are in submatrix from (*i*, 1) to (*n*, *j*) of given matrix. Then let's brute cell in which will be the first bending of pipe (pipe goes from top row and in this cell turned to left or to right), check, that in column *j* above this cell 0 grids, with help of arrays *lf* and *rg* find out as far as pipe can go to left or to right and with help of arrays *sumUp* and *sumDown* carefully update answer.
     64 
     65 Now print number *ans*1 + *ans*2 + *ans*3.
     66 
     67 Asymptotic behavior of this solution — *O*(*n* * *m* * *const*), where *n* — hoew many rows in given matrix, *m* — how many columns in given matrix, *const* takes different values depending on the implementation, in solution from editorial *const* = 10.