codeforces-scrape

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

1779.md (21299B)


      1 Source: https://codeforces.com/blog/entry/110629
      2 
      3 ## [1779A - Hall of Fame](/contest/1779/problem/A "Hello 2023")
      4 
      5 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
      6 
      7 **Hint**
      8 
      9 What happens when $\texttt{L}$ appears after some $\texttt{R}$ in the string?
     10 
     11 **Solution**
     12 
     13 Suppose that there exists an index $i$ such that $s_i = \texttt{R}$ and $s_{i+1} = \texttt{L}$. Lamp $i$ illuminates trophies $i+1,i+2,\ldots n$ and lamp $i+1$ illuminates $1,2,\ldots i$. We can conclude that all trophies are illuminated if $\texttt{L}$ appears right after some $\texttt{R}$. So, strings $\texttt{LLRRLL}, \texttt{LRLRLR}, \texttt{RRRLLL}, \ldots$ do not require any operations to be performed on them, since they represent configurations of lamps in which all trophies are already illuminated.
     14 
     15 Now, we consider the case when such $i$ does not exist and think about how we can use the operation **once**. Notice that if $\texttt{R}$ appears right after some $\texttt{L}$, an operation can be used to transform $\texttt{LR}$ into $\texttt{RL}$, and we have concluded before that all trophies are illuminated in that case. So, if $\texttt{LR}$ appears in the string, we perform the operation on it.
     16 
     17 An edge case is when $\texttt{L}$ and $\texttt{R}$ are never adjacent (neither $\texttt{LR}$ nor $\texttt{RL}$ appears). Notice that $s_i = s_{i+1}$ must hold for $i=1,2,\ldots n-1$ in that case, meaning that $\texttt{LL} \ldots \texttt{L}$ and $\texttt{RR} \ldots \texttt{R}$ are the only impossible strings for which the answer is $-1$.
     18 
     19 **Bonus Problem**
     20 
     21 Solve the task in which $q \leq 10^5$ range queries are given: for each segment $[l,r]$ print the required index $l \leq i \lt r$, $0$ or $-1$.
     22 
     23 ## [1779B - MKnez's ConstructiveForces Task](/contest/1779/problem/B "Hello 2023")
     24 
     25 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
     26 
     27 **Hint 1**
     28 
     29 There always exists an answer for **even** $n$. Can you find it?
     30 
     31 **Hint 2**
     32 
     33 There always exists an answer for **odd** $n \geq 5$. Can you find it?
     34 
     35 **Solution**
     36 
     37 If $n$ is **even**, the array $[-1,1,-1,1, \ldots ,-1,1]$ is a solution. The sum of any two adjacent elements is $0$, as well as the sum of the whole array.
     38 
     39 Suppose that $n$ is **odd** now. Since $s_{i-1} + s_i$ and $s_i + s_{i+1}$ are both equal to the sum of the whole array for each $i=2,3,\ldots n-1$, it must also hold that $s_{i-1} + s_i = s_i + s_{i+1}$, which is equivalent to $s_{i-1} = s_{i+1}$. Let's fix $s_1 = a$ and $s_2 = b$. The condition above produces the array $s = [a,b,a,b, \ldots a,b,a]$ (remember that we consider an **odd** $n$).
     40 
     41 Let $k$ be a positive integer such that $n = 2k+1$. The sum of any two adjacent elements is $a+b$ and the sum of the whole array is $(k+1)a + kb$. Since the two values are equal, we can conclude that $ka + (k-1)b = 0$. $a=k-1$ and $b=-k$ produces an answer. But, we must be careful with $a=0$ and $b=0$ since that is not allowed. If $k=1$ then $ka+(k-1)b=0$ implies $ka=0$ and $a=0$, so for $n=2\cdot 1 + 1 = 3$ an answer does not exist. Otherwise, one can see that $a=k-1$ and $b=-k$ will be non-zero, which produces a valid answer. So, the array $[k-1, -k, k-1, -k, \ldots, k-1, -k, k-1]$ is an answer for $k \geq 2$ ($n \geq 5$).
     42 
     43 **Bonus Problem**
     44 
     45 Solve a generalized task with given $m$ — find an array $a_1,a_2, \ldots a_n$ ($a_i \neq 0$) such that $a_i + a_{i+1} + \ldots a_{i+m-1}$ is equal to the sum of the whole array for each $i=1,2,\ldots n-m+1$ (or determine that it is impossible to find such array).
     46 
     47 ## [1779C - Least Prefix Sum](/contest/1779/problem/C "Hello 2023")
     48 
     49 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
     50 
     51 **Hint 1**
     52 
     53 Try a greedy approach.
     54 
     55 **Hint 2**
     56 
     57 What data structure supports inserting an element, finding the maximum and erasing the maximum? That is right, a binary heap, or STL *priority_queue*.
     58 
     59 **Solution**
     60 
     61 Let $p_i = a_1 + a_2 + \ldots a_i$ and suppose that $p_x \lt p_m$ for some $x \lt m$. Let $x$ be the greatest such integer. Performing an operation to any element in the segment $[1,x]$ does nothing since $p_m - p_x$ stays the same. Similarly, performing an operation to any element in segment $[m+1,n]$ does not affect it.
     62 
     63 A greedy idea is to choose the maximal element in segment $[x+1,m]$ and perform an operation on it, because it decreases $p_m$ as much as possible. Repeat this process until $p_m$ eventually becomes less than or equal to $p_x$. It might happen that a new $p_y$ such that $p_y \lt p_m$ and $y \lt x$ emerges. In that case, simply repeat the algorithm until $p_m$ is less than or equal to any prefix sum in its "left".
     64 
     65 Suppose that $p_x \lt p_m$ and $x \gt m$ now. The idea is the same, choose a minimal element in segment $[m+1,x]$ and perform an operation on it as it increases $p_x$ as much as possible. And repeat the algorithm as long as such $x$ exists.
     66 
     67 To implement this, solve the two cases independently. Let's describe the first case as the second one is analogous. Iterate over $i$ from $m$ to $1$ and maintain a priority queue. If $p_i \lt p_m$, pop the queue (possibly multiple times) and decrease $p_m$ accordingly (we simulate performing the "optimal" operations). Notice that one does not have to update any element other than $p_m$. Add $a_i$ to the priority queue afterwards.
     68 
     69 The time complexity is $O(n \log n)$.
     70 
     71 **Bonus Problem**
     72 
     73 Solve the task for each $m=1,2,\ldots, n$ i.e. print $n$ integers: the minimum number of operations required to make $a_1 + a_2 + \ldots a_m$ a least prefix sum for each $m$ (the tasks are independent).
     74 
     75 ## [1779D - Boris and His Amazing Haircut](/contest/1779/problem/D "Hello 2023")
     76 
     77 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
     78 
     79 **Stupid Hint**
     80 
     81 If $a_i \lt b_i$ for some $i$, then an answer does **not** exist since a cut cannot make a hair taller.
     82 
     83 **Hint**
     84 
     85 If you choose to perform a cut on some segment $[l,r]$ with a razor of size $x$, you can "greedily" extend it (decrease $l$ and increase $r$) as long as $x \geq b_i$ for each $i$ in that segment and still obtain a correct solution.
     86 
     87 **Solution**
     88 
     89 There exist some data structures (segment tree, dsu, STL maps and sets, $\ldots$) ideas, but there is also a simple solution with a STL stack.
     90 
     91 Consider $a_n$ and $b_n$. If $b_n$ is greater, the answer is `NO` since it is an impossible case (see "Stupid Hint" section). If $a_n$ is greater, then a cut on range $[l,n]$ with a razor of size $b_n$ has to be performed. Additionally, $l$ should be as small as possible (see "Hint" section). For each $i$ in the range, if $a_i$ becomes exactly equal to $b_i$, we consider the position $i$ *satisfied*. If $a_n$ and $b_n$ are equal, then we simply pop both arrays' ends (we ignore those values as they are already *satisfied*) and we continue our algorithm.
     92 
     93 Onto the implementation. We keep track (and count) of each razor size we must use. This can simply be done by putting the corresponding sizes into some container (array or vector) and checking at the end whether it is a subset of $x_1,x_2,\ldots x_m$ (the input array of allowed razors). To do this, one can use sorting or maps. This part works in $O(n \log n + m \log m)$ time.
     94 
     95 Implementing cuts is more challenging, though. To do this, we keep a monotone stack which represents all cuts which are valid until "now" (more formally, all cuts with their $l$ being $\leq i$, and the value of $l$ will be determined later). The top of the stack will represent the smallest razor, and the size of razors does **not decrease** as we pop it. So, we pop the stack as long as the top is smaller than $b_n$ (since performing an operation which makes $a_i$ less than $b_i$ is not valid). After this, if the new top is exactly equal to $b_n$ we can conclude that we have satisfied $a_n = b_n$ with some previous cut and we simply continue our algorithm. Otherwise, we add $b_n$ to the stack as a cut must be performed. This part works in $O(n + m)$ time.
     96 
     97 Total complexity is $O(n \log n + m \log m)$ because of sorting/mapping.
     98 
     99 **Bonus Problem**
    100 
    101 Solve the task in $O(n+m)$ total complexity.
    102 
    103 ## [1779E - Anya's Simultaneous Exhibition](/contest/1779/problem/E "Hello 2023")
    104 
    105 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
    106 
    107 **Hint**
    108 
    109 A tournament graph is given. Player $i$ is a candidate master if for every other player there exists a path from $i$ to them. Can you find *one* candidate master? (which helps in finding all of them)
    110 
    111 **Lemma 1**
    112 
    113 Statement: If player $i$ has the highest out-degree, then they are a candidate master.
    114 
    115 Proof: Let's prove a stronger claim, if player $i$ has the highest out degree, then they reach every other player in $1$ or $2$ edges. Let $S_1$ be the set of players which are immediately reachable and let $S_2$ be the set of other players (not including $i$). Choose some $x \in S_2$. If $x$ is not reachable from $i$, then it has an edge to it as well as to every player in $S_1$, meaning that the out-degree of $x$ is at least $|S_1|+1$. This is a contradiction, since $i$ has out-degree exactly equal to $|S_1|$ and the initial condition was for $i$ to have the highest out-degree. So, every $x \in S_2$ is reachable by $i$, which proves the lemma.
    116 
    117 **Lemma 2**
    118 
    119 Statement: There exists an integer $w$ such that player $i$ is a candidate master if and only if its out-degree is greater than or equal to $w$.
    120 
    121 Proof: Let $S_1, S_2, \ldots S_k$ represent the strongly connected components (SCC) of the tournament graph, in the topological order ($S_1$ is the "highest" component, while $S_k$ is the "lowest"). Since the graph is a tournament, it holds that there exists a directed edge from $x$ to $y$ for each $x \in S_i$, $y \in S_j$, $i \lt j$. We can also conclude that $x$ has a higher out-degree than $y$ for each $x \in S_i$, $y \in S_j$, $i \lt j$. The same holds for $i=1$, which proves the lemma since $S_1$ is the set of candidate masters, and also each player in it has **strictly higher** out-degree than every other player not in it.
    122 
    123 **Solution**
    124 
    125 For each player, we host a simul which includes every other player (but themselves). This tells us the necessary out-degrees and we can easily find one candidate master (the one with highest out-degree).
    126 
    127 The second step is to sort all players by out-degree in non-increasing order and maintain the current $w$ described in "Lemma 2". Its initial value is the out-degree of player $1$. As we iterate over players, we host additional simuls: if player $i$ wins a match against at least one player among $1,2, \ldots j$ (the set of current candidate masters), then $i$ is also a candidate master, as well as $j+1, j+2, \ldots i-1$, we update the set accordingly and eventually decrease $w$.
    128 
    129 The first step requires $n$ simuls to be hosted, and the same hold for step $2$. In total, that is $2n$ simuls (or slightly less, depending on implementation).
    130 
    131 **Bonus Problem**
    132 
    133 Solve the task if $n-1$ simuls are allowed to be hosted.
    134 
    135 ## [1779F - Xorcerer's Stones](/contest/1779/problem/F "Hello 2023")
    136 
    137 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
    138 
    139 **Hint 1.1**
    140 
    141 If **XOR** of all stones equals $0$, then by performing one spell to the root we obtain an answer.
    142 
    143 **Hint 1.2**
    144 
    145 Solve the task for **even** $n$.
    146 
    147 **Hint 1.3**
    148 
    149 If $n$ is **even**, performing a spell to the root guarantees that all nodes will have the same number of stones, meaning that the total **XOR** of the tree is $0$, thus performing the same spell again makes all nodes have $0$ stones.
    150 
    151 **Hint 2.1**
    152 
    153 Consider **even** and **odd** subtrees. What does a spell do to them?
    154 
    155 **Hint 2.2**
    156 
    157 A spell performed to the **odd** subtree does nothing. It does not change the total **XOR**, and it also makes performing a spell to some node in its subtree useless as their **XOR**s would be $0$ anyway. Thus, we are only interested in **even** subtrees.
    158 
    159 **Solution**
    160 
    161 Please refer to the hints as steps. Let's finish the casework:
    162 
    163 Let nodes $u$ and $v$ have **even** subtrees. And let the spell be performed on $u$, and then on $v$ slightly later. Consider the following $3$ cases:
    164 
    165 1. $u$ is an ancestor of $v$; performing a spell on $v$ does not make sense as its subtree's **XOR** is already $0$.
    166 2. $v$ is an ancestor of $u$; performing a spell on $u$ does not make sense either as it will be "eaten" by $v$ later. More formally, let $s_u$ be the current **XOR** of $u$'s subtree. We define $s_v$ and $s_1$ analogously. A spell performed on $u$ sets $s_v := s_v \oplus s_u$ and $s_1 := s_1 \oplus s_u$. Later, the spell performed on $v$ sets $s_1 := s_1 \oplus s_v$. Notice that the final state of $s_1$ is the same as if only the spell on $v$ was performed (since $s_u \oplus s_u = 0$). This means that the total **XOR** stays the same independent of whether we perform a spell on $u$ or not.
    167 3. Neither $u$ or $v$ is a parent of the other; this is the only case we are interested in and we will use this as a fact.
    168 
    169 We only need to choose some subtrees such that their total **XOR** is equal to the **XOR** of the root. Why? Because after applying the spells to them the total **XOR** becomes $0$, and that problem has been solved in "Hint 1.1". Of course, each pair of subtrees must satisfy the condition in case $3$, thus finding the subtrees is possible with dynamic programming and reconstruction. In each node we keep an array of size $32$ which tells us the possible **XOR** values obtained by performing spells on nodes in its subtree. Transitions are done for each edge, from child to parent, in similar fashion to the knapsack problem, but with **XOR** instead of sums.
    170 
    171 Time complexity is $O(n A^2)$ and memory complexity is $O(nA)$. It is possible to optimize this, but not necessary.
    172 
    173 **Bonus Problem**
    174 
    175 Can you minimize the number of operations?
    176 
    177 **Bonus Problem Hint**
    178 
    179 The number of them is $\leq 6$ (in an optimal case).
    180 
    181 ## [1779G - The Game of the Century](/contest/1779/problem/G "Hello 2023")
    182 
    183 Author: [Giove](/profile/Giove "Master Giove")
    184 
    185 **Hint**
    186 
    187 Consider the sides of the big triangle. If they have the same orientation (clockwise or counter-clockwise), $0$ segments have to be inverted since the village is already biconnected.
    188 
    189 **Solution**
    190 
    191 If the three sides do not all have the same orientation, inverting some segments is necessary. The following picture represents them (or rather, one case, but every other is analogous).
    192 
    193 ![ ](/predownloaded/a7/0f/a70f4d2da21d6877493f3f3dc7af58356d17b00a.png)
    194 
    195 There are two "major" paths:
    196 
    197 * $A \rightarrow C$
    198 * $A \rightarrow B \rightarrow C$
    199 
    200 Each road has a "beginning" in one of the paths, hence it is possible to reach every intersection from $A$. Similarly, $C$ can be reached from every other intersection. The problem is that $C$ acts as a tap as it cannot reach anything.
    201 
    202 To make the village biconnected, we will make it possible for $C$ to reach $A$ by inverting the smallest number of road segments. Intuitively, that will work since for every intersection $x$ there exists a cycle $A \rightarrow x \rightarrow C \rightarrow A$. A formal proof is given at the end of this section.
    203 
    204 The task is to find a shortest path from $C$ to $A$, with edges having weights of $0$ (its direction is already as desired) and $1$ (that edge has to be inverted). To implement this in $O(n)$, one has to notice that we are only interested in the closest road of each direction to the big triangle's side. One can prove that by geometrically looking at the strongly connected components, and maybe some casework is required. But, the implementation is free of boring casework.
    205 
    206 Now, it is possible to build a graph with vertices which belong to at least one of the $6$ roads we take into consideration (there are $3$ pairs of opposite directions). One can run a $0$-$1$ BFS and obtain the shortest path.
    207 
    208 This will indeed make the village biconnected as a shortest path does not actually pass through sides $A \rightarrow B$ and $B \rightarrow C$ (why would it? it is not optimal making effort to reach it just to invert some unnecessary additional road segments) The shortest path from $C$ to $A$ intersects the side $A \rightarrow C$ though (possibly multiple times), but it can be proved that every intersection on it is reachable from $C$. Also, sides $A \rightarrow B$ and $B \rightarrow C$ are reachable from $C$ since $A$ is reachable from $C$. This means that all sides are reachable by both $A$ and $C$, and so is every other intersection.
    209 
    210 **Bonus Problem**
    211 
    212 Solve the problem if it is required to process $q \leq 10^5$ queries: invert a given road (and every segment in it), then print the minimum number of road segments you need to additionally invert to make the village biconnected (and not perform them, they are independent from the queries).
    213 
    214 ## [1779H - Olympic Team Building](/contest/1779/problem/H "Hello 2023")
    215 
    216 Author: [n0sk1ll](/profile/n0sk1ll "Master n0sk1ll")
    217 
    218 Huge thanks to [dario2994](/profile/dario2994 "International Grandmaster dario2994") for helping me solve and prepare this problem.
    219 
    220 **Hint 1**
    221 
    222 Try reversing the process.
    223 
    224 **Hint 2**
    225 
    226 Start with some multiset ${ x }$ containing only $1$ element. We will try to make $x$ an *absolute winner*. Extend it by repeatedly adding subsets of equal sizes to it (which have sum less than or equal to the current one).
    227 
    228 **Fake Solution**
    229 
    230 A simple greedy solution is to always extend the current subset with the one which has the maximum sum. This, however, gives **WA** as `100 100 101 98 89 103 103 104 111 680 1 1 1 1 1 2` is a counter-example. (see it for yourself!)
    231 
    232 **Lemma**
    233 
    234 Statement: If it is possible to extend some multiset $A$ to the whole array $s$, we consider it *winning*. If $A \leq B$ holds for some subset $B$, then $B$ is also *winning*. Here, $A \leq B$ means that there exists a bijection $f\colon A\to B$ such that $x \leq f(x)$ for each $x \in A$.
    235 
    236 Proof: Let $A, A_1, A_2, \ldots A_k$ be a *winning* sequence of extensions. By definition of $A \leq B$, we can swap each element of $A$ with some other element. There are three cases:
    237 
    238 1. If we swap some $x \in A$ with an element which is already in $A$, nothing happens.
    239 2. If we swap some $x \in A$ with an element which is not in any $A_i$, the sum of $A$ increases hence it is also *winning*.
    240 3. If we swap some $x \in A$ with an element which is contained in some $A_i$, the sum of $A$ increases, the sum of $A_i$ decreases and the sum of sums of $A,A_1, \ldots, A_i$ stays the same. The sequence remains winning.
    241 
    242 **Solution**
    243 
    244 Special cases of the lemma are subsets of size $1$. We can conclude that if $x$ is winning and $x \leq y$, then so is $y$. The answer is binary-searchable. Let's work with some fixed $s_i = x$ from now on. The idea is to maintain a list of current possible *winning* subsets. The motivation of lemma is to exclude subsets which cannot produce the answer.
    245 
    246 1. we can see that ${ s_j, s_i } \leq { s_{i-1},s_i }$ for each $j \lt i-1$, hence the only *interesting* subset is ${ s_{i-1}, s_i }$ (we excluded others because if one of them is an answer, then so is ${ s_{i-1}, s_i }$. We will use this without explanation later on).
    247 2. we extend ${ s_{i-1}, s_{i} }$ further to a subset of size $4$. There will be at most $15$ new subsets and it can be proved by using the lemma and two pointers.
    248 3. extend the current subsets to have size $8$. And, of course, use the lemma again and exclude unnecessary subsets. Implementing it properly should be fast enough. A fact is that there will be **at most** $8000$ subsets we have to consider. Although, proving it is not trivial. Consider all subsets of size $4$ and a partial ordering of them. In our algorithm we have excluded all subsets with large sum and then we excluded all subsets which are less than some other included set. So, the max collection of such subsets is less in size than the max antichain of $4$-subsets with respect to $\leq$. Following the theory, a max anti-chain can have size at most $\max\limits_{k} f(k)$, where $f(k)$ is the number of $4$-subsets with indices having sum exactly $k$. Hard-coding this gives us an approximation of $519$. This value should be multiplied by $15$, since we had that many $4$-subsets to begin with. This is less than $8000$, which is relatively small.
    249 4. Extending the $8$-subsets further sounds like an impossible task. But, greedy finally comes in handy. Every $8$-subset should be extended with another $8$-subset which maximizes the sum. It is not hard to see that if an answer exists, then this produces a correct answer too. We are left with solving $8$-sum in an array of size $24$. As we need to do this around $8000$ times, we use the **meet in the middle** approach. It can be done in around $2^{12}$ operations if merge sort is used (it spares us the "$12$" factor in $12 \cdot 2^{12}$).
    250 
    251 Summary: Solving the task for $n\leq 16$ is trivial. Let's fix $n=32$. Calculating the exact complexity does not make much sense as $n$ is fixed, but we will calculate the rough number of basic arithmetic operations used. Firstly, a binary search is used, which is $\log 32 = 5$ operations. Then, we generate $8$-subsets which can be implemented quickly (but is not trivial). The **meet in the middle** part consumes $8000 \cdot 2^{12}$ operations. The total number of operations is roughly $5 \cdot 8000 \cdot 4096 = 163\,840\,000$, which gives us a decent upper bound.
    252 
    253 **Bonus Problem**
    254 
    255 Try to construct a strong test against fake greedy solutions :)