codeforces-scrape

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

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")