codeforces-scrape

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

205.md (9870B)


      1 Source: https://codeforces.com/blog/entry/4849
      2 
      3 ### [205A - Little Elephant and Rozdil](/contest/205/problem/A "Codeforces Round 129 (Div. 2)")
      4 
      5 This problem was the simplest in the problemset. All you need to do is just to sort all distances (keeping track on all indices). If the first two distances are equal, just output "Still Rozdil", otherwise output the index of the first element of the array.
      6 
      7 The complexity is *O*(*NlogN*).
      8 
      9 ### [205B - Little Elephant and Sorting](/contest/205/problem/B "Codeforces Round 129 (Div. 2)")
     10 
     11 In this problem you need to notice the fact (which can be proven, but it is almost obvious) that if you are doing some operation for interval from *l* to *r* (inclusive), *r* must be equal to *n*. This is becuase when you add something to all right part the answer can't be worse. After that you need to go from left to right and greedly add appropriate number of turns.
     12 
     13 The complexity is *O*(*N*).
     14 
     15 ### [205C - Little Elephant and Interval](/contest/205/problem/C "Codeforces Round 129 (Div. 2)")
     16 
     17 It is well-known that for such problem you need to write function *F*(*x*) which solves the problem for the interval 0..*x*, and the answer then is *F*(*r*) - *F*(*l* - 1).
     18 
     19 Now you need to write *F*(*x*) function. If *x* < 10, then answer is, of course, equal to *x*. Otherwise, let *len* be the length of *x*, *x*' — the integer *x* but without first and last digits, *x**i* — the *i*-th digit of integer *x* (from left to right, starting from 0). Interate through all possible first digit *d* (which is the last at the same time) and through the length *i* of the number. Then if *i* < *len* - 2 or (*i* = *len* - 2 and *d* < *x*0) you need to add 10*i* to the answer. Otherwise, if *i* = *len* - 2 and *d* = *x*0 you need to add *x*' to the answer. Finally, if *i* = *len* - 2 and *d* = *x*0 and *x**len* - 1 ≥ *d* add 1 to the answer.
     20 
     21 This problems also can be solved using DP.
     22 
     23 ### [205D - Little Elephant and Cards](/contest/205/problem/D "Codeforces Round 129 (Div. 2)")
     24 
     25 It is nice to use the *map* structure in this problem, but you can solve it without *map* (using sorting and binary serach). Lets iterate through all possible colors that we have and suppose that this currect color is the one that will make our set funny. The minimal number through all this will be the answer. To find the minimal number of turns to make our set funny using current color we need to know two numbers: the number of cards with current color on the front side and the number of cards with the current color on back side (but not at the same time). Let it be integers *a* and *b*. Let *m* = (*n* + 1) / 2 — the minimal number of the same cards required to get the funny set. Then if *a* + *b* < *m* it is impossible to make set funny using current color at all. If *a* ≥ *m* then the answer is 0, otherwise the answer is *m* - *a*.
     26 
     27 ### [205E - Little Elephant and Furik and Rubik](/contest/205/problem/E "Codeforces Round 129 (Div. 2)")
     28 
     29 This problem is to find the expected value. Important fact here is the linearity of the expected value. This means that we can for each element of the first strings find the probability that exactly this element will me matched with some other (but, of course, equal) from the second string. The answer will be the sum of all such probabilities.
     30 
     31 Let the current character of the first string be the *i*-th character (1-based numeration). Firstly we try to solve problem in *O*(*N*2) time. Namely, as it was said above, we need to find the number of such pairs of substrings that *i*-th character (which is on probably some other position in substring) is the same as the corresponding character of the second substring. Iterate through all *j* (*j* ≤ *i*) such that *A**i* = *B**j*. The number of such pairs of substrings that have match in that characters is *j*(*n* - *i* + 1) (considering 1-based numeration). This is *O*(*N*2). And because we need to find the sum of such values for all possible *j*, we can rewrite it as *S**i*(*n* - *i* + 1), where *S**i* equals to the sum of all integers *j* (*j* ≤ *i*) that *A**i* = *B**i*. Array *S* can be simply computed in a linear time. Analogically you should process all indices to the right from *i*.
     32 
     33 After we know the number of pairs of substrings with the match with the *i*-th character (let it be *count*), the probability is *count* / *total*, where *total* is the total number of pair of substrings (it can be found by loop or with some simple formula).
     34 
     35 The comlexity is *O*(*N*).
     36 
     37 ### [204D - Little Elephant and Retro Strings](/contest/204/problem/D "Codeforces Round 129 (Div. 1)")
     38 
     39 Firstly we should solve following subproblem: for each prefix find the number of it's fillings such that there is no consecutive block of *k* characters *B*. Let it be *F*(*x*), where *x* is the index in of the last character if the prefix. Assing *F*(*x*) = *F*(*x* - 1) * *cnt*, where *cnt* = 2 if *S**x* = 'X' and 1 otherwise. After such assing there may be some bad filling included to *F*(*x*). Since we suppouse that *F*(*x* - 1) is caclulated correctly, all bad filling must contain blocks of *k* charcters *B* only at the end of the prefix (they may be included only if substring *S**x* - *k* + 1..*x* doesn't contain characters *W* and character *S**x* - *k* is not *B*). So, if it's possible, we must subtract from *F*(*x*) value *F*(*x* - *k* - 1), because it's exactly the number of bad fillings.
     40 
     41 With the same DP you should you calc the same values for suffixes (but this time changing *B* by *W* and vice versa).
     42 
     43 Now we should carefully calculate the result in such way that now repeatings occur. Let iterate (from right to left) through all possible positions of the first blocks of *k* characters *B* (this means that we suppose that no block occur to the left). Using our DP we can simply find the number of fillings of all characters to the left from that block in such way that no another blocks of *k* characters *B* occur. Considering *O*(*N*2) solutions, we can iterate through all possible indexes of the begging of the last block of *k* characters *W* (again we suppose that this blocks must be the last and no another may occur to the right) and agin using our DP count the number of fillings to the right. We don't care what is between that blocks, so we just multiply answer by 2^(the number of characters *X* between blocks). But, since we are going from right to the left, we can just keep tracking on all possible last blocks and get *O*(*N*) solution.
     44 
     45 ### [204E - Little Elephant and Strings](/contest/204/problem/E "Codeforces Round 129 (Div. 1)")
     46 
     47 To solve this problems we can use suffix array. More information about suffix arrays you can find in the Internet.
     48 
     49 Firstly, concatenate all strings into the one separating consecutive strings by some unique characters (it was also useful to not use strings, but arrays of integers). For example, three strings *abc*, *a*, *ab* may be concatenated in the following way: *abc*#*a*@*ab*. Now we should build suffix array using this total string, this allows to us to sort all cyclic shifts of the string. After that each cyclic shift will either begin with additional character or the character from the input strings.
     50 
     51 Notice now that to find the result we need to find for each cyclic shift (begging of which doesn't contain additional character) the largest size of it's prefix such that this prefix is substring of at least *k* different input strings. This value can be found by binary search, but for this we need some function *F*(*x*, *len*) which can answer the questions: how many input strings contain prefix of size *len* of *x* cyclic shift as a substring.
     52 
     53 How to make *F*(*x*, *len*)? Look at all cyclic shifts, prefix of size *len* of which is equal to preifx of size *len* of *x*-th shift. Since all shifts are sorted lexicoraphically, this set of shifts can be represented as integral [*l*;*r*] of indices of shifts (1 ≤ *l* ≤ *x* ≤ *r*). How to find *l* and *r*? For each pair of consecutive shifts we can find it's greatest common prefix (using properties of suffix array). Than *l* and *r* can be found using RMQ. For *l* we need to know the rigthmost pair of shift (but to the left from *x*) that their greatest common prefix is less than *len*. Analogically we can find *r*. After that we have interval [*l*;*r*] and we need to find the number of different input strings that belongs to the shifts from *l*-th to *r*-th (actually, we need to find the number of different integer on interval). But, notice that we dont need the exactly number of different integers, we need to know just it is at least *k* or not. So let *L*[*i*] equals to the greatest *j* (*j* ≤ *i*) such that the number of different integers on interval [*j*;*i*] is equal to *k*. Then if *L*[*r*] ≥ *l*, obiously, interval [*l*;*r*] will also contains at least *k* different. So *F*(*x*, *len*) is done.
     54 
     55 The only thing to done is to fill array *L*. This is pretty simple using *set* (but it is possible without it but using RMQ). We will go from left to righ at keep the indices of the last (the rightmost) *k* different integers in the *set*. If some integer comes, then (if it was earlier) we need to erase this previous index from set (if it was still in) and insert new current. While the size of set is greater than *k*, we should erase the minimal number from it. Then if in some position *i* the size of the set (after above changings) is equal to *k*, than *L*[*i*] is equal to the minimal number in set.
     56 
     57 Since we *O*(*N*) times use binary search, and function *F*(*x*, *len*) works in *O*(*logN*) time, the total complexity is *O*(*Nlog*2*N*).