codeforces-scrape

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

2137.md (15134B)


      1 Source: https://codeforces.com/blog/entry/146121
      2 
      3 **Rating Predictions**
      4 
      5 | Predictor | A | B | C | D | E | F | G |
      6 | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") | 800 | 900 | 1100 | 1200 | 1400 | 1700 | 1900 |
      8 | [Intellegent](/profile/Intellegent "Международный мастер Intellegent") | 800 | 900 | 1000 | 1200 | 1500 | 1900 | 2000 |
      9 | [RobinFromTheHood](/profile/RobinFromTheHood "Эксперт RobinFromTheHood") | 800 | 800 | 1100 | 1400 | 1600 | — |
     10 | [yse](/profile/yse "Эксперт yse") | 800 | 900 | 1100 | 1300 | 1500 | 1800 | 1900 |
     11 | [Edeeva](/profile/Edeeva "Мастер Edeeva") | 800 | 800 | 1000 | 1100 | 1400 | 1700 | 2100 |
     12 | [-firefly-](/profile/-firefly- "Мастер -firefly-") | 800 | 800 | 800 | 900 | 1400 | 1800 | 1900 |
     13 | [Non-origination](/profile/Non-origination "Эксперт Non-origination") | 800 | 1000 | 1000 | 1300 | 1400 | — | 2000 |
     14 | [satyam343](/profile/satyam343 "Мастер satyam343") | 800 | 800 | 1000 | 1200 | 1500 | 1700 | 2000 |
     15 | [reirugan](/profile/reirugan "Кандидат в мастера reirugan") | 800 | 900 | 900 | 1000 | 1600 | 1800 | 2000 |
     16 | [catgirl](/profile/catgirl "Международный мастер catgirl") | 800 | 800 | 800 | 1000 | 1600 | 1900 | 1700 |
     17 | [temporary1](/profile/temporary1 "Мастер temporary1") | 800 | 800 | 900 | 1000 | 1600 | 1900 | 1700 |
     18 
     19 #### [2137A - Гипотеза Коллатца](/contest/2137/problem/A "Codeforces Round 1047 (Div. 3)")
     20 
     21 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
     22 
     23 **Solution**
     24 
     25 The reverse of the Collatz conjecture can be written as follows:
     26 
     27 * Multiply $x$ by $2$ (if $2x$ was even)
     28 * Subtract $1$ from $x$, then divide by $3$ (if $\frac{x-1}{3}$ is an integer and is odd).
     29 
     30 In this problem, we can ignore the second type completely, because $2x$ is always an integer and is always even. We can simply print out $x\cdot 2^k$ as our answer.
     31 
     32 **Code**
     33 
     34 ```
     35 import sys
     36 input = sys.stdin.readline
     37 for _ in range(int(input())):
     38     n,k = map(int,input().split())
     39     print(k<<n)
     40 ```
     41 
     42 **Rate The Problem!**
     43 
     44 * Good Problem
     45 * Okay Problem
     46 * Bad Problem
     47 * Didn't Solve
     48 
     49 #### [2137B - Веселая перестановка](/contest/2137/problem/B "Codeforces Round 1047 (Div. 3)")
     50 
     51 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
     52 
     53 **Solution**
     54 
     55 We can show that the permutation $q$ defined by $q_i=n+1-p_i$ satisfies all required properties.
     56 
     57 * Proof $q$ is a permutation: Since $p_i+q_i=n+1$ and elements of $p$ ranges from $1$ to $n$, elements of $q$ will also range from $1$ to $n$. Additionally, since $p$ is a permutation (all elements are distinct), $q$ must also be a permutation.
     58 * Proof $GCD(p_i+q_i, p_{i+1}+q_{i+1})\geq 3$: Since $n\geq2$, $n+1\geq 3$. The GCD of any number with itself is itself.
     59 
     60 **Code**
     61 
     62 ```
     63 import sys
     64 input = sys.stdin.readline
     65 for _ in range(int(input())):
     66     n = int(input())
     67     a = list(map(int, input().split()))
     68     b = [n - i + 1 for i in a]
     69     print(*b)
     70 ```
     71 
     72 **Rate The Problem!**
     73 
     74 * Good Problem
     75 * Okay Problem
     76 * Bad Problem
     77 * Didn't Solve
     78 
     79 #### [2137C - Максимальная четная сумма](/contest/2137/problem/C "Codeforces Round 1047 (Div. 3)")
     80 
     81 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
     82 
     83 **Solution**
     84 
     85 First, observe that in order to maximize the sum of two positive numbers given that their product must stay constant, it is optimal to minimize one number as much as possible (and in the process, maximize the other).
     86 
     87 Let's do casework on the parity of $a$ and $b$:
     88 
     89 * $a$, $b$ are both even: in this case, we cannot choose a $k$ such that $\frac{b}{k}$ is odd, as $a$ will stay even, and $a+b$ will be odd. The optimal $k$ here is $\frac{b}{2}$.
     90 * $a$ is even, but $b$ is odd: In this case, we should print $-1$, as it is impossible to make $a+b$ even.
     91 * $a$ is odd, $b$ is divisible by $2$ and not $4$: This case is also impossible. No matter what $k$ we choose, one of $a$ and $b$ will always be odd.
     92 * $a$ is odd, $b$ is divisible by $4$: Even though $a+b$ is initially odd, it is possible to make $a+b$ even in this case by choosing a $k$ so that $k$ and $\frac{b}{k}$ are both even. Once again, the optimal $k$ to use is $\frac{b}{2}$.
     93 * $a$ and $b$ are both odd: In this case, the optimal $k$ to use is $b$. Note that $a+b$ will always be even no matter what $k$ is chosen.
     94 
     95 **Code**
     96 
     97 ```
     98 import sys
     99 input = sys.stdin.readline
    100 for _ in range(int(input())):
    101     b,a = map(int,input().split())
    102     sol = -1
    103     if (a + b) & 1 == 0: sol = a + b
    104     if a % 2 == 1 and b % 2 == 1: sol = max(sol, a * b + 1)
    105     elif a % 2 == 0 and (a % 4 == 0 or b % 2 == 0): sol = max(sol, 2 + (a * b) // 2)
    106     print(sol)
    107 ```
    108 
    109 **Rate The Problem!**
    110 
    111 * Good Problem
    112 * Okay Problem
    113 * Bad Problem
    114 * Didn't Solve
    115 
    116 #### [2137D - Замена по вхождениям](/contest/2137/problem/D "Codeforces Round 1047 (Div. 3)")
    117 
    118 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
    119 
    120 **Solution**
    121 
    122 First, we should observe that the number of occurrences of $x$ in $b$ must be a multiple of $x$. This is true because if we have $b_i=k$, then there are $k$ occurrences of $a_i$ in the original array. Suppose we group up all equal elements in the array $a$. If the number of occurrences of $b_i$ is not a multiple of $b_i$, then there is at least one group which doesn't have $b_i$ elements. This is a contradiction.
    123 
    124 If the number of occurrences of $b_i$ is a multiple of $b_i$ for all $i$, then we can construct as follows:
    125 
    126 * keep a varible $z=1$.
    127 * For each $x$ from $1$ to $n$, iterate through the all indices $i$ with $b_i=x$. Label the first $x$ numbers as $z$, then increase $z$ by $1$. Continue until all indices are labeled.
    128 
    129 This solution works in $O(n)$.
    130 
    131 **Code**
    132 
    133 ```
    134 import sys
    135 input = sys.stdin.readline
    136 for _ in range(int(input())):
    137     n = int(input())
    138     a = list(map(int, input().split()))
    139     FRQ = [[] for _ in range(n+1)]
    140     for i in range(n): FRQ[a[i]].append(i)
    141     b = [0 for _ in range(n)]
    142     cnt = 1
    143     for i in range(1,n+1):
    144         if len(FRQ[i]) % i: print(-1);break
    145         else:
    146             c=0
    147             while c < len(FRQ[i]):
    148                 for v in range(i):
    149                     b[FRQ[i][c]] = cnt
    150                     c+=1
    151                 cnt+=1
    152     else:print(*b)
    153 ```
    154 
    155 **Rate The Problem!**
    156 
    157 * Good Problem
    158 * Okay Problem
    159 * Bad Problem
    160 * Didn't Solve
    161 
    162 #### [2137E - Мексификация](/contest/2137/problem/E "Codeforces Round 1047 (Div. 3)")
    163 
    164 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
    165 
    166 **Solution**
    167 
    168 Let's first determine how to run the operation a single time.
    169 
    170 Let $m$ be the MEX of the array, and let $occ_i$ be the number of occurrences of the number $i$. We have these cases:
    171 
    172 * If $a_i \gt m$, then $a_i$ will become $m$.
    173 * If $occ_{a_i}=1$ and $a_i \lt m$, then $a_i$ will still be itself after the operation. This is because after we remove $a_i$ from the array, $a_i$ will be the new MEX.
    174 * if $occ_{a_i} \gt 1$ and $a_i \lt m$, then $a_i$ will become $m$. This is because even after removing $a_i$, there will still be at least one more occurrence of $a_i$, so $a_i$ will simply become the MEX of the whole array.
    175 
    176 From this, we notice that numbers with frequency $1$ and less than the MEX will not change, while other numbers will map to the MEX. We now discuss several possible cases:
    177 
    178 * If $a$ is a permutation of $[0,1,\ldots,n-1]$, then doing operations on $a$ will not change anything about the array.
    179 * Otherwise, let $x$ be the smallest number with $occ_x \neq 1$. If $occ_x=0$, then $x$ is the MEX of $a$. After the first operation, all numbers greater than $x$ will get mapped to $x$ while all numbers less than $x$ will map to themselves (because $occ_i=1$ for all $i\leq n$. Now, all occurrences of $x$ (if there are more than $1$) will map to $x+1$. The array will then continuously alter between these two states. Be careful of the edge case $[0,1,\ldots,n-2,n]$, where it will map to the permutation case and not change again.
    180 * Otherwise, $occ_x \gt 1$. Let $m$ be the MEX of $a$. After the first operation, all numbers less than $x$ will map to itself, while all occurrences of $x$ will map to $m$. This array is now the case of the previous one (where the smallest $x$ with $occ_x \neq 1$ will have $occ_x=0$), meaning that it will continuously alter between two states.
    181 
    182 In all cases, after at most two operations, the array will only alter between two states after at most one operation. So it is possible to simulate the operation $min(k, k MOD 2 + 2)$ times and print out the sum.
    183 
    184 **Code**
    185 
    186 ```
    187 import sys
    188 input = sys.stdin.readline
    189 for _ in range(int(input())):
    190     n,k = map(int,input().split())
    191     a = list(map(int,input().split())); l = []; sl = -1
    192     a.sort()
    193     while k and l != a:
    194         k -= 1
    195         sl = list(l)
    196         l = list(a)
    197         F = [0 for _ in range(n+1)]
    198         for i in a:F[i] += 1
    199         B = []
    200         mex = 0
    201         while F[mex]: mex += 1
    202         mm = 0
    203         for i in a:
    204             if F[i] > 1: B.append(mex)
    205             else: B.append(mm)
    206             if i == mm: mm += 1
    207         B.sort()
    208         a = B
    209         if a == sl:
    210             k &= 1
    211     print(sum(a))
    212 ```
    213 
    214 **Rate The Problem!**
    215 
    216 * Good Problem
    217 * Okay Problem
    218 * Bad Problem
    219 * Didn't Solve
    220 
    221 #### [2137F - Префиксная максимальная инвариантность](/contest/2137/problem/F "Codeforces Round 1047 (Div. 3)")
    222 
    223 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
    224 
    225 **Solution**
    226 
    227 What is the condition for being able to make $x_i=y_i$? It is always possible if $x_i=y_i$ already. If $x_i \gt y_i$, it's only possible if $a_i$ is not already a prefix maximum. If $x_i \lt y_i$, it's only possible if there is a prefix maximum in the array before $i$ that is at least equal to $y_i$.
    228 
    229 Let's formalize the conditions for the last two cases. If $x_i \gt y_i$, then there must exist an index $j \lt i$ such that $x_j \gt x_i$ (as this guarantees $a_i$ to not be a prefix maximum). If $x_i \lt y_i$, then there must exist an index $j \lt i$ such that $x_j \geq y_i$, as this ensures you can change $x_i$ to $y_i$. Let's calculate the correct $j$ for each $i$ in the original array $a$. This can be done in a variety of data structures. I used a set, but it is possible to use a segment tree or a stack as well.
    230 
    231 Finally, to find the sum over all subarrays in $a$, for each index $i$ we need to calculate the number of subarrays containing $i$ where we can make $a_i=b_i$. If $x_i=y_i$, all subarrays containing $i$ counts, so we add $(i)(n-i+1)$ to our answer. Otherwise, let $prev_i$ be the number we calculated before. We can add $(i-prev_i+1)(n-i+1)$ to our answer.
    232 
    233 **Code**
    234 
    235 ```
    236 import sys
    237 input = sys.stdin.readline
    238 class SparseTarble():
    239     def __init__(self,arr,op=min):
    240         self.n = len(arr)
    241         self.log = self.n.bit_length()
    242         self.PRE = [0 for _ in range(self.log * self.n)]
    243         for i in range(self.n):
    244             lsb = (i+1) & (-i-1)
    245             v = lsb.bit_length() - 1
    246             jo = self.n * v
    247             self.PRE[jo + i] = arr[i]
    248             for j in range(i+1,min(self.n,i+lsb)):
    249                 self.PRE[jo + j] = op(self.PRE[jo+j-1],arr[j])
    250             for j in range(i-1, i - lsb, -1):
    251                 self.PRE[jo + j] = op(arr[j],self.PRE[jo+j+1])
    252         self.op = op
    253     def query(self,l,r):
    254         assert(l < r)
    255         bit = (r ^ l).bit_length() - 1
    256         return self.op(self.PRE[bit * self.n + l], self.PRE[bit * self.n + r - 1])
    257 for _ in range(int(input())):
    258     n = int(input())
    259     a = list(map(int,input().split()))
    260     b = list(map(int,input().split()))
    261     sq = SparseTarble(a,max)
    262     sol = 0
    263     for i in range(n):
    264         if a[i] == b[i]: sol += (n * n + n) // 2; continue
    265         lo = -1; hi = i
    266         while lo + 1 < hi:
    267             mid = (lo + hi) // 2
    268             if sq.query(mid,i) >= max(a[i],b[i]): lo = mid
    269             else: hi = mid
    270         lo+=1
    271         sol += lo * (n - i)
    272     print(sol)
    273 ```
    274 
    275 **Rate The Problem!**
    276 
    277 * Good Problem
    278 * Okay Problem
    279 * Bad Problem
    280 * Didn't Solve
    281 
    282 #### [2137G - Плачь, река](/contest/2137/problem/G "Codeforces Round 1047 (Div. 3)")
    283 
    284 Problem Credits: [SpyrosAliv](/profile/SpyrosAliv "Специалист SpyrosAliv")
    285 
    286 **Solution**
    287 
    288 Let $dp_1(i)$ be a boolean on whether Cry will win if the token is on node $i$ and it is currently Cry's turn, and let $dp_2(i)$ be a boolean on whether Cry will win a game if we are on node $i$ and it is currently River's turn. Initially, $dp_1(i)=1$ and $dp_2(i)=1$ for all $1 \leq i \leq n$. Assuming we maintain the correct $dp$ values all the time, queries of the second type is easily answered by looking at the dp state.
    289 
    290 How can we maintain the correct $dp$ values after a node is painted red? Consider BFS on the reverse graph. Suppose node $u$ was turned red. First, node $u$ becomes winning for River immediately no matter whose turn it is. Now, if a node becomes losing on Cry's turn, all nodes that are adjacent to that node in the reverse graph becomes winning on River's turn (as River can move the node to a node that loses on Cry's turn). If a node becomes losing on River's turn, consider the set of nodes adjacent on the reverse graph. If all nodes adjacent to that node (on the original graph) is losing on River's turn, then that node is also losing on Cry's turn, as no matter which node he decides to move to, it will be going to a lost node.
    291 
    292 Keeping track of the DP states seems like it will be $O(n^2)$ complexity. However, since each node is visited only twice (once for updating $dp_1$ and once for updating $dp_2$, this solution will amortize to $O(n+m)$. Keep note that we should maintain a third array that counts how many adjacent nodes are losing on River's turn, so we don't have to check manually every time.
    293 
    294 **Code**
    295 
    296 ```
    297 import sys
    298 input = sys.stdin.readline
    299 for _ in range(int(input())):
    300     n,m,q = map(int,input().split())
    301     G = [[] for _ in range(n+1)]
    302     A = [1 for _ in range(n+1)]
    303     B = [0 for _ in range(n+1)]
    304     C = [0 for _ in range(n+1)]
    305     for _ in range(m):
    306         a,b = map(int,input().split())
    307         G[b].append(a)
    308         C[a] += 1
    309     for _ in range(q):
    310         a,b = map(int,input().split())
    311         if a == 2:
    312             if A[b]: print("yes")
    313             else: print("no")
    314         else:
    315             q = []
    316             if A[b] == 1: q.append((b,0))
    317             if B[b] == 0: q.append((b,1)); B[b] = 1
    318             for x,t in q:
    319                 if t:
    320                     for c in G[x]:
    321                         C[c] -= 1
    322                         if C[c] == 0:
    323                            q.append((c,0))
    324                 else:
    325                     if A[x] == 0: continue
    326                     A[x] = 0
    327                     for c in G[x]:
    328                         if B[c]: continue
    329                         B[c] = 1
    330                         q.append((c,1))
    331 ```
    332 
    333 **Rate The Problem!**
    334 
    335 * Good Problem
    336 * Okay Problem
    337 * Bad Problem
    338 * Didn't Solve