codeforces-scrape

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

351.md (6216B)


      1 Source: https://codeforces.com/blog/entry/9070
      2 
      3 ### Editorial for Codeforces Round #204
      4 
      5 #### [352A - Jeff and Digits](/contest/352/problem/A "Codeforces Round 204 (Div. 2)")
      6 
      7 Solution is looking for few cases:  
      8 1. If we do not have zeros, then the answer is -1.  
      9 2. If we have less than 9 fives, then the answer is 0.  
     10 3. Otherwise, the answer is:  
     11 4. 1. The maximum number of fives divisible by 9  
     12 4. 2. All zeros, we have
     13 
     14 #### [352B - Jeff and Periods](/contest/352/problem/B "Codeforces Round 204 (Div. 2)")
     15 
     16 We will go through the array from left to right. At each step, we will store the arrays:  
     17 1. *next**x* — the last occurrence of the number *x*  
     18 2. *period**x* — period, which occurs *x*  
     19 3. *fail**x* — whether a time when the number of *x* no longer fit
     20 
     21 Now, when we get a new number we considering the case when it is the first, second or occurred more than twice.  
     22 All the cases described in any past system testing solution.
     23 
     24 #### [351A - Jeff and Rounding](/contest/351/problem/A "Codeforces Round 204 (Div. 1)")
     25 
     26 Initially, we should remember the number of integers — *C*. On next step we will round down all numbers and count the sum. Now we can change the sum, rounding up some numbers, with those not matter what kind of, the main thing — how many. Consider a couple what we could get:  
     27 1. (*int*, *int*) (*c*1)  
     28 2. (*int*, *double*) (*c*2)  
     29 3. (*double*, *int*) (*c*3)  
     30 4. (*double*, *double*) (*c*4)
     31 
     32 Iterate over the number of pairs of the first type. Then we know the total number of second and third type and number of the fourth type:  
     33 1. *c*2 + *c*3 = *C* - 2*c*1  
     34 2. *c*4 = *N* - (*c*1  +  *c*2  +  *c*3)  
     35 Check to see if you can get such numbers (enough for us count of integers and real numbers, respectively). We find that we can round up from *c*4 to *c*4 + *c*2 + *c*3 numbers. We will find the best choise.
     36 
     37 #### [351B - Jeff and Furik](/contest/351/problem/B "Codeforces Round 204 (Div. 1)")
     38 
     39 ote that after each step, the number of inversions in the permutation is changed by **1**. Let us turn to the inversions of the permutation — let them be *I* pcs. It is clear that when we have one inversion, then the answer — 1. Now we will see how to use it further:  
     40 1. it is clear that after a Jeff's step inversions will become lower by 1  
     41 2. it is clear that after a Furik's step inversions will be on 1 lowerwith porbability of 0, 5, and on 1 greater with probability of 0, 5.  
     42 3. we have the formula for an answer *ans**I* = 1 + 1 + *ans**I* - 1 - 1 × 0.5 + *ans**I* - 1 + 1 × 0.5  
     43 4. after transformation we have *ans**I* = 4 + *ans**I* - 2.
     44 
     45 #### [351C - Jeff and Brackets](/contest/351/problem/C "Codeforces Round 204 (Div. 1)")
     46 
     47 How to solve the problem for small *NM*? Just use the dynamic programming *dp**i*, *j* — minimum cost to build *i* first brackets with the balance *j*. Transfers are simple:  
     48 1. *dp**i*, *j* + *a**i* + 1 -> *dp**i* + 1, *j* + 1  
     49 2. *dp**i*, *j* + *b**i* + 1 -> *dp**i* + 1, *j* - 1  
     50 3. we make transfers only when balance will be non-negative  
     51 4. starting state *dp*0, 0 = 0
     52 
     53 In this problem, we can assume that the balance will never exceed 2*N*. The proof is left as homework.
     54 
     55 And by using this fact problem can be done by erecting a matrix to the power:  
     56 1. lets *T**i*, *j* — cost of transfer from balance *i* to balance *j*, using *N* brackets  
     57 2. (*T**M*)0, 0 — answer to the problem
     58 
     59 #### [351D - Jeff and Removing Periods](/contest/351/problem/D "Codeforces Round 204 (Div. 1)")
     60 
     61 After the first request we can sort the numbers and for further moves will be able to remove all occurrences of a certain number. So the answer is the number of different numbers + 1 if there is no number, occurrence of which form an arithmetic progression.
     62 
     63 Number of different numbers on a segment — standart problem, can be done *O*(*N*1.5) with offline algorithm.
     64 
     65 The problem about finding the right number will be solved in a similar algorithm:  
     66 1. lets sort queries like pairs (*l**i* / 300, *r**i*), we use integer dividing  
     67 2. learn how to move from the interval (*l*, *r*) to intervals (*l* - 1, *r*), (*l* + 1, *r*), (*l*, *r* - 1), (*l*, *r* + 1) with complexcity *O*(1)  
     68 3. by means of such an operation will move from one segment to the next, in the amount of the operation algorithm will works *O*(*N*1.5)
     69 
     70 It remains to learn how to make the change on the interval by 1 element. Such a problem can be solved quite simply:  
     71 1. we craete *deque* for all value of numbers in array  
     72 2. depending on changes in the segment will add / remove items to the start / end of the respective *deque*  
     73 3. check whether the resulting *deque* is arithmetic progression. it will be homework.
     74 
     75 #### [351E - Jeff and Permutation](/contest/351/problem/E "Codeforces Round 204 (Div. 1)")
     76 
     77 We make the zero step, replace the elements on their modules.
     78 
     79 The first thing you need to understand the way in which we will build our response. After selecting a few ways to understand the fact that initially you need to determine the sign of the largest numbers.
     80 
     81 Consider the case where the current step we have only one maximal element. It is clear that if you put a sign - all the elements on the left of this will form an inversion, while on the right there will be no inversions. If we do not put a sign - it will all be the opposite. We select the best one and cross out the number of the array, it will not affect to some inversion.
     82 
     83 Now we should understand how to read the response when the highs more than one. We write the dynamics **dp[i][j]** — how much inversions can you get, when we looked at the first **i** higest values and **j** from them lefted as possitive. Of these dynamics is not difficult to make the transition and get the answer.
     84 
     85 And so we have a simple and short algorithm:  
     86 1. Iterates until the array is not empty  
     87 2. Find all the maximal elements  
     88 3. Calculate dynamics and find right signs  
     89 4. Remove elements from an array
     90 
     91 #### *For more details view any passed system tests solution.*