codeforces-scrape

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

1750.md (15909B)


      1 Source: https://codeforces.com/blog/entry/108504
      2 
      3 # [A — Indirect Sort](https://codeforces.com/contest/1750/problem/A)
      4 
      5 Authors: [mejiamejia](/profile/mejiamejia "Expert mejiamejia"), [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
      6 
      7 **Solution**
      8 
      9 We claim that we can sort the array if and only if $a_1 = 1$.
     10 
     11 **Necessity**
     12 
     13 We can notice that index $1$ cannot be affected by any swap operation.
     14 
     15 Let's see what happens to the value $1$. According to the definition of the operation, it can either increase or be swapped. In order to be increased, there must exist some $k$ such that $1 \gt a_k$, but since $1$ is the minimum possible value, it will never be true as other values in array $a$ can only increse as well. Since index $1$ can not be affected by a swap operation and $a_1 \gt 1$, we conclude that if $a_1 \neq 1$, the answer is **No**.
     16 
     17 **Sufficiency**
     18 
     19 Let's focus on the second operation. Since we have $a_1 = 1$, we can always choose $i=1$ and the operation then turns into picking some pair $2 \le j \lt k \le n$ and swapping $a_j$ with $a_k$. It's trivial to see we can always sort with such an operation.
     20 
     21 **Code (Ecrade_)**
     22 
     23 [**Click me**](https://pastebin.com/pgmxzkiq)
     24 
     25 **Rate Problem**
     26 
     27 Good problem
     28 
     29 Ok problem
     30 
     31 Bad problem
     32 
     33 Didn't solve it, idk
     34 
     35 # [B — Maximum Substring](https://codeforces.com/contest/1750/problem/B)
     36 
     37 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
     38 
     39 **Solution**
     40 
     41 Considering that if we want to find the max value of $x \cdot y$, then the whole string is the best to calculate, for it $0$ s and $1$ s are the max.
     42 
     43 Then considering $x \cdot x$ and $y \cdot y$ : what we need to do is to calculate the max continuous number of $0$ or $1$, compare its square to the first condition, then take the bigger one as the answer.
     44 
     45 **Code (tibinyte)**
     46 
     47 [**Click me**](https://pastebin.com/jSs8Nvy1)
     48 
     49 **Rate Problem**
     50 
     51 Good problem
     52 
     53 Ok problem
     54 
     55 Bad problem
     56 
     57 Didn't solve it, idk
     58 
     59 # [C — Complementary XOR](https://codeforces.com/contest/1750/problem/C)
     60 
     61 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
     62 
     63 **Solution**
     64 
     65 For each operation, the interval changed by a sequence and b sequence is complementary, so you must judge whether all $[a_i=b_i]$ are the same at the beginning. If they are different, you can't have a solution.
     66 
     67 Now, if $a = \neg b$, we can do an operation on $a$ and have $a=b$. Now suppose $a_i=b_i=1$ for some $i$ and try to make $a_i=b_i=0$ without changing anything else. If $i \gt 1$, then this is very simple, we can just do an operation with $(1,i)$ and an operation on $(1,i-1)$. If $i=1$ we can make $(1,n)$ and $(2,n)$. Since $n \gt 1$, this can always be done, thus we found a solution using $2 \cdot n + O(1)$ operations. To optimize it to only use $n + O(1)$ operations, note that we only care about the parity of the number of operations did at any index.
     68 
     69 **Code (tibinyte)**
     70 
     71 [**Click me**](https://pastebin.com/usNVxyqv)
     72 
     73 **Rate Problem**
     74 
     75 Good problem
     76 
     77 Ok problem
     78 
     79 Bad problem
     80 
     81 Didn't solve it, idk
     82 
     83 # [D — Count GCD](https://codeforces.com/contest/1750/problem/D)
     84 
     85 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
     86 
     87 **Solution**
     88 
     89 We can notice that if for some $2 \le i \le n$, $a_{i-1}$ is not divisible by $a_{i}$, then the answer is $0$. Else, note that all the prime factors of $a_1$ are also prime factors in all the other values. Thus after factorizing $a_1$ we can quickly factorize every other value.
     90 
     91 Now let's find the number of ways we can select $b_i$ for every $i$. The answer will be the product of these values since each position is independent. It's easy to see that there is only one way to select $b_1$, that is $a_1$. Now for $i \gt 1$ we need to find the number of values $x$ such that $gcd(a_{i-1},x)=a_i$. Let $x=a_i \cdot k$, we can rephrase as $gcd( \frac{a_{i-1}}{a_i} \cdot a_i, a_i \cdot k) = a_i$, which is also equivalent to $gcd( \frac{a_{i-1}}{a_i}, k) = 1$. We have $k \le \frac{m}{a_i}$, thus the task reduces to a simple principle of inclusion-exclusion problem.
     92 
     93 Time complexity $O(2^9 \cdot 9 \cdot log + \sqrt{m})$ per testcase.
     94 
     95 **Code (tibinyte)**
     96 
     97 [**Click me**](https://pastebin.com/wD9hfrHG)
     98 
     99 **Rate Problem**
    100 
    101 Good problem
    102 
    103 Ok problem
    104 
    105 Bad problem
    106 
    107 Didn't solve it, idk
    108 
    109 # [E — Bracket Cost](https://codeforces.com/contest/1750/problem/E)
    110 
    111 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
    112 
    113 **Solution**
    114 
    115 Let $a_i=1$ if $s_i=($, $a_i=-1$ if $s_i=)$ and $b_i$ be the prefix sum of $a_i$.
    116 
    117 Theorem: the cost of $s[l+1,r]$ is $max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$
    118 
    119 Necessity: after one operation, $max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$ decrease at most one.
    120 
    121 Sufficiency: If $b_l \lt b_r$, we can do operation 2, add a right bracket at the end of string.
    122 
    123 If $b_l \gt b_r$, we can do operation 2, add a left bracket at the beginning of string.
    124 
    125 If $b_l=b_r$, assume x be the largest x that $b_x=min(b_l,b_{l+1},...,b_r)$, then $s_{x+1}=($, so we can do operation 1, cyclic shift $s[l,x+1]$ to right.
    126 
    127 Under any condition, $max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$ decrease one after one operation.
    128 
    129 We can use binary index tree to calculate $max(b_l,b_r)$ and $min(b_l,b_{l+1},...,b_r)$.
    130 
    131 **Code (tibinyte)**
    132 
    133 [**Click me**](https://pastebin.com/cPFBgXLb)
    134 
    135 **Rate Problem**
    136 
    137 Good problem
    138 
    139 Ok problem
    140 
    141 Bad problem
    142 
    143 Didn't solve it, idk
    144 
    145 # [F — Majority](https://codeforces.com/contest/1750/problem/F)
    146 
    147 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
    148 
    149 **Solution**
    150 
    151 First off, let's try to reduce the given operation to a simpler form. We claim that if it is possible to make the string $111...111$ using the specified operation, we can make it $111...111$ by doing the following new operation : Select two indices $(i,j)$ such that the substring $s_{i...j}$ looks like this $111..100...001...111$ and make it all one. The proof is just to show that if we can perform operation $(i,j)$, then it must exist some substring of $s_{i...j}$ respecting the propriety of the new operation.
    152 
    153 Let $dp_{i,j}$ be the number of binary strings of length $i$ that in the final form ( after no more operations can be made ) begin with a prefix full of ones of length $j$. For transitions, we have to iterate through the length of the next $0$ sequence and the length of the fixable prefix right after it ( such that we cannot perform an operation to make a bigger prefix, because that would break the definition ), but there is one problem -- we cannot compute $dp_{i,i}$ using any recurrence relation. Fortunately, we can compute it by subtracting the ways we get roadblocks, because, by definition $dp_{i,i}$ can be turned into $111...111$ which doesn't have any roadblocks at all. This is $O(n^4)$ if implemented naively, but one can optimize it to $O(n^2)$ by keeping prefix sums over prefix sums.
    154 
    155 **Code (tibinyte)**
    156 
    157 [**Click me**](https://pastebin.com/EACgp5PX)
    158 
    159 **Rate Problem**
    160 
    161 Good problem
    162 
    163 Ok problem
    164 
    165 Bad problem
    166 
    167 Didn't solve it, idk
    168 
    169 **Challenge: Solve the problem in $O(nlog^2)$ or $O(nlog)$ ( modulo is prime )**
    170 
    171 **Solution**
    172 
    173 [**Click me**](https://codeforces.com/blog/entry/108504?#comment-970900)
    174 
    175 # [G — Doping](https://codeforces.com/contest/1750/problem/G)
    176 
    177 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
    178 
    179 **Solution**
    180 
    181 Consider a permutation $p$ that lexicographically smaller than given permutation, assume the first different position is $k$, if we fix $p_k$, the remaining numbers $a_{k+1},a_{k+2},...,a_n$ can be arranged in any order. Denote $S$ as the set of remaining numbers. Let $m$ be the number of consecutive pairs, $m=|{x|x \in S,(x-1) \in S\cup{p_k} }|$, $p_k$ is included because it is possible that $p_{k+1}=p_k+1$. Fix the number of positions that $p_i=p_{i-1}+1$, this consumes some consecutive pairs, the remaining consecutive pairs should not increase the number of positions. Define a sequence $p$ good if and only if it has no $i$ that $p_i=p_{i-1}+1$.
    182 
    183 Consider $dp[i][j]$ = number of good arrangements of $i$ values with $j$ consecutive pairs. Consider one consecutive pair, if it is the only wrong pair, the number of values decrease by one and this situation should be excluded, otherwise this pair can be ignored, so $dp[i][j]=dp[i][j-1]-dp[i-1][j-1]$, with boundary $dp[i][0]=i!$. After enumrating $k$, let $S'={a_k,a_{k+1},...,a_n}$, $p_k$ is chosen from $S'$ and $p_k \lt a_k$. Assume $p_k=x$, if $x-1 \in S'$, the number of consecutive pairs decrease by one, otherwise it stay the same. Additionally, if $x \ne p_{k-1}+1$, the number of subarrays increase by one. For every situation, count the number of $p_k$ and then calculate answer.
    184 
    185 Time complexity: $O(n^2)$.
    186 
    187 **Solution 2**
    188 
    189 Since we have to deal with lexicographically smaller condition, it's natural to fix the common prefix $i$. Now, we can mismatch $p_{i+1}$ with some of the left values. After that, we are left with permuting the other elements.
    190 
    191 Let's say we are trying to find the number of ways to permute the remaining values {$a_1,a_2,a_3,...,a_k$} such that $a_i \neq a_{i+1}-1$ for $1 \le i \lt k$.
    192 
    193 For each $i$, we define $b_i$ to be a boolean value denoting the existence of $a_i - 1$ in set $a$.
    194 
    195 We can formulate the following 2 claims:
    196 
    197 * The number of ways to permute array $a$ only depends on $k$ and sum of $b$
    198 * For some pair $(i,j)$, the number of ways to permute $a$ starting with $a_i$ is equal to the number of ways to permute $a$ starting with $a_j$ if and only if $b_i = b_j$
    199 
    200 With these observations, we can formulate a $dp$ solution for counting permutations. Let $dp_{i,j,flag}$ be the number of ways to permute if $k=i$, $j$ is the sum of $b$, starting with a value with $b$ value equal to $flag$. Let's conclude transitions:
    201 
    202 * $dp_{i,1,true} = dp_{i-1,1,false}$
    203 * $dp_{i,1,false} = (dp_{i-1,1,true} + dp_{i-1,1,false}) \cdot (i-1)$ $-$ By claim 2, we can think of ending in the minimum value and we are left with another permutation we can transition 2.
    204 * $dp_{i,j \gt 1,true} = (dp_{i-1,j-1,true}+dp_{i-1,j-1,false}) \cdot j$ $-$ By claim 1, we can think of an equivalent array $a$ in which all values with $b_i = 1$ are left alone. Combining with claim 2, all distributions are equal, and selecting a single value makes the permutation have $j-1$ values with $b_i=1$.
    205 * $dp_{i,j \gt 1,false} = (dp_{i-1,j,false} + dp_{i-1,j,true}) \cdot (i-j)$ $-$ By claim 2, we can select any value with $b_i=0$ and combining with claim $2$, we can select the first value in the last chain.
    206 
    207 Let $sum$ be the sum of $b$.The number of ways to permute $a$ such that it respects the given demands, is $dp_{k,sum,true} + dp_{k,sum,false}$. Now the number of ways to permute $a$ with $t$ positions such that $a_i \neq a_{i+1}-1$ is $\binom{k-sum}{t-sum} \cdot (dp_{k,t,true} + dp_{k,t,false})$. This is because we can choose the values that contribute, $sum$ of them are always contributing, so we are left with choosing $t-sum$ values out of $k-sum$ possibilities.
    208 
    209 Now thinking about the values we missmatch $p_{i+1}$ with, looking at claim $2$, a lot of values are equivalent. We can count each value type separately since there are $O(1)$ types, and have a $O(n)$ complexity to update the results accordingly. Also be careful with the case where a past range of consecutive values is continued after the missmatch. It's easy to handle this because $p'_{i+1}$ is fixed and we can count it independently in $O(n)$.
    210 
    211 Thus we have achieved $O(n^2)$ total time complexity
    212 
    213 **Code (tibinyte)**
    214 
    215 [**Click me**](https://pastebin.com/dWs91GjP)
    216 
    217 **Rate Problem**
    218 
    219 Good problem
    220 
    221 Ok problem
    222 
    223 Bad problem
    224 
    225 Didn't solve it, idk
    226 
    227 # [H — BinaryStringForces](https://codeforces.com/contest/1750/problem/H)
    228 
    229 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006")
    230 
    231 **Solution**
    232 
    233 We call a maximal sequence of $0$ a $0$ block, a maximal sequence of $1$ a $1$ block.
    234 
    235 For each $i$, store some disjoint intervals with the following property:
    236 
    237 For each $j$ that $i \lt =j$ and $s[j]=1$, j is in one of the intervals if and only if $(i,j)$ is a good substring.
    238 
    239 We can prove the number of intervals for each $i$ is $O(\log n)$.
    240 
    241 Let's start from $(i,i)$ to $(i,n)$, and consider when. good substring become bad and bad substring become good.
    242 
    243 Assume we are at $(i,j)$.
    244 
    245 If it is a good substring and ending with 1, it become bad when it meet a longer 0 block, so we get one interval and go to a bad substring ending with 0.
    246 
    247 If it is a bad substring and ending with 0, suppose the next 1 is at k, then the next good intervals start at the smallest j' with three properties: (1) $(k,j')$ is good
    248 
    249 (2) $s[j']=1$
    250 
    251 (3) $(k,j')$ is not shorter than the last 0 block.
    252 
    253 Proof: Property 2 is obvious because we only care about substrings ending with 1.
    254 
    255 If $(k,j')$ is shorter than the last $0$ block, it is impossible to change this $0$ block, so $(i,j')$ is bad.
    256 
    257 If $(k,j')$ is bad, if it starts with a 1 block $(k,j")$ not shorter than the last $0$ block after some operations, then $j"$ is smaller than $j'$ and has those three properties, otherwise it is impossible to change the last $0$ block.
    258 
    259 If it has all three properties, in substring $(i,j')$, $(k,j')$ is good and can change the last $0$ block $1$, and then change $(i,j')$ to $1$, so we go to a good substring ending with 1.
    260 
    261 When good substring become bad, the length is doubled, so the number of intervals for each i is $O(logn)$.
    262 
    263 To know when good substring become bad ,for every 0 block $(j,k)$,if $(j,k)$ is longer than $(i,j-1)$, then $(i,k)$ is bad, we can preprocess those i in $O(n)$.
    264 
    265 To know when bad substring become good, we go with $i$ from $n$ to $1$ and for each $i$, search in $O(\log n)$ intervals $O(\log n)$ times.
    266 
    267 So we get those intervals in $O(n\log^2 n)$
    268 
    269 Now we can check each substring ending with $1$ is good or not. Do the above algorithm on the reversed string, so we can check each substring starting with 1 is good or not. But we can not check substring starting and ending with 0.
    270 
    271 Suppose $(i',j')$ is the longest $0$ block in $(i,j)$, then $(i,j)$ is good if at least one of $(i,i'-1)$ and $(j'+1,j)$ is good and not shorter than $(i',j')$.
    272 
    273 Proof: After changing the longest $0$ block, we can change all other $0$ blocks. So for any substring, it is good if and only if we can change its longest $0$ block.
    274 
    275 If $(i,i'-1)$ is good and not shorter, it can change $(i',j')$, so $(i,j)$ is good.
    276 
    277 If $(i,j)$ is good assume the longest 0 block is changed from left. So after some operations in $(i,i'-1)$, there is a substring $(k,i'-1)$ become all $1$ and not shorter than $(i',j')$. Then $(k,i'-1)$ can make $(i,i'-1)$ good as there is no longer $0$ block.
    278 
    279 Similarly, we can prove for $(j'+1,j)$.
    280 
    281 So for each substring, we consider its longest $0$ block (substrings with no $0$ are always good). For convenience, if there are multiple maximum, we take the rightmost.
    282 
    283 The longest $0$ block in substrings can be either a $0$ block in the original string or part of $0$ block in the original string. We can ignore substring in one $0$ block, so the longest $0$ block can only be a prefix or suffix, the number of possible longest $0$ block is $O(n)$.
    284 
    285 For each possible 0 block $(i,j)$, assume the longest substring that $(i,j)$ is the longest $0$ block is $(i',j')$, we need to count answer for substring $(l,r)$ that $i' \le l \le i,j \le r \le j'$, it is equivalent to count the number of $l$ that $i'\le l \le i-(j-i+1)$ and $(l,i-1)$ is good and the number of $r$ that $j+(j-i+1) \le r \le j'$ and $(j+1,r)$ is good.
    286 
    287 Notice that $s[i-1]=s[j+1]=1$, we can calculate them by above intervals.
    288 
    289 We can use persistent segment tree directly or use segment tree or binary index tree after sorting queries. We need $O(nlogn)$ modifications and $O(n)$ queries. Thus we have solved our problem in $O(n\log^2 n)$.
    290 
    291 **Code (tibinyte)**
    292 
    293 [**Click me**](https://pastebin.com/epzbTXuY)
    294 
    295 **Rate Problem**
    296 
    297 Good problem
    298 
    299 Ok problem
    300 
    301 Bad problem
    302 
    303 Didn't solve it, idk
    304 
    305 **#LeafTON**