670.md (7250B)
1 Source: https://codeforces.com/blog/entry/44715 2 3 ### [670A - Holidays](/contest/670/problem/A "Codeforces Round 350 (Div. 2)") 4 5 There are many ways to solve this problem. Let's talk about one of them. At first we need to write a function, which takes the start day of the year and calculate the number of days off in such year. To make it let's iterate on the days of the year and will check every day — is it day off or no. It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off. If the first day of the year equals to the first day off of the week (i.e. this day is Saturday) in this year will be maximum possible number of the days off. 6 7 ### [670B - Game of Robots](/contest/670/problem/B "Codeforces Round 350 (Div. 2)") 8 9 To solve this problem we need to brute how many identifiers will called robots in the order from left to right. Let's solve this problem in one indexing. Let the current robot will call *i* identifiers. If *k* - *i* > 0 let's make *k* = *k* - *i* and go to the next robot. Else we need to print *a*[*k*], where *a* is the array with robots identifiers and end our algorithm. 10 11 ### [670C - Cinema](/contest/670/problem/C "Codeforces Round 350 (Div. 2)") 12 13 We need to use *map*-ом (let's call it *cnt*) and calculate how many scientists knows every language (i. e. *cnt*[*i*] equals to the number of scientists who know the language number *i*). Let's use the pair *res*, where we will store the number of \textit{very pleased} scientists and the number of \textit{almost satisfied} scientists. At first let *res* = *make*_*pair*(0, 0). Now we need to iterate through all movies beginning from the first. Let the current movie has the number *i*. Then if *res* < *make*_*pair*(*cnt*[*b*[*i*]], *cnt*[*a*[*i*]]) let's make *res* = *make*_*pair*(*cnt*[*b*[*i*]], *cnt*[*c*[*i*]]) and update the answer with the number of current movie. 14 15 ### [670D1 - Magic Powder - 1](/contest/670/problem/D1 "Codeforces Round 350 (Div. 2)") 16 17 This problem with small constraints can be solved in the following way. Let's bake cookies one by one until it is possible. For every new cookie let's calculate *val* — how many grams of the magic powder we need to bake it. For this let's brute all ingredients and for the ingredient number *i* if *a*[*i*] ≤ *b*[*i*] let's make *b*[*i*] = *b*[*i*] - *a*[*i*], else let's make *b*[*i*] = 0 and *val* = *val* + *a*[*i*] - *b*[*i*]. When we bruted all ingredients if *val* > *k* than we can't bake more cookies. Else let's make *k* = *k* - *val* and go to bake new cookie. 18 19 ### [670D2 - Magic Powder - 2](/contest/670/problem/D2 "Codeforces Round 350 (Div. 2)") 20 21 Here we will use binary search on the answer. Let's we check the current answer equals to *cur*. Then the objective function must be realized in the following way. Let's store in the variable *cnt* how many grams of the magic powder we need to bake *cur* cookies. Let's iterate through the ingredients and the current ingredient has the number *i*. Then if *a*[*i*]·*cur* > *b*[*i*] let's make *cnt* = *cnt* + *a*[*i*]·*cur* - *b*[*i*]. If after looking on some ingredient *cnt* becomes more than *k* the objective function must return *false*. If there is no such an ingredient the objective function must return *true*. 22 23 If the objective function returned *true* we need to move the left end of the binary search to the *cur*, else we need to move the right end of the binary search to the *cur*. 24 25 ### [670E - Correct Bracket Sequence Editor](/contest/670/problem/E "Codeforces Round 350 (Div. 2)") 26 27 Let's solve this problem in the following way. At first with help of stack let's calculate the array *pos*, where *pos*[*i*] equals to the position of the bracket which paired for the bracket in the position *i*. Then we need to use two arrays *left* and *right*. Then *left*[*i*] will equals to the position of the closest to the left bracket which did not delete and *right*[*i*] will equals to the position of the closest to the right bracket which did not delete. If there are no such brackets we will store -1 in the appropriate position of the array. 28 29 Let's the current position of the cursor equals to *p*. Then if the current operation equals to \texttt{L} let's make *p* = *left*[*p*] and if the current operation equals to \texttt{R} let's make *p* = *right*[*p*]. We need now only to think how process the operation \texttt{D}. 30 31 Let *lf* equals to *p* and *rg* equals to *pos*[*p*]. If *lf* > *rg* let's swap them. Now we know the ends of the substring which we need to delete now. If *right*[*rg*] = = - 1 we need to move *p* to the left (*p* = *left*[*lf*]), else we need to move *p* to the right (*p* = *right*[*rg*]). Now we need to recalculate the links for the ends of the deleted substring. Here we need to check is there any brackets which we did not deleted to the left and to the right from the ends of the deleted substring. 32 33 To print the answer we need to find the position of the first bracket which we did not delete and go through all brackets which we did not delete (with help of the array *right*) and print all such brackets. To find the position of the first bracket which we did not delete we can store in the array all pairs of the ends of substrings which we deleted, then sort this array and find the needed position. Bonus: how we can find this position in the linear time? 34 35 ### [670F - Restore a Number](/contest/670/problem/F "Codeforces Round 350 (Div. 2)") 36 37 At first let's find the length of the Vasya's number. For make this let's brute it. Let the current length equals to *len*. Then if *len* equals to the difference between the length of the given string and the number of digits in *len* if means that *len* is a length of the Vasya's number. 38 39 Then we need to remove from the given string all digits which appeared in the number *len*, generate three strings from the remaining digits and choose smaller string from them — this string will be the answer. Let *t* is a substring which Vasya remembered. Which three strings do we need to generate? 40 41 1. Let's write the string *t* and after that let's write all remaining digits from the given string in the ascending order. This string can be build only if the string *t* does not begin with the digit 0. 42 2. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than the first digit in the *t* in the ascending order, then write the string *t* and then write all remaining digits in the ascending order. 43 3. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than or equal to the first digit in the *t* in the ascending order, then write the string *t* and then write all remaining digits in the ascending order. 44 45 Also we need to separately consider the case when the Vasya's number equals to zero.