1995.md (11748B)
1 Source: https://codeforces.com/blog/entry/131851 2 3 ## [1995A - Diagonals](/contest/1995/problem/A "Codeforces Round 961 (Div. 2)") 4 5 **Hint** 6 7 How many described diagonals are there in total? How many cells do they contain? 8 9 **Answer to Hint** 10 11 In total we have $2 n - 1$ diagonals. There is only one diagonal that contains $n$ cells, two containing $n - 1$ cells, ..., and two containing only one cell each (namely passing through $(1, n)$ and $(n, 1)$). 12 13 **Solution** 14 15 Obviously, in this case, it is worth filling the largest diagonal with chips, then two that are smaller in size, and so on. The asymptotics turns out to be $O(n)$. 16 17 **Code** 18 19 [272176453](/contest/1995/submission/272176453 "Submission 272176453 by goncharovmike") 20 21 ## [1995B1 - Bouquet (Easy Version)](/contest/1995/problem/B1 "Codeforces Round 961 (Div. 2)") 22 23 **Hint** 24 25 For each number of petals, we can bruteforce the answer for $x, x + 1$ 26 27 **Solution** 28 29 First, we can aggregate number of flowers with $x$ petals into $c_{x}$ (for example, sort the array and then create array of pairs $(x, c_{x})$, where $c_{x}$ is the length of segment with elements equal to $x$). 30 31 Note that $\sum_{x} c_{x} = n$. Also note that for every $x$ we won't need more than $\left\lfloor\frac{m}{x}\right\rfloor$ flowers (otherwise total number of petals will exceed $m$). 32 33 Then we iterate through all $x$. Suppose that we want to assemble a bouquet with $x, x + 1$ petals. We can bruteforce the amount of flowers with $x$ petals in $O(c_{x})$. If we have $0 \le k_1 \le min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$ flowers with $x$ petals, we already have $k_1 * x$ petals. There are still $m - k_1 * x$ coins which we can spend for flowers with $x + 1$ petals. There are at most $k_2 = min(c_{x + 1}, \left\lfloor\frac{m - k_1 * x}{x + 1}\right\rfloor)$ flowers with $x + 1$ petal we can buy. So we need to find maximum over all such $k_1 * x + k_2 * (x + 1)$. 34 35 Total complexity is $O(\sum_{x} c_{x}) = O(n)$ for finding the maximum and $O(n \log n)$ for sorting. 36 37 **Code** 38 39 [272263831](/contest/1995/submission/272263831 "Submission 272263831 by Vitaly239239") 40 41 ## [1995B2 - Bouquet (Hard Version)](/contest/1995/problem/B2 "Codeforces Round 961 (Div. 2)") 42 43 **Hint** 44 45 Maybe there is a way to change bruteforce into checking optimal values for counts of $x, x + 1$? Maybe there are only few types of optimal bouquets for $x, x + 1$? 46 47 **Solution** 48 49 We already have a list of $c_x$. We can use hash map to be able to check for any $c_x$ by $x$. 50 51 We again will try to assemble the bouquet only with flowers with $x, x + 1$ petals. We set $k1 = min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$. Then we have $coins = m - k1 * x$. Let's set $k2 = min(c_{x + 1}, \left\lfloor\frac{coins}{x + 1}\right\rfloor)$. Then we have $coins = m - (k1 * x + k2 * (x + 1))$. Let's substitute flower with $x$ petals with flower with $x + 1$ petals as many times as we can. This can be done $r = min(k1, c_{x + 1} - k2, coins)$ times, as each operation will require us 1 coin, 1 flower in the bouquet with $x$ petals and one 1 flower with $x + 1$ petals not in the bouquet. In total we can get $(k1 - r) * x + (k2 + r) * (x + 1)$ petals. 52 53 This assembling is optimal. Here is why. Suppose that we have $0 \le b1 \le c_{x}$ flowers with $x$ petals and $0 \le b2 \le c_{x + 1}$ flowers with $x + 1$ petals and greater total value of $b1 * x + b2 * (x + 1)$. We already know that $b1 \le k1$ by choosing of $k1$. If $k1 - r \lt b1$, then we can ''undo'' our operation $r + b1 - k1$ times, sum is still not greater than $m$, and we know that now there can't be more than $k2 + r + b1 - k1$ flowers with $x + 1$ petals, as otherwise we didn't chose optimal $k2$. If $k2 + r \lt b2$, then $r \ne c_{x + 1} - k2$, if $r = k1$ then it is just the case when we have only flowers with $x + 1$ petals which will be considered in case $x + 1, x + 2$, if $r = coins$ then $m = (k1 - r) * x + (k2 + r) * (x + 1)$ and we already found the maximum. So $b2 \le k2 + r$ and $b1 \le k1 - r$ and $b1 * x + b2 * (x + 1)$ is not better than optimal. 54 55 Total time complexity is $O(n)$. 56 57 **Code** 58 59 [272263882](/contest/1995/submission/272263882 "Submission 272263882 by Vitaly239239") 60 61 ## [1995C - Squaring](/contest/1995/problem/C "Codeforces Round 961 (Div. 2)") 62 63 **Hint** 64 65 How many times we need to apply the operation to index $i$, so that $a[i - 1] \leq a[i]$? Let's call it $op[i]$ 66 It's easy to calculate these values in no time. 67 Can we just accumulate them? 68 69 **Answer to Hint** 70 71 We almost can. But, let's take $[4, 2, 4]$ as an example. op[2] = 1, but we don't want to do anything with a[3]. 72 So, sometimes $a[i - 1] \le a[i]$ and we may not want touch a[i] at all, even if something was applied before it. 73 So, should we consider making $op[i] \lt 0$ for some $i$? 74 75 **Solution Integer** 76 77 Let's set $op[i]$ to the number of operation we need to apply to index $i$ so that $a[i - 1] \leq a[i]$. 78 But, if $a[i - 1] \ll a[i]$, let's set it to the negative number of times that we can apply the operation to $a[i - 1]$ so that $a[i - 1] \leq a[i]$ still holds. 79 Now let's just calculate the prefix sum $\texttt{prefix_op}$, don't forget to do $\max(0, \texttt{prefix_op}[i])$. The sum of values in $\texttt{prefix_op}$ is the answer. 80 81 **Solution Float** 82 83 Let's try to go to the logarithmic space to get rid of too big numbers. 84 $\log(x * x) = 2\log(x)$ 85 So, if we replace each value with its logarithm, the operation of squaring becomes multiplying by 2. 86 But this is not good enough, since we may need to do the operation thousands of times, $2^{1000}$ is too big, it doesn't fit into any floating point. 87 So, let's just repeat our trick and go to the log-log space 88 $\log(2 * y) = \log(y) + \log(2)$ 89 Now we see that the operation turns into just adding $\log(2)$. We can afford doing that thousands and millions of times. 90 Let's deine 91 92 Unable to parse markup [type=CF_MATHJAX] 93 94 95 So now, we can just go with a for-loop and do $\displaystyle{\left\lceil\frac{b[i] - b[i - 1]}{\log(2)}\right\rceil}$ opeartions with $i$-th element, updating $b[i]$ accordingly. 96 Since initially $b[i] \leq \log(10^6) \leq 20 \log(2)$, we can maintain the invariant that $b[i] \leq (20 + i)\log(2)$ since after applying an operation to $b[i]$ we can't exceed $b[i - 1]$ by more than $\log(2)$. It means that the final numbers in the log-log space won't exceed 97 98 Unable to parse markup [type=CF_MATHJAX] 99 100 . We can maintain $O(n)$ arithmetics using double without any problems. 101 102 **Code Integer** 103 104 [272174772](/contest/1995/submission/272174772 "Submission 272174772 by Akulyat") 105 106 **Code Float** 107 108 [272174825](/contest/1995/submission/272174825 "Submission 272174825 by Akulyat") 109 110 ## [1995D - Cases](/contest/1995/problem/D "Codeforces Round 961 (Div. 2)") 111 112 **Hint 1** 113 114 If letter is chosen as an ending to some case, each occurrence of this letter may in the text can be considered an ending? 115 116 **Hint 2** 117 118 The length of the word is something too complex. How can you simplify the restriction? 119 120 **Answer to Hint 2** 121 122 The final letter must be an ending of some case and among any 123 124 Unable to parse markup [type=CF_MATHJAX] 125 126 consecutive letters there must be at least one ending. 127 128 **Hint 3** 129 130 Now you don't need the text because you can store bitmasks instead of substrings of length $k$. To calculate the bitmasks you can use prefix sums for each of the characters (it will take $O(cn)$ overall). 131 132 **Hint 4** 133 134 Now you need to find a bitmask with a minimal number of ones which intersects all the stored bitmasks. 135 136 **Hint 5** 137 138 Identify "bad" bitmask instead of "good" ones. 139 140 **Solution** 141 142 (Read the hints.) 143 144 Unable to parse markup [type=CF_MATHJAX] 145 146 is bad if there exists stored 147 148 Unable to parse markup [type=CF_MATHJAX] 149 150 such that 151 152 Unable to parse markup [type=CF_MATHJAX] 153 154 which is equivalent to $b$ being a submask of $\text{~}a$. All such b can be found using simple dp on bitmasks. The rest $b$ are good. 155 156 Time complexity: $O(c n + c 2^c)$ 157 158 **Code** 159 160 [272218277](/contest/1995/submission/272218277 "Submission 272218277 by ikrpprppp") 161 162 ## [1995E1 - Let Me Teach You a Lesson (Easy Version)](/contest/1995/problem/E1 "Codeforces Round 961 (Div. 2)") 163 164 **Hint 1** 165 166 Consider cases of odd and even $n$. Which one is simpler? 167 168 **Answer to Hint 1** 169 170 Even. In this case you can solve the problem for the opposite desks independently. From now on $n$ is odd. 171 172 **Why independently?** 173 174 Let a desk have knights with intelligence $a$, $b$ and the opposite one with $c$, $d$. Since $(a + b) + (c + d) = (a + c) + (b + d)$, the minimal total intelligence on these desks is greater iff the maximal total intelligence is less. 175 176 **Hint 2** 177 178 If you reorder desks/knights in a way that you swap neighbors (i.e. $2$ with $3$, $4$ with $5$, ..., $2 n$ with $1$) instead of opposite knights, it'll probably become easier to think about this problem. We will use this notation from now on. 179 180 **Hint 3** 181 182 You're allowed to run in $O(n^2)$. Wouldn't it have sense to fix some entity and solve in linear time for fixed entity? 183 184 **Answer to Hint 3** 185 186 Fix the minimal (maximal) desk and the knights who are sitting at it (if the original knights were swapped or not). You'll need to find the minimal maximum on a desk for $4 n$ such cases. 187 188 **Hint 4** 189 190 DP. 191 192 **Solution** 193 194 (Read the hints.) Let the fixed desk have index $k$. Let $dp_{i, b}$ (where $i$ is the index of the desk and $b$ is $0$ / $1$ which indicates whether the knight $2 i$ was swapped) be the minimal maximum that can be achieved on a segment from $k$ to $i$ (satisfying bit $b$ and the fact that the desk $k$ is actually minimal). Then you can easily make transitions $dp_{i, 0}, dp_{i, 1} \to dp_{i + 1, 0}, dp_{i + 1, 1}$. In the end you'll just need to check $dp_{k - 1, b'}$ where $b'$ indicates whether the knight $2 * k - 1$ was swapped in our choice. 195 196 (All the indices for the desks are taken modulo $n$ and all the indices for the knights are taken modulo $2 n$.) 197 198 Time complexity: $O(n^2)$, but the constant is large and $O(n^2\log n)$ solutions with binary search are unlikely to pass. 199 200 **Code** 201 202 [272207462](/contest/1995/submission/272207462 "Submission 272207462 by ikrpprppp") 203 204 ## [1995E2 - Let Me Teach You a Lesson (Hard Version)](/contest/1995/problem/E2 "Codeforces Round 961 (Div. 2)") 205 206 **Hint 0** 207 208 Read the first two hints to E1. 209 210 **Hint 1** 211 212 There are $4 n$ possible desks in total. One of them will be the minimal desk and another one will be the maximal. What is the common-used technique for such problems? 213 214 **Answer to Hint 1** 215 216 Sort them and then use two pointers. 217 218 **Hint 2** 219 220 The data structure you need is very famous. 221 222 **Solution** 223 224 (Read the hints.) Assign a boolean matrix $2 \times 2$ to each of the desks. Rows correspond to the first knight at the desk (two rows for each of the events "the knight was swapped" / "the knight was not swapped"), columns correspond to the second one. The value in the intersection is true if under current restrictions (minimum and maximum) both events can happen, i.e. the result on the desk is between minimum and maximum. 225 226 What is a (boolean) multiplication of matrices from $d_l$ to $d_r$? 227 228 **Answer** 229 230 The matrix where the rows correspond to the knight $2 d_l - 1$ and the columns correspond to the knight $2 d_r$. 231 232 To determine whether it's possible to swap the knights under current restrictions you can just multiply all the matrices and check if there are ones on the main diagonal. Now using two pointers and a segment tree on these matrices you can solve the problem (basically, when you leave some option for a desk in the sorted array of options, you change one of the values of this matrix from $1$ to $0$, and vice versa). 233 234 **Code** 235 236 [272212685](/contest/1995/submission/272212685 "Submission 272212685 by ikrpprppp")