codeforces-scrape

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

2257.md (9136B)


      1 Source: https://codeforces.com/blog/entry/156058
      2 
      3 Thank you for participating in our round! We hope you enjoyed the problems.
      4 
      5 [2257A - Creating Abbreviations](/contest/2257/problem/A "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka")
      6 
      7 **Solution**
      8 
      9 Note that adding abbreviations to the set $S$ does not create any new possibilities for creating new abbreviations, because a word starting with that letter already exists. Therefore, for each of the 26 letters, we can remember that there is a word that begins with it, and then go through all the abbreviations and check each letter.
     10 
     11 **Code**
     12 
     13 [387467084](/contest/2257/submission/387467084 "Submission 387467084 by pskobx")
     14 
     15 **Rate the problem**
     16 
     17 Amazing
     18 
     19 Good
     20 
     21 Ok
     22 
     23 Bad
     24 
     25 Terrible
     26 
     27 [2257B - Gigantomachy](/contest/2257/problem/B "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka")
     28 
     29 **Solution**
     30 
     31 On each turn, the height at which the giant stands decreases by exactly $1$, except in cases where he changes mountains.
     32 
     33 Thus, the first giant will lose after $((a_1 - a_2) + 1) + ((a_2 - a_3) + 1) + \dots + ((a_{n - 1} - a_n) + 1) + a_n = a_1 + n - 1$ moves.
     34 
     35 Similarly, the second giant will lose after $b_1 + m - 1$ moves. All left is only to compare these two numbers.
     36 
     37 Time complexity: $\mathcal{O}(n)$.
     38 
     39 **Code**
     40 
     41 [387467136](/contest/2257/submission/387467136 "Submission 387467136 by pskobx")
     42 
     43 **Rate the problem**
     44 
     45 Amazing
     46 
     47 Good
     48 
     49 Ok
     50 
     51 Bad
     52 
     53 Terrible
     54 
     55 [2257C - Spying on the Beaver](/contest/2257/problem/C "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka")
     56 
     57 **Solution**
     58 
     59 Suppose we have placed some cameras and remove the corresponding edges from the tree. If all the dams are now in different connected components, we can always uniquely determine where the Beaver went. Conversely, if there is a component containing two dams, we cannot distinguish between them.
     60 
     61 Since the original graph is a tree, it is necessary and sufficient to remove $m-1$ edges.
     62 
     63 If the root contains a dam, we can take the edges leading directly to all the other dams, obtaining a set of size $m-1$.
     64 
     65 If the root does not contain a dam, we take the same edges but skip one of them. It is important that we cannot skip just any edge: we must choose a dam such that there are no other dams on the path from the root to it. We can take the dam with the smallest depth or vertex number. In this case, we do not even need to run a DFS.
     66 
     67 Time complexity: $\mathcal{O}(n+m)$.
     68 
     69 **Code**
     70 
     71 [387467226](/contest/2257/submission/387467226 "Submission 387467226 by pskobx")
     72 
     73 **Rate the problem**
     74 
     75 Amazing
     76 
     77 Good
     78 
     79 Ok
     80 
     81 Bad
     82 
     83 Terrible
     84 
     85 [2257D - Bermuda Rectangle](/contest/2257/problem/D "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx"), [oblememan](/profile/oblememan "Master oblememan"), [egorka5opka](/profile/egorka5opka "Master egorka5opka")
     86 
     87 **Solution**
     88 
     89 Before processing the queries, let us perform some preprocessing. Find all pairs $(a, b)$ such that $a \cdot b = S$. There are $\mathcal{O}(\sqrt{S})$ such pairs, and they can also be found in $\mathcal{O}(\sqrt{S})$ time with standard algorithms.
     90 
     91 These pairs are the top-right corners of all possible Bermuda rectangles. The union of these rectangles forms a staircase-like shape; let us call it $F$. The answer to a query is the area of the intersection of the query rectangle with $F$.
     92 
     93 Sort the points by $x$, and for the point with index $i$, compute the value $P_i$, equal to the area of $F$ between $0$ and this $x_i$.
     94 
     95 This information is enough to answer each query efficiently using binary search. We find the position where the boundary of $F$ crosses the horizontal side of the query rectangle and calculate the answer using the corresponding prefix areas. The exact formulas and case analysis may vary depending on the implementation.
     96 
     97 A couple of remarks that may make implementation easier. If there is a point $(x, y)$, then there is also $(y, x)$, and since, knowing one coordinate, it is easy to compute the other. Therefore, it is enough to store just the sorted list of divisors of $S$ and treat them both as $x$ and as $y$.
     98 
     99 Preprocessing complexity: $\mathcal{O}(\sqrt{S})$, time complexity per query: $\mathcal{O}(\log S)$.
    100 
    101 **Code**
    102 
    103 [387467301](/contest/2257/submission/387467301 "Submission 387467301 by pskobx")
    104 
    105 **Rate the problem**
    106 
    107 Amazing
    108 
    109 Good
    110 
    111 Ok
    112 
    113 Bad
    114 
    115 Terrible
    116 
    117 [2257E - Busy Beaver](/contest/2257/problem/E "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx")
    118 
    119 **Solution**
    120 
    121 The first step is to earn as many carrots as possible to maximize our capital. Divide the floors of each building into the shortest consecutive segments whose total profit is non-negative, and calculate the entry threshold of each such segment. The entry threshold is the minimum amount of capital required to construct all floors of the segment in order.
    122 
    123 For example, consider two floors with $(a_1, a_2) = (10, 0)$ and $(b_1, b_2) = (0, 100)$. Constructing only the first floor is unprofitable, but constructing both floors yields a profit of $90$ carrots. However, an initial capital of at least $10$ carrots is required.
    124 
    125 In an ordered set, we keep the next available segment for each building, sorted by its entry threshold. While the segment with the minimum threshold is affordable, we construct the entire segment, add its profit to our capital, and insert the next segment of the same building into the set. If the segment with the minimum threshold is not affordable, then none of the available segments can be constructed, meaning that we have maximized our capital.
    126 
    127 In the second step, we independently try to continue constructing each building from its current height, floor by floor, for as long as the current capital allows. Among all buildings, we choose the maximum resulting height and, in case of a tie, the smallest index.
    128 
    129 Time complexity: $\mathcal{O}\left(\sum m_i \log n\right)$.
    130 
    131 **Code**
    132 
    133 [387467400](/contest/2257/submission/387467400 "Submission 387467400 by pskobx")
    134 
    135 **Rate the problem**
    136 
    137 Amazing
    138 
    139 Good
    140 
    141 Ok
    142 
    143 Bad
    144 
    145 Terrible
    146 
    147 [2257F1 - Beaver's Jumping Track (Easy Version)](/contest/2257/problem/F1 "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx"), [oblememan](/profile/oblememan "Master oblememan"), [egorka5opka](/profile/egorka5opka "Master egorka5opka")
    148 
    149 **Solution**
    150 
    151 Since $x$ is small, we build a segment tree whose vertices store matrices of size $x \times x$.
    152 
    153 For an interval of platforms, let $c[i][j]$ be the minimum penalty if the Beaver starts $i$ cells after the beginning of the interval and first lands $j$ cells after its end. Invalid starting positions are ignored.
    154 
    155 For a single platform of length $d$ and penalty $s$,
    156 
    157 $ c[i][j]= \left( \left\lceil\frac{d+j-i}{x}\right\rceil-1 \right)s, $
    158 
    159 where $0\le i \lt \min(d,x)$ and $0\le j \lt x$. The last jump leaves the platform and causes no penalty, while all previous jumps stay inside it.
    160 
    161 To merge two consecutive intervals $A$ and $B$, enumerate the first landing position $k$ in $B$:
    162 
    163 $ c_{A+B}[i][j] = \min_k\left(c_A[i][k]+c_B[k][j]\right). $
    164 
    165 If $A$ contains fewer than $x$ cells, the Beaver may start directly inside $B$; in this case, we copy the corresponding values from $c_B$.
    166 
    167 For a query $[l,r]$, obtain the matrix for $[l,r-1]$ and enumerate the first landing position $i$ on platform $r$. The answer is
    168 
    169 $ \min_{0\le i \lt \min(x,d_r)} \left( c[0][i] + \left\lceil\frac{d_r-i-1}{x}\right\rceil s_r \right). $
    170 
    171 The case $l=r$ is calculated directly.
    172 
    173 Each update and query takes $\mathcal{O}(x^3\log n)$ time. Memory complexity is $\mathcal{O}(nx^2)$. Build is $\mathcal{O}(nx^3)$.
    174 
    175 **Code**
    176 
    177 [387467533](/contest/2257/submission/387467533 "Submission 387467533 by pskobx")
    178 
    179 **Rate the problem**
    180 
    181 Amazing
    182 
    183 Good
    184 
    185 Ok
    186 
    187 Bad
    188 
    189 Terrible
    190 
    191 [2257F2 - Beaver's Jumping Track (Hard Version)](/contest/2257/problem/F2 "Codeforces Round 1117 (Div. 2)")
    192 
    193 **Solution**
    194 
    195 Surprisingly, the main problem with the solution from F1 is memory, not time. A segment tree stores $\mathcal{O}(n)$ matrices, each containing $x^2$ values. For $x=10$, this does not fit into the memory limit.
    196 
    197 To reduce memory usage, divide the platforms into blocks of size $B$ (for example, $B=16$). For each block, calculate the matrix of the entire block using the same merging formula as in F1. Then build a segment tree only over these block matrices.
    198 
    199 For a query, at most two blocks are only partially covered by the required range. Process the platforms in these blocks separately, and use the segment tree to combine all blocks that are fully covered. After an update, recalculate the matrix of the affected block and update it in the segment tree.
    200 
    201 For a block size $B$, the memory complexity is $\mathcal{O}\left(n+\frac{n}{B}x^2\right)$.
    202 
    203 Each query takes $\mathcal{O}\left(Bx^2+x^3\log\frac{n}{B}\right)$.
    204 
    205 Аnd each update takes $\mathcal{O}\left(Bx^3+x^3\log\frac{n}{B}\right)$.
    206 
    207 **Code**
    208 
    209 [387467610](/contest/2257/submission/387467610 "Submission 387467610 by pskobx")
    210 
    211 **Rate the problem**
    212 
    213 Amazing
    214 
    215 Good
    216 
    217 Ok
    218 
    219 Bad
    220 
    221 Terrible