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