codeforces-scrape

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

476.md (16127B)


      1 Source: https://codeforces.com/blog/entry/14256
      2 
      3 First I want to thank all the problem solvers!  
      4  Hope you had or are going to have a good time with Dreamoon!
      5 
      6 If you think there's something that can be improved in this editorial please let me know!
      7 
      8 Definitions used in this editorial:  
      9  ⌈⌉ stands for ceiling function.  
     10  ⌊⌋ stands for floor function.  
     11  ![](https://espresso.codeforces.com/a7487d7e62f90136b78ae3fbf0a008396f146e13.png) stands for real division.  
     12  For non-negative integer *a* and positive integer *b*, *div*(*a*, *b*) stands for integral division, ![](https://espresso.codeforces.com/ecf5a5b0cc9134e021d3226d2a3351af6931f766.png).  
     13  For non-negative integer *a* and positive integer *b*, *mod*(*a*, *b*) stands for module operation, *a* = *div*(*a*, *b*) * *b* + *mod*(*a*, *b*).  
     14  *length*(*string*) is the length of *string*.  
     15  For non-negative integer *a* ≤ *b*, *A*[*a*..*b*] stands for the set of *A*[*a*], *A*[*a* + 1], *A*[*a* + 2]... *A*[*b* - 1] when *A* is an array and the substring of *A* consists of *a**th* to (*b* - 1)*th* character(inclusive) of *A* when *A* is a string. For such substring we have *length*(*A*[*a*..*b*]) = *b* - *a*.  
     16  *C*(*a*, *b*) stands for the combination function, the ways of selecting a elements from a group of b elements.
     17 
     18 [476A - Dreamoon and Stairs](/contest/476/problem/A "Codeforces Round 272 (Div. 2)")  
     19  We can show that the maximum number of moves possible is n and minimal moves needed is ![](https://espresso.codeforces.com/ddb3724dfe86122a90456ba01b63e009b59027a6.png), so the problem equals to determine the minimal integer that is a multiple of m in the range ![](https://espresso.codeforces.com/b7866867aa6b92d1737157fea7e46540d9715863.png).  
     20  One way to find the minimal number which is a multiple of m and greater than or equal to a number x is ![](https://espresso.codeforces.com/3a31a4515898ee8aefe8a58bdd6bf8c42605d31f.png), we can compare this number to the upper bound n to determine if there is a valid solution.  
     21  Although best practice is *O*(1), *O*(*n*) enumeration of each possible number of moves would also work.  
     22  time complexity: *O*(1)  
     23  sample code: [8212169](/contest/476/submission/8212169 "Submission 8212169 by drazil")  
     24  explanation of sample code:  
     25  The ![](https://espresso.codeforces.com/1f831d5eb31c75ce28fbf28e4162c1b8e3bd0d06.png) can be calculated in the following c++ code if *a* is non-negative and *b* is positive: `(a+b-1)/b`  
     26 Because `/` in c++ is integral division so `(a+b-1)/b` would result in ![](https://espresso.codeforces.com/532a6507db54577ae0558c8abca06f5192866545.png)  
     27  Let *a* = *div*(*a*, *b*)*b* + *mod*(*a*, *b*) = *db* + *m*, ![](https://espresso.codeforces.com/f07d0873192c2376eecb0aaa8c9e17ad530e67c8.png).  
     28  Which means if ![](https://espresso.codeforces.com/466b017b9166560d3f78beed5d8c4a4b57cf3b9b.png), otherwise *div*(*a* + *b* - 1, *b*) = *d* + 1. Can be translated to if ![](https://espresso.codeforces.com/12dda13951bd7607d06b00ae1322aa6edd0009a5.png), otherwise *div*(*a* + *b* - 1, *b*) = *div*(*a*, *b*) + 1. Which matches the value of ![](https://espresso.codeforces.com/1f831d5eb31c75ce28fbf28e4162c1b8e3bd0d06.png).
     29 
     30 [476B - Dreamoon and WiFi](/contest/476/problem/B "Codeforces Round 272 (Div. 2)")  
     31  The order of moves won't change the final position, so we can move all '?'s to the end of the string.  
     32  We have the following information:  
     33  1. the correct final position  
     34  2. the position that Dreamoon will be before all '?'s  
     35  3. the number of '?'s  
     36  We can infer that the distance and direction dreamoon still needs to move in the '?' part from 1. and 2., and furthur translate that to how many +1s and -1s dreamoon will need to move.  
     37  What's left is a combinatorial problem, the probability would be ![](https://espresso.codeforces.com/d402fbe31f975efcdcae8bc2f9c9b05c6156419b.png).  
     38  So we can compute that formula within *O*(*n*) time assuming n is the length of commands, but since N is small so we can brute force every possible choice of '?' with some recursive or dfs like search in *O*(2*n*) time complexity.  
     39  Note that the problem asks for a precision of 10- 9, so one should output to 11 decimal places or more.  
     40  time complexity: *O*(*n*), assuming *n* is the length of commands.  
     41  sample code: [8215177](/contest/476/submission/8215177 "Submission 8215177 by drazil")
     42 
     43 [476C - Dreamoon and Sums](/contest/476/problem/C "Codeforces Round 272 (Div. 2)") / [477A - Dreamoon and Sums](/contest/477/problem/A "Codeforces Round 272 (Div. 1)")  
     44  If we fix the value of *k*, and let *d* = *div*(*x*, *b*), *m* = *mod*(*x*, *b*), we have :  
     45  *d* = *mk*  
     46  *x* = *db* + *m*  
     47  So we have *x* = *mkb* + *m* = (*kb* + 1) * *m*.  
     48  And we know *m* would be in range [1, *b* - 1] because it's a remainder and *x* is positive, so the sum of *x* of that fixed *k* would be ![](https://espresso.codeforces.com/ce8c122dab64273848ca2e4d30067482bc410273.png).  
     49  Next we should notice that if an integer *x* is *nice* it can only be *nice* for a single particular *k* because a given *x* uniquely defines *div*(*x*, *b*) and *mod*(*x*, *b*).  
     50  Thus the final answer would be sum up for all individual *k*: ![](https://espresso.codeforces.com/04dd59efc46d351d44bb04c75be16e55de567c89.png) which can be calculated in *O*(*a*) and will pass the time limit of 1.5 seconds.  
     51  Also the formula above can be expanded to ![](https://espresso.codeforces.com/d6c2ee2216301957ab4c922a921826b94f73c995.png). Dreamoon says he's too lazy to do this part, so if you use *O*(1) solution you just computed the answer faster than Dreamoon!!!  
     52  Note that no matter which approach one should be very careful of overflowing of the integer data type of the used language. For example one should do a module after every multiplication if using 64-bit integer type. And pay attention to precedence of operations: take c++ for example a+b%c would be executed as a+(b%c) instead of (a+b)%c, another c++ example a*(b*c)%m would be executed as (a*(b*c))%m instead of a*((b*c)%m).  
     53  Thanks [saurabhsuniljain](/profile/saurabhsuniljain "Expert saurabhsuniljain") for pointing out the preceding problem and examples in the comment!  
     54  time complexity: *O*(1)  
     55  sample code: [8215188](/contest/476/submission/8215188 "Submission 8215188 by drazil")
     56 
     57 [476D - Dreamoon and Sets](/contest/476/problem/D "Codeforces Round 272 (Div. 2)") / [477B - Dreamoon and Sets](/contest/477/problem/B "Codeforces Round 272 (Div. 1)")  
     58  The first observation is that if we divide each number in a set by *k*, than the set would be rank 1. So we could find *n* sets of rank 1 then multiple every number by *k*.  
     59  For how to find *n* sets of rank 1, we can use {6*a* + 1, 6*a* + 2, 6*a* + 3, 6*a* + 5} as a valid rank 1 set and take *a* = 0 to *n* - 1 to form *n* sets and thus *m* = (6*n* - 1) * *k*.  
     60  The proof that *m* is minimal can be shown by the fact that we take three consecutive odd numbers in each set. If we take less odd numbers there will be more than 1 even number in a set which their gcd is obviously a multiple of 2. And if we take more odd numbers *m* would be larger.  
     61  The output method is straight forward. Overall time complexity is *O*(*n*).  
     62  time complexity: *O*(*n*)  
     63  sample code: [8215198](/contest/476/submission/8215198 "Submission 8215198 by drazil")
     64 
     65 [476E - Dreamoon and Strings](/contest/476/problem/E "Codeforces Round 272 (Div. 2)") / [477C - Dreamoon and Strings](/contest/477/problem/C "Codeforces Round 272 (Div. 1)")  
     66  First let *A*[*i*] to be the minimal length *L* needed so that substring *s*[*i*..*i* + *L*] can become pattern *p* by removing some characters. We can calculate this greedily by keep selecting next occurrence of characters in *p* in *O*(*length*(*s*)) time for a fixed *i*, so for all *i* requires *O*(*length*(*s*)2).  
     67  Next we can do a dp *D*[*i*][*j*] where *D*[*i*] is the answer array for *s*[0..*i*]. *D*[*i*] can contribute to *D*[*i* + 1] with 0 or 1 removal and to *D*[*i* + *A*[*i*]] with *A*[*i*] - *length*(*p*) removal(s). In other words, *D*[*i*][*j*] can transition into tree relations *D*[*i* + 1][*j*] = *D*[*i*][*j*] //not delete *s*[*i*], *D*[*i* + 1][*j* + 1] = *D*[*i*][*j*] //delete *s*[*i*], and *D*[*i* + *A*[*i*]][*j* + *A*[*i*] - *length*(*p*)] = *D*[*i*][*j*] + 1 //form a substring *p* by deleting *A*[*i*] - *length*(*p*) characters. Calculate forwardly from *D*[0] to *D*[*length*(*s*) - 1] gives the final answer array as *D*[*length*(*s*)]. Calculating *D*[*i*] requires *O*(*length*(*s*)) time for a fixed *i*, so for all *i* takes *O*(*length*(*s*)2) time.  
     68  time complexity: *O*(*n*2), *n* = *length*(*s*)  
     69  sample code: [8215203](/contest/476/submission/8215203 "Submission 8215203 by drazil")
     70 
     71 Another solution:  
     72  Let *k* = *div*(*length*(*s*), *length*(*p*)). We can run an edit distance like algorithm as following (omitting the details of initialization and boundary conditions):
     73 
     74 ```
     75 for(i=0;i<n;i++)
     76     for(j=0;j<k*p;j++)
     77         if(s[i]==p[j%length(p)])
     78             D[i][j] = D[i-1][j-1]
     79          D[i][j] = min(D[i][j], D[i-1][j] + (j%length(p)!=length(p)-1))
     80 ```
     81 
     82 That means remove cost is 1 when it is in the middle of a *p* and 0 elsewhere because *p* need to be consecutive(thus no need to be actually remove outside of a *p*). Then *D*[*n*][*t* * *length*(*p*)] is the minimal number of removals to have *t* non-overlapping substring of *p*. So we have *answer*[*D*[*n*][*t* * *length*(*p*)..(*t* + 1) * *length*(*p*)] = *t*. And after the maximal *t* is reached, decrease answer by 1 for every *length*(*p*).  
     83  time complexity: *O*(*n*2)  
     84  sample code: [8215394](/contest/476/submission/8215394 "Submission 8215394 by drazil")
     85 
     86 [477D - Dreamoon and Binary](/contest/477/problem/D "Codeforces Round 272 (Div. 1)")  
     87  Let *Xb* be the binary string of number *X*. An ideal sequence can be expressed as a partition of *Xb*: *P*1 = *Xb*[1..*p*1], *P*2 = *Xb*[*p*1..*p*2], ... *P**K* = *Xb*[*p**K* - 1..*length*(*Xb*)] where *P**i* ≤ *P**i* + 1. The length of operations of such sequence is *P**K* + *K*.  
     88  We can calculate the number of different ideal sequences by dp. State *D*[*i*][*j*] stands for the answer of state that we have print *Xb*[1..*j*] and last partition is *Xb*[*i*..*j*]. A possible way of transition is that a state *D*[*i*][*j*] can go to state *D*[*i*][*j* + 1] and *D*[*j*][*k*] where *k* is the minimal possible position such that value of *Xb*[*j*..*k*] is equal to or greater than the value of *Xb*[*i*..*j*] and *Xb*[*j*] is 1 since we can't print any leading 0.  
     89  Note that *D*[*j*][*k* + 1] can also derived from *D*[*i*][*j*] but it will covered by *D*[*i*][*j*] → *D*[*j*][*k*] → *D*[*j*][*k* + 1], so we don't need to consider this case to avoid redundant counts.  
     90  If we can determine *k* for each *i*, *j* pair in *O*(1) then we can compute this dp in *O*(*length*(*Xb*)2) in the following manner:
     91 
     92 ```
     93 for(j=0;j<n;j++)
     94     for(i=0;i<j;i++)
     95         compute the transitions of D[i][j]
     96 ```
     97 
     98 So let's look into how to calculate the value *k* for a given *i*, *j* pair. If the value of *Xb*[*j*..2*j* - *i*] is equal to or greater than *Xb*[*i*..*j*] than *k* is 2*j* - *i* because if *k* is less than 2*j* - *i* would make length of the new partition less than the previous partition thus its value would be lesser. And if *k* can't be 2*j* - *i*, the value of 2*j* - *i* + 1 is always a valid choice because it would make the length of the new partition greater than the previous one. So for each length *L* if we know the order of *Xb*[*i*..*i* + *L*] and *Xb*[*i* + *L*..*i* + 2*L*] in *O*(1) time we can calculate k in *O*(1) time(can be easily shown by assuming *L* = *j* - *i*).  
     99  One way of doing such is using prefix doubling algorithm for suffix array construction to build a RMQ structure for query in *O*(1) time. The prefix doubling algorithm requires *O*(*nlgn*) precompute time. Note there is still a various of ways to do this part of task in the same or better time complexties.  
    100  And for the shortest length part we can compute the minimal parts needed so far for each state along with the preivous dp. Then compare all states ends with *j* = *length*(*Xb*).  
    101  Overall we can solve this problem in *O*(*length*(*Xb*)2) with caution in details like boundaries and module operations.  
    102  time complexity: *O*(*n*2), *n* = *length*(*Xb*)  
    103  Note the sample code use a nlgnlgn version of prefix doubling algorithm  
    104  sample code: [8215216](/contest/477/submission/8215216 "Submission 8215216 by drazil")
    105 
    106 [477E - Dreamoon and Notepad](/contest/477/problem/E "Codeforces Round 272 (Div. 1)")  
    107  Although swapping two parts of a query would result in different answer, if we reverse the lines length alltogether then the answer would stay the same. So we only analyze queries where *r*2 ≥ *r*1.  
    108  The answers would comes in several types, we’ll discuss them one by one:  
    109  1. HOME key being pressed once: the answer will be 1(*HOME*) + *r*2 - *r*1(*down* *keys*) + *c*2(*right* *keys*). Note that this is the best answer if the HOME key is ever pressed once, so we won’t consider HOME key anymore. This step is *O*(1) for a single query, thus *O*(*q*) in total.  
    110  2. direct presses *r*2 - *r*1 down keys and no or one END key in those rows: because the cursor position will be reset to the row length if we go down to a row with length less than current cursor position, the possible positions that can be at row *p* if we start at end of each previous rows can be track with a stack. The position directly pressing only down keys from *r*1 to *r*2 is *min*(*c*1, *the* *length* *of* *first* *row* *after* *r*1 *in* *stack*). We can use a binary search to get the first row after or equal *r*1 in stack. From that row till *r*2 in the stack are the positions possible when pressing ONE END key (pressing more won’t get more possible positions), we can use a binary search to find the position closest to *c*2 which is the best. We can sort all queries and use *O*(*qlgn*) time for queries and *O*(*n*) time for maintaining stack, so *O*(*qlgn* + *n*) in total.  
    111  3. go back some rows and press one or no END key at the row: we only interested in END OF rows in stack constructed in 2.. We can use a binary search in stack to identify the range of rows interested. For those lengths of row less than *c*2(also can use a binary search to locate) we only need to consider the first one encountered(closest to *r*1), note still need to consider if it needs an END key for this case. For those lengths of row greater than or equal to *c*2, the answer would be *r*1 + *r*2 - 2 * (*row* *reached*) + (*length* *of* *the* *row*) - *c*2 + (1 *if* *length* *of* *the* *row* *greater* *than* *c*1). The terms related to row in the previous formula is 2 * (*row* *reached*) + (*length* *of* *the* *row*) + (1 *if* *length* *of* *the* *row* *greater* *than* *c*1). We can identify the range with and without +1(last term) and query in a segment tree of the minimal value of 2 * (*row* *reached*) + (*length* *of* *the* *row*) for each range. Thus the time need here is *O*(*nlgn*) for maintaining segment tree and *O*(*qlgn*) for query while sharing with the stack of 2., so *O*(*nlgn* + *qlgn*) in total.  
    112  4. go beyond r2 some rows and press no or one END at the row: this needs a reversed stack and very similar approach of 3.. The time complexity is the same as 2. and 3..  
    113  So the total time complexity is *O*((*n* + *q*)*lgn*), note this problem is very hard to get the code right.  
    114  time complexity: *O*((*n* + *q*)*lgn*)  
    115  sample code: [8212528](/contest/477/submission/8212528 "Submission 8212528 by dreamoon_love_AA")