1735.md (11472B)
1 Source: https://codeforces.com/blog/entry/107533 2 3 [1735A - Working Week](/contest/1735/problem/A "Codeforces Round 824 (Div. 2)") 4 5 **Hint1** 6 7 Let's consider that $l_1$, $l_2$, and $l_3$ are sorted working segments. Can we explicitly say something about one of them? 8 9 **Answer to Hint1** 10 11 $l_1$ must be equal to $1$. 12 13 **Solution** 14 15 Let's consider that $l_1$, $l_2$, and $l_3$ are sorted working segments. 16 17 If $l_1$ is not equal to $1$ then we can decrease $l_1$ by $1$ and increase $l_3$ by $1$. So we'll increase the answer. 18 19 We've got that $l_1 = 1$ and we have to work just with $l_2$ and $l_3$. 20 21 Now, our problem can be rewritten as: 22 $l_2 + l_3 = n - 4$, maximize $min(l_2 - 1, l_3 - l_2)$. 23 24 And as we know that $l_3 = n - 4 - l_2$, just: 25 maximize $min(l_2 - 1, n - 4 - 2 \cdot l_2)$. 26 27 If we increase both values under the minimum scope by one, solutions don't change: 28 maximize $min(l_2, (n - 3) - 2 \cdot l_2)$. 29 30 If we choose $l_2 = \left\lfloor\frac{n-3}{3}\right\rfloor$, then $min(l_2, (n - 3) - 2 \cdot l_2) = \left\lfloor\frac{n-3}{3}\right\rfloor$. 31 If the answer is greater, then $l_2 \gt \frac{n - 3}{3}$ and $(n - 3) - 2 \cdot l_2 \gt \frac{n - 3}{3}$, and it means that $2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) \gt n - 3$ but $2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) = n - 3$. 32 33 The only thing is left to do is to calculate final answer. And it is $\left\lfloor\frac{n-3}{3}\right\rfloor - 1$ or just $\left\lfloor\frac{n}{3}\right\rfloor - 2$. 34 35 It was a mathematician way of solving. As it's pretty obvious that $l_2$ is approximately $\frac{n}{3}$, you could check $l_2 = \frac{n}{3} \pm 5$ and choose the best among them. 36 37 **Code** 38 39 [174443363](/contest/1735/submission/174443363 "Submission 174443363 by Akulyat") 40 41 [1735B - Tea with Tangerines](/contest/1735/problem/B "Codeforces Round 824 (Div. 2)") 42 43 **Hint1** 44 45 Is there a way to cut pieces to save the minimum value and satisfy required conditions? 46 47 **Hint2** 48 49 What is the minimum possible number of operations to perform it? 50 Is there any better solution? 51 52 **Solution** 53 54 Let's start with a simple solution. 55 56 Let's choose the minimum piece from $a$ and assume that it will remain the minimum until the end. 57 As the array is sorted, let's define the minimum piece as $a_1$. 58 It means that in the end, all pieces must be smaller or equal to $2 \cdot a_1 - 1$. 59 60 The lower bound of the answer for this solution is $\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot a_1 - 1}\right\rceil}$. 61 62 Let's show that this is achievable. 63 For each piece, while its size greater than $2 \cdot a_1 - 1$, let's cut off a piece of size $2 \cdot a_1 - 1$. 64 The only problem is that we could get a piece smaller than $a_1$ in the end. 65 But it means that before the last cut we had a piece in the range $[2 \cdot a_1, 3 \cdot a_1 - 2]$. All pieces in this range can be easily cut into pieces of the right size in one move. 66 67 The only left question is why the minimum piece in the end should have size $a_1$. Actually, it shouldn't, but it gives the best answer anyway. 68 As was described above, the lower bound of the solution with the minimal piece of size $x$ in the end is $\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot x - 1}\right\rceil}$. 69 Having a minimal piece with a smaller size, we can't get anything better, because the lower bound will be equal or greater for all $x \lt a_1$. 70 71 **Code** 72 73 [174443424](/contest/1735/submission/174443424 "Submission 174443424 by Akulyat") 74 75 [1735C - Phase Shift](/contest/1735/problem/C "Codeforces Round 824 (Div. 2)") 76 77 **Hint1** 78 79 What is the first letter in the answer? 80 81 **Answer to Hint1** 82 83 $a$ if $t$ doesn't start with $a$ and $b$ otherwise. 84 85 **Hint2** 86 87 Ask the same question as Hint1 for each position. 88 89 **Hint3** 90 91 When we can't choose the minimum unused letter? 92 93 **Answer to Hint3** 94 95 If we form a circle of size less then $26$. 96 Maintain any structure to check it. 97 98 **Solution** 99 100 First of all, the encryption process is reversible. If we obtained $t$ from $s$ using the circle $c$, we can obtain $s$ from $t$ using the same cycle $c$, but reversed. 101 So, let's think in terms of encryption of $t$. 102 103 Lexicographical order itself is a greedy thing. So, we can create a greedy algorithm. 104 105 Let's go from left to right and generate the result letter by letter. We have to choose the best possible option at each step. Let's describe the options we have. 106 107 * If the current letter was used earlier, we already know the replacement we need to choose. 108 * Otherwise, we would like to choose the minimum possible option. We need to maintain some structure to know what is acceptable. 109 110 Let's keep the circle that is already generated(it's a graph). For each letter we have one incoming edge and one outgoing edge in the end. Let's keep them for every letter: arrays $in[26]$, $out[26]$. 111 When we want to generate an outgoing edge at some step(let's define the letter on this step as $x$), we have to choose the minimum letter that doesn't have an incoming edge yet. With one exception: if creating the edge using this rule creates a circle of size less than $26$. It would mean that we wouldn't have a full circle in the end. It's easy to see that there is no more than one such letter, as this letter is just the end of a chain starting in $x$. 112 To check that a small circle wasn't generated, we can go along an outgoing edge $26$ times, starting at $x$. If we end up in $x$ or there was no edge at some step then everything is ok, we can create this edge. 113 114 Complexity is $\mathcal{O}(26 \cdot 26 + n)$, that is, $\mathcal{O}(n)$. 115 116 **Code** 117 118 [174443480](/contest/1735/submission/174443480 "Submission 174443480 by Akulyat") 119 120 [1735D - Meta-set](/contest/1735/problem/D "Codeforces Round 824 (Div. 2)") 121 122 **Hint1** 123 124 How many sets can fit in $5$ cards? 125 126 **Answer to Hint1** 127 128 At most two. 129 If there are two sets among $5$ cards, there will be a central card. 130 Consider each card as a central card. 131 132 **Solution** 133 134 For every two cards, there is always a single card that forms a set with them. 135 [1] That means that two sets can share at most one card. 136 137 Let's prove that there are no more than $2$ sets in a meta-set. 138 Let's define $5$ cards as $c_1, c_2, c_3, c_4, c_5$. Let's guess that $(c_1, c_2, c_3)$ is a set. 139 All other sets can have at most one card among $(c_1, c_2, c_3)$ (according to [1]), so they must include $c_4$ and $c_5$. So we have at most one other set, otherwise they would have two same cards, which is prohibited according to [1]. 140 141 So, every meta-set looks like $2$ sets with one common card. Let's call this card a central card. 142 143 Now there is just a simple combinatorics. For each card, we want to know the number of sets that include it. If this number is $s$, then we should add $\frac{s(s-1)}{2}$ to the answer — it is the number of meta-sets with this card as a central card. 144 145 To get the number of sets for each card, we can iterate over all pairs of cards $(i, j)$, generate the complement to the set, and add $1$ to that card in a map/hashmap. 146 147 Complexity is $\mathcal{O}(kn^2\log(n))$ or $\mathcal{O}(kn^2)$. 148 149 **Code** 150 151 [174443540](/contest/1735/submission/174443540 "Submission 174443540 by Akulyat") 152 153 [1735E - House Planning](/contest/1735/problem/E "Codeforces Round 824 (Div. 2)") 154 155 **Hint1** 156 157 How many possible options are there for the distance between $p_1$ and $p_2$. 158 159 **Answer to Hint1** 160 161 We can limit it with $2 \cdot n$ options. 162 Consider options $d_1[1] + d_2[i]$, $|d_1[1] - d_2[i]|$. Solve each one in linear(almost) time. 163 164 **Hint2** 165 166 Consider the biggest distance among $d_1$ and $d_2$. 167 Can we match it with something? 168 169 **Hint3** 170 171 Remove them one by one while they exceed the distance between $p_1$ and $p_2$. Then the problem is trivial. 172 173 **Solution** 174 175 Let's assume that considered point $p_1$ was to the left of considered point $p_2$. 176 Let's assume that we know the distance $l$ between considered points $p_1$ and $p_2$. Let's show how to solve this problem in linear time(almost linear). 177 178 As long as there is a value greater than $l$, let's get the largest among them(let's call it $x$). Let's assume that this value is from $d_1$. 179 It's easy to see that this point is to the right of the considered point $p_2$ (because the largest distances is to the point $p_1$). It means that we can match distance $x$ from $d_1$ to the distance $x - l$ from $d_2$. 180 181 When there is no value greater than $l$, all other houses are located between considered points. We can match them by sorting. 182 183 That is the $\mathcal{O}(n log(n))$ solution. 184 185 Let's limit possible options of $l$ with $\mathcal{O}(n)$ options. 186 If we know that some house has distances $x$ and $y$ to considered options, then there are $2$ options of $l$: $x + y$ and $|x - y|$. 187 Let's consider $2 \cdot n$ options $d_1[1] + d_2[i]$, $|d_1[1] - d_2[i]|$. 188 189 Complexity is $\mathcal{O}(n^2 log(n))$. 190 191 **Code** 192 193 [174443587](/contest/1735/submission/174443587 "Submission 174443587 by Akulyat") 194 195 [1735F - Pebbles and Beads](/contest/1735/problem/F "Codeforces Round 824 (Div. 2)") 196 197 **Hint1** 198 199 Draw currencies on 2D plane. 200 Assume that you can throw out any amount of money at any moment. 201 What will an area of possible points look like? 202 203 **Hint2** 204 205 It will look like a convex polygon in the upper-right quarter. 206 Keep its edges. 207 How does the structure change when a new day comes? 208 209 **Hint3** 210 211 A new segment is added. A prefix of old segments is shifted by vector, the remaining suffix of old segments is shifted by opposite vector, 212 213 **Solution** 214 215 Let's draw currencies on 2D plane. Having $x$ pebbles and $y$ beads is described as point $(x, y)$. 216 Let's assume that we can throw out any amount of money at any moment. In this case, an area of possible points can be described as a convex polygon in the upper-right quarter. Initially it is the rectangle $[(0, 0), (0, b), (a, b), (a, 0)]$. 217 At any moment, this polygon can be described as a list of segments starting at point $(0, y_0)$ and finishing at point $(x_k, 0)$. In the rectangle described above, there are $2$ segments. 218 Let's keep those segments sorted by angle. 219 220 When a new day comes, each point can be shifted by the vector $c\cdot(p_i, -q_i)\ \forall c \in [-1, 1]$ if the new point has non-negative coordinates. 221 If we forget about new points to be non-negative, how new segments look like? 222 We just have to add new segment $(2 \cdot p_i, -2 \cdot q_i)$ and shift a prefix of old segments by $(-p_i, q_i)$ and remaining suffix of segments by $(p_i, -q_i)$. 223 Then the only thing left to do is to cut segments to keep our polygon non-negative. 224 Sounds great, but sounds like $\mathcal{O}(n^2)$. 225 226 Do we need to maintain segments explicitly? 227 No! 228 Let's just keep the set of their lengths and angles. Knowledge of extreme points $(0, y_0)$ and $(x_k, 0)$ is enough. 229 So we need to: 230 231 * Insert a new segment to the set. (You need just length and angle). 232 * Shift extreme points $(0, y_0)$ and $(x_k, 0)$ by $(-p_i, q_i)$ and $(p_i, -q_i)$ correspondingly. 233 * Delete or cut the last and first segments while they are out of the non-negative area. 234 235 Complexity $\mathcal{O}(nlog(n))$. 236 237 There is another simple $\mathcal{O}(n^2log(n))$ approach: 238 We can keep the area as a polygon. At each step, create two copies shifted by corresponding vectors. Build a convex hull of them. Cut this convex hull to be in the non-negative area. 239 It won't fit. Mentioned just for fun. 240 241 **Code** 242 243 [174443858](/contest/1735/submission/174443858 "Submission 174443858 by Akulyat")