codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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)$.