536.md (14126B)
1 Source: https://codeforces.com/blog/entry/17401 2 3 ### [535A - Tavas and Nafas](/contest/535/problem/A "Codeforces Round 299 (Div. 2)") 4 5 First of all check if *n* is one of the values 0, 10, 11, …, 19. Then, let’s have array *x*[] = {"", "", "twenty", "thirty", …, "ninety"} and *y*[] = {"", "one", …, "nine"}. 6 7  8 9 Let  and *b* = *n* *modulo* 10. 10 11 If *n* is not one of the values above, then if *a* = 0, print *y*[*b*], else if *b* = 0 print *x*[*a*] otherwise print *x*[*a*]-*y*[*b*]. 12 13 Time complexity: *O*(1) 14 15 [Code](http://ideone.com/mytb2L) by [SoroushE](/profile/SoroushE "Master SoroushE") 16 17 [Another Code](http://ideone.com/CqgNe5) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 18 19 [Another Code](http://ideone.com/dqiMNL) by [Haghani](/profile/Haghani "Grandmaster Haghani") 20 21 [Python Code](http://ideone.com/6tZmNF) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 22 23 ### [535B - Tavas and SaDDas](/contest/535/problem/B "Codeforces Round 299 (Div. 2)") 24 25 Sol1: Consider *n* has *x* digits, *f*(*i*) = decimal representation of binary string *i*, *m* is a binary string of size *x* and its *i* - *th* digit is 0 if and only if the *i* - *th* digit of *n* is 4. Finally, answer equals to 21 + 22 + … + 2*x* - 1 + *f*(*m*) + 1. 26 27 Time complexity: *O*(*log*(*n*)) 28 29  30 31 Sol2: Count the number of lucky numbers less than or equal to *n* using bitmask (assign a binary string to each lucky number by replacing 4s with 0 and 7s with 1). 32 33 Time complexity: *O*(2*log*(*n*)) 34 35 [Code](http://ideone.com/RTzRZK) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 36 37 [Another Code](http://ideone.com/j6Gamw) by [SoroushE](/profile/SoroushE "Master SoroushE") 38 39 [Another Code](http://ideone.com/qKbG2Y) by [Haghani](/profile/Haghani "Grandmaster Haghani") 40 41 [Python Code](http://ideone.com/0fX8LQ) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 42 43 ### [536A - Tavas and Karafs](/contest/536/problem/A "Codeforces Round 299 (Div. 1)") 44 45 **Lemma:** Sequence *h*1, *h*2, …, *h**n* is (*m*, *t*) - Tavas-Eatable if and only if *max*(*h*1, *h*2, …, *h**n*) ≤ *t* and *h*1 + *h*2 + … + *h**n* ≤ *m* × *t*. 46 47 **Proof:** *only if* is obvious (if the sequence is Tavas-Eatable, then it fulfills the condition). 48 49 So we should prove that if the conditions are fulfilled, then the sequence is Tavas-Eatable. 50 51 Use induction on *h*1 + *h*2 + ... + *h**n*. Induction definition: the lemma above is true for every sequence *h* with sum of elements at most *k*. So now we should prove it for *h*1 + *h*2 + ... + *h**n* = *k* + 1. There are two cases: 52 53 1- There are at least *m* non-zero elements in the sequence. So, the number of elements equal to *t* is at most *m* (otherwise sum will exceed *m* × *t*). So, we decrease *m* maximum elements by 1. Maximum element will be at most *t* - 1 and sum will be at least *m* × *t* - *m* = *m*(*t* - 1). So according to the induction definition, the new sequence is (*m*, *t* - 1) - Tavas-Eatable, so *h* is (*m*, *t*) - Tavas-Eatable. 54 55 2- There are less than *m* non-zero elements in the sequence. We decrease them all by 1. Obviously, the new sequence has maximum element at most equal to *t* - 1 so its sum will be at most *m*(*t* - 1). So according to the induction definition, the new sequence is (*m*, *t* - 1) - Tavas-Eatable, so *h* is (*m*, *t*) - Tavas-Eatable. 56 57  58 59 For this problem, use binary search on *r* and use the fact that the sequence is non-decreasing and  . 60 61 Time complexity: *O*(*qlog*(*mt*)) 62 63 [Code](http://ideone.com/VyAw9l) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 64 65 [Another Code](http://ideone.com/IEYwEw) by [Haghani](/profile/Haghani "Grandmaster Haghani") 66 67 [Java Code](http://ideone.com/lcinCr) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 68 69 ### [536B - Tavas and Malekas](/contest/536/problem/B "Codeforces Round 299 (Div. 1)") 70 71 First of all you need to find uncovered positions in *s* (because rest of them will determine uniquely). If there is no parados in covered positions (a position should have more than one value), then the answer will be 0, otherwise it’s 26*uncovered*. To check this, you just need to check that no two consecutive matches in *s* have parados. So, for this purpose, you need to check if a prefix of *t* is equal to one of its suffixes in *O*(1). You can easily check this with prefix function (or Z function). 72 73  74 75 Time complexity: *O*(*n* + *m*) 76 77 [Code](http://ideone.com/hdKn12) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 78 79 [Another Code](http://ideone.com/ypEag6) by [Haghani](/profile/Haghani "Grandmaster Haghani") 80 81 [Java Code](http://ideone.com/AIjZhj) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 82 83 ### [536C - Tavas and Pashmaks](/contest/536/problem/C "Codeforces Round 299 (Div. 1)") 84 85 For each competitor put the point  in the Cartesian plane. So, the time a competitor finishes the match is . 86 87 Determine their convex hull(with maximum number of points. i.e it doesn’t matter to have π radians angle). Let *L* be the leftmost point on this convex hull (if there are more than one, choose the one with minimum *y* component). Similarly, let *D* be the point with minimum *y* component on this convex hull (if there are more than one, consider the leftmost). 88 89 Proof:  is the scalar product that is smaller if the point  is farther in the direction of (*S*, *R*). It's obvious that the farthest points in some direction among the given set lie on a convex hull. (*S*, *R*) can get any value that is vector in first quadrant. So we need the points on the convex hull that we actually calculate (also we know that the points on the right or top of the convex hull, are not in the answer, because they're always losers). 90 91  92 93 It’s easy to see that the answer is the points on the path from *D* to *L* on the convex hull (bottom-left arc). i.e the bottom-left part of the convex hull. 94 95 Time complexity: *O*(*nlog*(*n*)) 96 97 In this problem, we recommend you to use integers. How ? Look at the code below 98 99 [Code](http://ideone.com/ccMHza) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 100 101 In this code, function `CROSS` returns  (it's from order of 1016, so there won't be any overflows.) 102 103 In `double` version, you should have a very small epsilon. 104 105 [Code of double version](http://ideone.com/pcc5xc) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") 106 107 [Another Code With Lower Envelope of Lines](http://ideone.com/PTMgaW) by [Haghani](/profile/Haghani "Grandmaster Haghani") 108 109 [Java Code](http://ideone.com/mGeglg) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 110 111 ### [536D - Tavas in Kansas](/contest/536/problem/D "Codeforces Round 299 (Div. 1)") 112 113 For each vertex *v*, put a point (*dis*(*s*, *v*), *dis*(*v*, *t*)) with its point (score) in the Cartesian plane. The first player in his/her turn chooses a vertical line and erases all the points on its left side. Second player in his/her turn chooses a horizontal line and erases all the point below it. 114 115 Each player tries to maximize his/her score. 116 117 Obviously, each time a player chooses a line on the right/upper side of his/her last choice. Imagine that there are *A* different *x* components *x*1 < *x*2 < … < *x**A* and *B* different *y* components *y*1 < *y*2 < … < *y**B* among all these lines. So, we can show each state before the game ends with a pair (*a*, *b*) (1 ≤ *a* ≤ *A*, 1 ≤ *b* ≤ *B* It means that in this state a point (*X*, *Y*) is not erased yet if and only if *x**a* ≤ *X* and *y**b* ≤ *Y*). 118 119  120 121 So, using dp, *dp*[*a*][*b*][*i*] (1 ≤ *i* ≤ 2) is the maximum score of *i* - *th* player in state (*a*, *b*) and it’s *i* - *th* player’s turn. So, consider *s*[*a*][*b*] is the sum of the scores of all valid points in state (*a*, *b*) and *t*[*a*][*b*] is the amount of them. So, 122 123 If *i* = 1 then, *dp*[*a*][*b*][*i*] = *max*(*s*[*a*][*b*] - *dp*[*c*][*b*][2]) (*a* ≤ *c* ≤ *A*, *t*[*c*][*b*] < *t*[*a*][*b*]). 124 125 Otherwise *dp*[*a*][*b*][*i*] = *max*(*s*[*a*][*b*] - *dp*[*a*][*c*][1]) (*b* ≤ *c* ≤ *B*, *t*[*a*][*c*] < *t*[*a*][*b*]). 126 127 So we need two backward `for`s for our dp and another `for` on *i*. So, now the only thing that matters is updating the dp. For this purpose, we need two more arrays *QA* and *QB*. 128 129 *QA*[*b*][1] = the minimum value of pairs (*dp*[*j*][*b*][2], *t*[*j*][*b*]) and *QA*[*b*][2] = minimum value of pairs (*dp*[*j*][*b*][2], *t*[*j*][*b*]) such that *t*[*j*][*b*] > *QA*[*b*][1].*second* in the states we’ve seen so far. Similarly, *QB*[*a*][1] = the minimum value of pairs (*dp*[*a*][*j*][1], *t*[*a*][*j*]) and *QB*[*a*][2] = minimum value of pairs (*dp*[*a*][*j*][1], *t*[*a*][*j*]) such that *t*[*a*][*j*] > *QB*[*a*][1].*second* in the states we’ve seen so far. Now updating dp is pretty easy : 130 131 *dp*[*a*][*b*][1] = *s*[*a*][*b*] - (*t*[*a*][*b*] ≤ *QA*[*b*][1].*second*?*QA*[*b*][2].*first*: *QA*[*b*][1].*first*). 132 133 *dp*[*a*][*b*][2] = *s*[*a*][*b*] - (*t*[*a*][*b*] ≤ *QB*[*a*][1].*second*?*QB*[*a*][2].*first*: *QB*[*a*][1].*first*). 134 135 And updating *QA* and *QB* is super easy. 136 137 Now, let *f* = *dp*[1][1][1] and *S* be the sum of scores of all points. So, the score of first player is *f* and the second one is *S* - *f*. 138 139 Time complexity: *O*(*n*2) 140 141 [Code](http://ideone.com/FZ5Ojl) by [sobhan.miryoosefi](/profile/sobhan.miryoosefi "Expert sobhan.miryoosefi") 142 143 [Another Code](http://ideone.com/QvOITL) by [Haghani](/profile/Haghani "Grandmaster Haghani") 144 145 [Java Code](http://ideone.com/0JPkPt) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 146 147 ### [536E - Tavas on the Path](/contest/536/problem/E "Codeforces Round 299 (Div. 1)") 148 149 Let's call the answer for vertices *v* and *u* with edges *e*1, *e*2, ..., *e**k* on the path, score of sequence *w*(*e*1), *w*(*e*2), ..., *w*(*e**k*). 150 151 Use heavy-light decomposition. Decompose the edges into chains. So, for each Query, decompose the path into subchains. After solving the problem for them, combine them. Problem for subchains is : 152 153 We have an array *a*1, *a*2, …, *a**n* and *q* queries. Each query gives numbers *x*, *y*, *l* (1 ≤ *x* ≤ *y* ≤ *n*) and we should print the goodness of subarray *a**x*, *a**x* + 1, …, *a**y*. 154 155  156 157 For this problem, we have too choices: 1.Solve offline with a normal segment tree. 2.Solve online using persistent segment tree. Now, I prefer to use the first approach. Sort the array to have a permutation of 1, 2, …, *n*: *p*1, *p*2, …, *p**n* and *a**p*1 ≥ *a**p*2 ≥ … ≥ *a**p**n*. Also sort the queries in the decreasing order of *l*. No for *i* - *th* query (in the sorted order) we have information: *x*, *y*, *l*, *index*. 158 159 Then, use two pointers. Keep a `pointer = n` and Initially we have a binary string *b*, of length *n* with all indices set to 0. Then in each query: 160 161 ``` 162 for i = 1 to q 163 while (pointer > 1 and l[i] >= a[pointer]) 164 Set p[pointer]-th bit of b (from left) to 1 165 pointer = pointer - 1 166 answer to query number index[i] = T(bx…by) 167 ``` 168 169 Now, we should fins *T*(*b**x*…*T**y*). For this purpose, we need a segment tree. In each node of the segment tree, we need to keep a package named `node`. 170 171 ``` 172 struct node{ 173 int p, s, cnt, tot; 174 }; 175 ``` 176 177 A package `node` is used for calculating *T* of a binary string *c*. *p* = the number of leading 1s, *s* = the number of trading 1s, *cnt* = the total number of 1s, *tot* = the *T* value of the binary string after deleting its leading and trading 1s. 178 179 Merging two nodes is really easy. Also after reversing *c*, we just need to swap *p* and *s*. 180 181 So, we can determine the `node` of this subarray in subchains. 182 183 After solving these offline for subchains it's time for combining. 184 185 Merge the `node` of subchains in the path from *v* to *LCA*(*v*, *u*) then merge the result with the reverse of the `node`s of answers in the subchains in path from *LCA*(*v*, *u*) to *u*. 186 187 Time complexity: *O*((*n* + *m*)*log*2(*n*)) 188 189 [Code](http://ideone.com/N0Vb7e) by [PrinceOfPersia](/profile/PrinceOfPersia "Candidate Master PrinceOfPersia") (This was one of the hardest codes I ever wrote in competitive programming :D) 190 191 [Shorter Code](http://ideone.com/7blKHl) by [Haghani](/profile/Haghani "Grandmaster Haghani") 192 193 [Java Code](http://ideone.com/d2s583) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 194 195  196 197 If there's any suggestion or error, just let me know.