474.md (4334B)
1 Source: https://codeforces.com/blog/entry/14136 2 3 [474A - Keyboard](/contest/474/problem/A "Codeforces Round 271 (Div. 2)") 4 5 This is an implementation problem, therefore most of the solution fit in the time limit. We can even save the keyboard in 3 strings and make a brute force search for each character to find its position and then print the left/right neighbour. 6 7 [474B - Worms](/contest/474/problem/B "Codeforces Round 271 (Div. 2)") 8 9 There are two solutions: 10 11 1. We can make partial sums (*sum**i* = *a*1 + *a*2 + ... + *a**i*) and then make a binary search for each query *q**i* to find the result *j* with the properties *sum**j* - 1 < *q**i* and *sum**j* ≥ *q**i*. This solution has the complexity *O*(*n* + *m*·*log*(*n*)) 12 2. We can precalculate the index of the pile for each worm and then answer for each query in *O*(1). This solution has the complexity *O*(*n* + *m*) 13 14 [474C - Captain Marmot](/contest/474/problem/C "Codeforces Round 271 (Div. 2)") 15 16 For each 4 points we want to see if we can rotate them with 90 degrees such that we obtain a square. We can make a backtracking where we rotate each point 0, 1, 2 or 3 times and verify the figure obtained. If it's a square we update the minimal solution. Since we can rotate each point 0, 1, 2 or 3 times, for each regiment we have 44 configurations to check. So the final complexity is about *O*(*n*). 17 18 [474D - Flowers](/contest/474/problem/D "Codeforces Round 271 (Div. 2)") 19 20 We can notate each string as a binary string, instead of red and white flowers. A string of this type is good only if every maximal contigous subsequence of "0" has the length divisible by *k*. We can make dynamic programming this way : *nr**i* = the number of good strings of length *i*. If the *i*-th character is "1" then we can have any character before and if the *i*-th character is "0" we must have another *k* - 1 "0" characters before, so *nr**i* = *nr**i* - 1 + *nr**i* - *k* for *i* ≥ *k* and *nr**i* = 1 for *i* < *k*. Then we compute the partial sums (*sum**i* = *nr*1 + *nr*2 + ... + *nr**i*) and for each query the result will be *sum**b* - *sum**a* - 1. This solution has the complexity *O*(*maxVal* + *t*), where *maxVal* is the maximum value of *b**i*. 21 22 [474E - Pillars](/contest/474/problem/E "Codeforces Round 271 (Div. 2)") 23 24 We have to find a substring *i*1, *i*2, ..., *i**k* such that *abs*(*h**i**j* - *h**i**j* + 1) ≥ *D* for 1 ≤ *j* < *k*. Let's suppose that the values in *h* are smaller. We can make dynamic programming this way : *best**i* = the maximal length of such a substring ending in the *i*-th position, *best**i* = *max*(*best**j*) + 1 with *j* < *i* and *h**j* ≥ *D* + *h**i* or *h**j* ≤ *h**i* - *D*. So we can easily search this maximum in a data structure, such as an segment tree or Fenwick tree. But those data structure must have the size of *O*(*maxH*) which can be 109. For our constraints we mantain the idea described above, but instead of going at some specific position in the data structure based on a value, we would normalize the values in *h* and binary search the new index where we should go for an update or a query in the data structure. Therefore, the data structure will have the size *O*(*n*). The complexity of this solution is *O*(*n*·*log*(*n*)). 25 26 [474F - Ant colony](/contest/474/problem/F "Codeforces Round 271 (Div. 2)") 27 28 For each subsequence [*L*, *R*] we must find how many queens we have. A value is "queen" only if is the GCD of (*s**L*, *s**L* + 1, ..., *s**R*). Also, we must notice that the GCD of (*s**L*, *s**L* + 1, ..., *s**R*) can be only the minimum value from (*s**L*, *s**L* + 1, ..., *s**R*). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of (*s**L*, *s**L* + 1, ..., *s**R*) and if these two values are equal then we output the answer *R* - *L* + 1 - *nrValues*, where *nrValues* is the number of values in the subsequence equal to the GCD and the minimum value. The complexity of this solution is *O*(*n*·*log*(*n*)·*log*(*valMax*) + *t*·*log*(*n*)·*log*(*valMax*)), where *valMax* is the maximum value of *s**i*.