1614.md (5628B)
1 Source: https://codeforces.com/blog/entry/97283 2 3 [A. Divan and a Store](https://codeforces.com/contest/1614/problem/A) 4 5 **Solution** 6 7 To solve this problem, let's use the following greedy algorithm. 8 9 Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $l$, but not more than $r$ until we run out of money. 10 11 The number of chocolate bars that we took will be the answer to the problem. 12 13 The resulting asymptotics in time: $\mathcal{O}(n\log{}n)$. 14 15 [B. Divan and a New Project](https://codeforces.com/contest/1614/problem/B) 16 17 **Solution** 18 19 Obviously, the more often we have to go to the $ i $ building, the closer it should be to the main office. 20 21 This implies a greedy algorithm. Let's put the main office at $0$ and sort the rest by $a_i$. Then we put the most visited building at a point with a coordinate of $1$, the second at $-1$, the third at $2$, etc. 22 23 The resulting asymptotics in time is $\mathcal{O}(n\log{}n)$. 24 25 [C. Divan and bitwise operations](https://codeforces.com/contest/1614/problem/C?locale=en) 26 27 **Solution** 28 29 Let's count for each bit how many times it will be included in the answer. 30 31 Let us now consider the $i$-th bit. Note that if no number contains the included $i$-th bit, then such a bit will never be included in the answer. Otherwise, each of the subsequences contains $i$-th bit even or odd number of times. If a bit enters an even number of times, then we should not count such a subsequence, because the bitwise exclusive OR for this bit will be zero. If the bit enters an odd number of times, then we must count such a subsequence, because the bitwise exclusive OR for this bit will be equal to one. 32 33 It is stated that the number of subsequences in which the $i$-th bit enters an odd number of times is equal to $2^{n - 1}$. Let's prove it. 34 35 Divide the numbers into two sets $A$ and $B$. In the set $A$ there will be numbers whose $i$th bit is off, in the set $B$ there will be numbers whose $i$-th bit is on. 36 37 Note that the numbers from the set $A$ do not affect the answer in any way, because $x\; XOR\; 0 = 1$. Thus, whichever subset of $A$ we take, the $i$-th bit will not change its parity. There will be $2^{|A|}$ in total of such subsets. 38 39 Let $k = 1$ if $|B|$ is even, or $k = 0$ if $|B|$ is odd. In order for the $i$-th bit to enter the subsequence an odd number of times, you need to take an odd number of elements from the set $B$. This number is equal to $C_{|B|}^{1} \, + \, C_{|B|}^{3} \, + \dots \, + \, C_{|B|}^{|B| - k} = 2^{|B| - 1}$. 40 41 Thus, the $i$-th bit is included in exactly $2^{|A|}\cdot 2^{|B|- 1}= 2^{n - 1}$ subsequences, which was required to be proved. 42 43 Then the solution to this problem turns out to be very simple: let $x$ be equal to the bitwise OR of all elements of the sequence (or, the same thing, bitwise OR of all given segments), then the answer will be equal to $x\cdot 2^{n - 1}$ modulo $10^9 + 7$. 44 45 The resulting asymptotics in time: $\mathcal{O}(n)$. 46 47 [D1. Divan and Kostomuksha (easy version)](https://codeforces.com/contest/1614/problem/D1) 48 49 **Solution** 50 51 Let's solve the dynamic programming problem. Let $dp_i$ be the maximum answer for all arrays, the last element of which is divisible by $i$. Let's calculate the dynamics from $C$ to $1$, where $C$ is the maximum value of $a_i$. Initially, $dp_i = cnt_i \cdot i$, where $cnt_i$ is the amount of $a_i = i$. How do we recalculate our dynamic programming? $dp_i = max(dp_i, dp_j + i \cdot (cnt_i - cnt_j))$, for all $j$ such that $j$ $mod$ $i = 0$ (i.e. $j$ is divisible by $i$). In this dynamic, we iterate over the past change of our $gcd$ on the prefix, and greedily add all possible elements. 52 53 The resulting asymptotics in time is $\mathcal{O}(C\log{}C)$. 54 55 [D2. Divan and Kostomuksha (hard version)](https://codeforces.com/contest/1614/problem/D2) 56 57 **Solution** 58 59 To solve $D2$, we can notice that to recalculate the dynamics, we can iterate over all such $j$ that differ from $i$ by multiplying exactly $1$ prime number. Also, to speed up the solution, we can use the linear sieve of Eratosthenes to find primes and factorization. 60 61 The resulting asymptotics in time: $\mathcal{O}(C\log{}\log{}C) $. 62 63 [E. Divan and a Cottage](https://codeforces.com/contest/1614/problem/E) 64 65 **Solution** 66 67 Let $ans_{temp}$ the current answer for temperature $temp$. Before all days, $ans_{temp}$ is considered equal to $temp$. 68 69 In order to respond to a request with a temperature of $x$, we will just need to output the value of $ans_x$. But how to maintain $ans$? With the help of an implicit tree of segments, at the vertices of which the minimum and maximum will be stored, as well as the variable $add$, which will contain the value that needs to be added to the current vertex (that is, such a variable that is needed to perform lazy operations on the segment tree). 70 71 At the beginning of the next day you get the temperature $T$. Now we need to change the current answer for some $temp$. We need to find such $ans_{temp}$ that $ans_{temp} \lt T$ and add $+1$ to them, and then find such $ans_{temp}$ that $ans_{temp} \gt T$ and add $-1$ to them. All this is not difficult to do, just starting from the root of the segment tree and stopping at the moments when: 72 73 * the maximum of the current vertex is less than $T$ — here we add $+1$; 74 * the minimum of the current vertex is greater than $T$ — here we add $-1$; 75 * the minimum of the vertex is equal to the maximum of the vertex (and, therefore, the $T$ itself) — here we do not add anything. 76 77 The resulting asymptotics in time: $\mathcal{O}(n\log{}T)$.