codeforces-scrape

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

676.md (3308B)


      1 Source: https://codeforces.com/blog/entry/45018
      2 
      3 ### [676A - Nicholas and Permutation](/contest/676/problem/A "Codeforces Round 354 (Div. 2)")
      4 
      5 All what you need to solve this problem — find the positions of numbers 1 and *n* in the given array. Let's this positions equal to *p*1 and *p**n*, then the answer is the maximum of 4 values:
      6 
      7 *abs*(*n* - *p*1),  *abs*(*n* - *p**n*),  *abs*(1 - *p*1),  *abs*(1 - *p**n*).
      8 
      9 Asymptotic behavior *O*(*n*).
     10 
     11 ### [676B - Pyramid of Glasses](/contest/676/problem/B "Codeforces Round 354 (Div. 2)")
     12 
     13 The restrictions in this problem allow to simulate the process. Let the volume of one wineglass equals to 2*n* conventional units. So the volume of the champagne surpluses which will stream to bottom level will always integer number. So let's pour in the top wineglass *q* * 2*n* units of champagne, and then we have following case: if in the current wineglass is more champagne than its volume, let's make *surplus* = *V**tek* - 2*n*, and add *surplus* / 2 of champagne in each of the two bottom wineglasses.
     14 
     15 Asymptotic behavior *O*(*n*2).
     16 
     17 ### [676C - Vasya and String](/contest/676/problem/C "Codeforces Round 354 (Div. 2)")
     18 
     19 This problem can be solved with help of two pointers. Let the first pointer is *l* and the second pointer is *r*. Then for every position *l* we will move right end *r* until on the substring *s**l**s**l* + 1... *s**r* it is possible to make no more than *k* swaps to make this substring beautiful. Then we need to update the answer with length of this substring and move *l* to the right.
     20 
     21 Asymptotic behavior *O*(*n* * *alphabet*).
     22 
     23 ### [676D - Theseus and labyrinth](/contest/676/problem/D "Codeforces Round 354 (Div. 2)")
     24 
     25 It is easy to understand that we have only 4 states of the maze. How to solve this problem if there is no any buttons? It is just bfs on the maze (on the graph). Because of buttons we need to add to graph 3 additional levels and add edges between this levels. After that we need to run bfs on this graph and find the length of the minimum path if such exists.
     26 
     27 Asymptotic behavior *O*(*n* * *m*).
     28 
     29 ### [676E - The Last Fight Between Human and AI](/contest/676/problem/E "Codeforces Round 354 (Div. 2)")
     30 
     31 In this problem we have two main cases: *k* = 0,  *k* ≠ 0.
     32 
     33 1. Case when *k* = 0. Then the division of the polynomial to the *x* - *k* depends only of the value of *a*0. If *a*0 is already known then we need to compare it with zero. If *a*0 = 0 then the human wins, otherwise the human loses. If *a**i* is not known then win who make the move.
     34 2. Case when *k* ≠ 0. Here we have two cases: all coefficients already known. Then we need to check *x* = *k* — is it the root of the given polynomial. Otherwise who will make the last move will win. Let we know all coefficient except one. Let this coefficient is the coefficient before *x**i*. Let *C*1 is the sum for all *j* ≠ *i*  *a**j**k**j* and *C*2 = *k**i* ≠ 0. Then we have the equation *a**i* * *C*2 =  - *C*1 which always have the solution. If the human will make the last move he need to write the root to the place of the coefficient, otherwise computer will write any number, but not the root.
     35 
     36 Asymptotic behavior *O*(*n*).