558.md (6348B)
1 Source: https://codeforces.com/blog/entry/19212 2 3 ## [558A - Lala Land and Apple Trees](/contest/558/problem/A "Codeforces Round 312 (Div. 2)") 4 5 Let's divide all the trees into two different groups, trees with a positive position and trees with a negative position. Now There are mainly two cases: 6 7 1. If the sizes of the two groups are equal. Then we can get all the apples no matter which direction we choose at first. 8 2. If the size of one group is larger than the other. Then the optimal solution is to go to the direction of the group with the larger size. If the size of the group with the smaller size is *m* then we can get apples from all the *m* apple trees in it, and from the first *m* + 1 trees in the other group. 9 10 So we can sort each group of trees by the absolute value of the trees position and calculate the answer as mentioned above. 11 12 **Time complexity:**  13 14 [**Implementation**](http://ideone.com/3zzpsd) . 15 16 ## [558B - Amr and The Large Array](/contest/558/problem/B "Codeforces Round 312 (Div. 2)") 17 18 First observation in this problem is that if the subarray chosen has *x* as a value that has the maximum number of occurrences among other elements, then the subarray should be [*x*, ..., *x*]. Because if the subarray begins or ends with another element we can delete it and make the subarray smaller. 19 20 So, Let's save for every distinct element *x* in the array three numbers, the smallest index *i* such that *a**i* = *x*, the largest index *j* such that *a**j* = *x* and the number of times it appears in the array. And between all the elements that has maximum number of occurrences we want to minimize *j* - *i* + 1 (i.e. the size of the subarray). 21 22 **Time complexity:**  23 24 [**Implementation**](http://ideone.com/QNw51a) 25 26 ## [558C - Amr and Chemistry](/contest/558/problem/C "Codeforces Round 312 (Div. 2)") 27 28 Let the maximum number in the array be *max*. Clearly, changing the elements of the array to any element larger than *max* won't be optimal, because the last operation is for sure multiplying all the elements of the array by two. And not doing this operation is of course a better answer. 29 30 Now we want to count the maximum number of distinct elements that can be reached from some element *a**i* that are not larger than *max*. Consider an element *a**i* that has a zero in the first bit of its binary representation. If we divided the number by two and the multiplied it by two we will get the original number again. But if it has a one, the resulting number will be different. So, for counting the maximum number of distinct elements we will assume *a**i* = *x* where *x* has only ones in its binary representation. 31 32 From *x* we can only reach elements that have a prefix of ones in its binary representation, and the other bits zeros (e.g. {0, 1, 10, 11, 100, 110, 111, 1000, ...} ). Let's assume *max* has *m* bits in its binary representation, then *x* can reach exactly  distinct elements. So, from each element in the array *a**i* we can reach at most  elements. 33 34 So, Let's generate the numbers that can be reached from each element *a**i* using bfs to get minimum number of operations. And between all the numbers that are reachable from all the *n* elements let's minimize the total number of operations. 35 36 **Time complexity:**  37 38 [**Implementation**](http://ideone.com/9wXvKz) 39 40 ## [558D - Guess Your Way Out! II](/contest/558/problem/D "Codeforces Round 312 (Div. 2)") 41 42 First, each query in the level *i* from *L* to *R* can be transmitted into level *i* + 1 from *L* * 2 to *R* * 2 + 1, so, we can transform each query to the last level. 43 44 Let's maintain a set of correct ranges such that the answer is contained in one of them. At the beginning we will assume that the answer is in the range [2*h* - 1, 2*h* - 1] inclusive. Now Let's process the queries. If the query's answer is yes, then we want to get the intersection of this query's range with the current set of correct ranges, and update the set with the resulting set. If the query's answer is no, we want to exclude the query's range from the current set of correct ranges, and update the set with the resulting set. 45 46 After we finish processing the queries, if the set of correct ranges is empty, then clearly the game cheated. Else if the set has only one correct range [*L*, *R*] such that *L* = *R* then we've got an answer. Otherwise there are multiple exit candidates and the answer can't be determined uniquely using the current data. 47 48 We will have to use stl::set data structure to make updating the ranges faster. In each yes query we delete zero or more ranges. In each no query we may add one range if we split a correct range, so worst case will be linear in queries count. 49 50 **Time complexity:**  51 52 [**Implementation**](http://ideone.com/s8HPBx) 53 54 ## [558E - A Simple Task](/contest/558/problem/E "Codeforces Round 312 (Div. 2)") 55 56 In this problem we will be using [counting sort](https://en.wikipedia.org/wiki/Counting_sort). So for each query we will count the number of occurrences for each character, and then update the range like this 57 58 ``` 59 for(int j=x;j<=y;j++) 60 cnt[s[j] - 'a']++; 61 ind = 0; 62 for(int j=x;j<=y;j++) 63 { 64 while(cnt[ind] == 0) 65 ind++; 66 s[j] = ind + 'a'; 67 cnt[ind]--; 68 } 69 ``` 70 71 But this is too slow. We want a data structure that can support the above operations in appropriate time. 72 73 Let’s make 26 segment trees each one for each character. Now for each query let’s get the count of every character in the range, and then arrange them and update each segment tree with the new values. We will have to use lazy propagation technique for updating ranges. 74 75 **Time complexity:**  where sz is the size of the alphabet (i.e. = 26). 76 77 [**Implementation**](http://ideone.com/wHwvnU)