1543.md (40389B)
1 Source: https://codeforces.com/blog/entry/92582 2 3 #### [A: Exciting Bets](https://codeforces.com/contest/1543/problem/A) 4 5 **Hint 1** 6 7 $GCD(a,b)=GCD(a-b,b)$ if $a \gt b$ 8 9 **Hint 2** 10 11 $a-b$ does not change by applying any operation. However, $b$ can be changed arbitrarily. 12 13 **Tutorial** 14 15 If $a=b$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times. 16 17 Otherwise, the maximum excitement the fans can get is $g=\lvert a-b\rvert$ and the minimum number of moves required to achieve it is $min(a\bmod g,g-a\bmod g)$. 18 19 **Proof** 20 21 Without loss of generality, assume $a \gt b$ otherwise we can swap $a$ and $b$. We know that $GCD(a,b) = GCD(a-b,b)$. Notice that no matter how many times we apply any operation, the value of $a-b$ does not change. We can arbitrarily change the value of $b$ to a multiple of $a-b$ by applying the operations. In this way, we can achieve a $GCD$ equal to $a-b$. Now, since $GCD(x,y)\leq min(x,y)$ for any positive $x$ and $y$, $GCD(a-b,b)$ can never exceed $a-b$. So, we cannot achieve a higher GCD by any means. 22 23 To achieve the required $GCD$, we need to make $b$ a multiple of $g=a-b$ using as few operations as possible. There are two ways to do so $-$ decrease $b$ to the largest multiple of $g$ less than or equal to $b$ or increase $b$ to the smallest multiple of $g$ greater than $b$. The number of operations required to do so are $b\bmod g$ and $g-b\bmod g$ respectively. We will obviously choose the minimum of the two. Also notice that $a\bmod g=b\bmod g$ since $a=b+g$. So, it doesn't matter if we use either $a$ or $b$ to determine the minimum number of operations. 24 25 **Time Complexity** 26 27 $\mathcal{O}(1)$ per test case. 28 29 **Solution** 30 31 ``` 32 #include <bits/stdc++.h> 33 using namespace std; 34 35 int main() 36 { 37 ios_base::sync_with_stdio(false); 38 cin.tie(NULL); 39 int t; 40 cin >> t; 41 while(t--) 42 { 43 long long a,b; 44 cin >> a >> b; 45 if(a==b) 46 cout << 0 << " " << 0 << '\n'; 47 else 48 { 49 long long g = abs(a-b); 50 long long m = min(a%g,g-a%g); 51 cout << g << " " << m << '\n'; 52 } 53 } 54 } 55 ``` 56 57 #### [B: Customising the Track](https://codeforces.com/contest/1543/problem/B) 58 59 **Hint** 60 61 In the optimal arrangement, the number of cars will be distributed as evenly as possible. 62 63 **Tutorial** 64 65 In the optimal arrangement, the number of traffic cars will be distributed as evenly as possible, *i.e.*, $\lvert a_i-a_j\rvert\leq 1$ for each valid $(i,j)$. 66 67 **Proof (Warning: Too much Math inside)** 68 69 Let's sort the array in non-decreasing order. Let $a_1=p$, $a_n=q$, $p\leq q-2$, $x$ elements of the array be equal to $p$, $y$ elements of the array be equal to $q$, $\displaystyle\sum\limits_{i=x+1}^{n-y}\sum\limits_{j=i+1}^{n-y} a_j-a_i=r$ and $\displaystyle\sum\limits_{i=x+1}^{n-y} a_i=s$. 70 71 The inconvenience of the track will be equal to $S_1=r+x\cdot[s-(n-x-y)\cdot p]+y\cdot[(n-x-y)\cdot q-s]+[xy\cdot(q-p)]$ 72 73 Suppose we increase $a_1$ by $1$ and decrease $a_n$ by $1$. Then, the number of occurrences of $p$ and $q$ will reduce by $1$, two new elements $p+1$ and $q-1$ will be formed, and $r$ and $s$ will remain unchanged. In such a case, the new inconvenience of the track will be $S_2=r+(x-1)\cdot[s-(n-x-y)\cdot p]$ $+(y-1)\cdot[(n-x-y)\cdot q-s]$ $+[(x-1)\cdot(y-1)\cdot(q-p)]$ $+[s-(n-x-y)\cdot(p+1)]$ $+[(n-x-y)\cdot(q-1)-s]$ $+[(y-1)\cdot(q-p-1)]$ $+[(x-1)\cdot(q-p-1)]$ $+(x-1)+(y-1)+(q-p-2)$ 74 75 Change in inconvenience, $\Delta = S_1-S_2 = [s-(n-x-y)\cdot p]+[(n-x-y)\cdot q-s]+[(x+y-1)\cdot(q-p)]$ $-[s-(n-x-y)\cdot(p+1)]$ $-[(n-x-y)\cdot (q-1)-s]$ $-[(y-1)\cdot(q-p-1)]$ $-[(x-1)\cdot(q-p-1)]$ $-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y)+(x+y-1)\cdot(q-p)-(x+y-2)\cdot(q-p-1)-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y)+(q-p)+(x+y-1)-1-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y+1) \gt 0$ as $x+y\leq n$. 76 77 So, it follows that if $p\leq q-2$. it is always beneficial to move a traffic car from the sub-track with the highest number of traffic cars to the sub-track with the lowest number of traffic cars. If $p=q-1$, applying this operation won't change the inconvenience as this will only swap the last and the first element of the array leaving everything else unchanged. If $p=q$, all the elements of the array are already equal, meaning that we have $0$ inconvenience which is the minimum possible. So, there is no point in applying any operation. 78 79 Now that we have constructed the optimal arrangement of traffic cars, let's find out the value of minimum inconvenience of this optimal arrangement. Finding it naively in $\mathcal{O}(n^2)$ will time out. 80 81 Notice that in the optimal arrangement we will have some (say $x$) elements equal to some number $p+1$ and the other $(n-x)$ elements equal to $p$. Let the sum of all elements in $a$ be $sum$. Then, $x=sum\bmod n$ and $p=\bigg\lfloor\dfrac{sum}{n}\bigg\rfloor$. For each pair $(p,p+1)$, we will get an absolute difference of $1$ and for all other pairs, we will get an absolute difference of $0$. Number of such pairs with difference $1$ is equal to $x\cdot(n-x)$. So, the minimum inconvenience we can achieve is equal to $x\cdot(n-x)$. That's all we need to find out! 82 83 **Time Complexity** 84 85 $\mathcal{O}(n)$ 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 using namespace std; 92 93 int main() 94 { 95 ios_base::sync_with_stdio(false); 96 cin.tie(NULL); 97 int t; 98 cin >> t; 99 while(t--) 100 { 101 int n; 102 cin >> n; 103 int a[n]; 104 long long s=0; 105 for(int i=0;i<n;i++) 106 { 107 cin >> a[i]; 108 s+=a[i]; 109 } 110 long long k = s%n; 111 long long ans = k*(n-k); 112 cout << ans << '\n'; 113 } 114 } 115 ``` 116 117 #### [C: Need for Pink Slips](https://codeforces.com/contest/1543/problem/C) 118 119 **Hint 1** 120 121 Did you notice that $v\geq 0.1$? 122 123 **Hint 2** 124 125 The probability of drawing a pink slip can never decrease. 126 127 **Hint 3** 128 129 What would be the complexity of a bruteforce solution? 130 131 **Hint 4** 132 133 Make sure to account for precision errors while comparing floating point numbers. 134 135 **Tutorial** 136 137 Bruteforce over all the possible drawing sequences until we are sure to get a pink slip, *i.e.*, until the probability of drawing a pink slip becomes $1$. 138 139 **Why this works?** 140 141 Whenever we draw a reward other than a pink slip, 142 143 * If $a\leq v$, one of the rewards becomes invalid, reducing $x$ by $1$ and this can happen at most $2$ times during the whole process. 144 * Else, the probability of drawing a pink slip increases by $\dfrac{v}{2}$. 145 146 Notice that the probability of drawing a pink slip can never decrease. 147 148 Now, since $v\geq 0.1$, each time we make a draw of the second type, the probability of drawing a pink slip increases by at least $0.05$. It will reach $1$ after just $20$ such draws. So, there will be at most $d=22$ draws before we are sure to get a pink slip. 149 150 Simulating the whole process will take $\mathcal{O}(2^d)$ time which is sufficient in our case. 151 152 What's left is just implementing the bruteforce solution taking care of precision errors while dealing with floating point numbers, especially while comparing $a$ with $v$ as this can completely change things up, keeping an item valid when it should become invalid. It follows that an error approximation of `1e-6` or smaller is sufficient while comparing any two values because all the numbers in the input have at most $4$ decimal places. Another alternative is to convert floating point numbers given in the input to integers using a scaling factor of $10^6$. 153 154 **Time Complexity** 155 156 $\mathcal{O}\big(2^{\frac{2}{v}}\big)$ 157 158 **Solution** 159 160 ``` 161 #include <bits/stdc++.h> 162 using namespace std; 163 164 const long double eps = 1e-9; 165 const long double scale = 1e+6; 166 167 long double expectedRaces(int c,int m,int p,int v) 168 { 169 long double ans = p/scale; 170 if(c>0) 171 { 172 if(c>v) 173 { 174 if(m>0) 175 ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v)); 176 else 177 ans += (c/scale)*(1+expectedRaces(c-v,0,p+v,v)); 178 } 179 else 180 { 181 if(m>0) 182 ans += (c/scale)*(1+expectedRaces(0,m+c/2,p+c/2,v)); 183 else 184 ans += (c/scale)*(1+expectedRaces(0,0,p+c,v)); 185 } 186 } 187 if(m>0) 188 { 189 if(m>v) 190 { 191 if(c>0) 192 ans += (m/scale)*(1+expectedRaces(c+v/2,m-v,p+v/2,v)); 193 else 194 ans += (m/scale)*(1+expectedRaces(0,m-v,p+v,v)); 195 } 196 else 197 { 198 if(c>0) 199 ans += (m/scale)*(1+expectedRaces(c+m/2,0,p+m/2,v)); 200 else 201 ans += (m/scale)*(1+expectedRaces(0,0,p+m,v)); 202 } 203 } 204 return ans; 205 } 206 207 int main() 208 { 209 int t; 210 cin >> t; 211 while(t--) 212 { 213 long double cd,md,pd,vd; 214 cin >> cd >> md >> pd >> vd; 215 int c = round(cd*scale); 216 int m = round(md*scale); 217 int p = round(pd*scale); 218 int v = round(vd*scale); 219 long double ans = expectedRaces(c,m,p,v); 220 cout << setprecision(12) << fixed << ans << '\n'; 221 } 222 } 223 ``` 224 225 #### [D1: RPD and Rap Sheet (Easy Version)](https://codeforces.com/contest/1543/problem/D1) 226 227 **Hint 1** 228 229 In this version, $x\oplus z=y$ or in other words, $z=x\oplus y$ where $\oplus$ is the Bitwise XOR operator. 230 231 **Hint 2** 232 233 The number of queries allowed is equal to the number of possible initial passwords. 234 235 **Hint 3** 236 237 The grader provides us no information other than whether our guess was correct or not. So, we need to find a way to ask queries such that the $x$-th query will give the correct answer if the original password was $(x-1)$. 238 239 **Hint 4** 240 241 Try to ask queries in such a way that the $i$-th query reverses the effect of the $(i-1)$-th query and simultaneously checks if the initial password was $(i-1)$. 242 243 **Hint 5** 244 245 Try to use the self-inverse property of Bitwise XOR, *i.e.*, $a\oplus a=0$. 246 247 **Tutorial** 248 249 In this version of the problem, $k=2$. So, the $k$-itwise XOR is the same as Bitwise XOR. 250 251 In case of incorrect guess, the system changes password to $z$ such that $x\oplus z=y$. Taking XOR with $x$ on both sides, $x\oplus x\oplus z=x\oplus y\implies z=x\oplus y$ because we know that $x\oplus x = 0$. 252 253 Since the original password is less than $n$ and we have $n$ queries, we need to find a way to make queries such that if the original password was $(x-1)$, then the $x$-th query will be equal to the current password. There are many different approaches. I will describe two of them. 254 255 **Method 1** 256 257 Let $q_i$ denote the $i$-th query. Then, 258 259 * $q_1=0$. 260 * $q_i=(i-1)\oplus (i-2)$ for $2\leq i\leq n$. 261 262 Let's see why this works. 263 264 Claim — If the original password was $x$, after $i$ queries, the current password will be $x\oplus (i-1)$. 265 266 **Proof** 267 268 Let's prove this by induction. 269 270 Base Condition — After $1$-st query, the password becomes $x\oplus 0=x\oplus(1-1)$. 271 272 Induction Hypothesis — Let the password after $i$-th query be $x\oplus (i-1)$. 273 274 Inductive step — The $(i+1)$-th query will be $i\oplus(i-1)$. If this is not equal to the current password, the password will change to $(x\oplus(i-1))\oplus(i\oplus(i-1))$ $=x\oplus(i-1)\oplus i\oplus(i-1)$ $=x\oplus i$ $=x\oplus((i+1)-1)$. 275 276 Hence, proved by induction. 277 278 Now notice that after $x$ queries, the password will become $x\oplus(x-1)$. And our $(x+1)$-th query will be $x\oplus(x-1)$ which is the same as the current password. So, the problem will be solved after $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved in at most $n$ queries. 279 280 **Method 2 (Idea by KAN)** 281 282 Again, let $q_i$ denote the $i$-th query. Then, 283 284 $q_i=(i-1)\oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-2} \oplus q_{i-1}$ 285 286 Let's see why this works. 287 288 Claim — If the original password was $x$, after $i$ queries, the current password will be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$. 289 290 **Proof** 291 292 Let's prove this by induction. 293 294 Base Condition — The first query is $0$. After $1$-st query, the password becomes $x\oplus 0=x\oplus q_1$. 295 296 Induction Hypothesis — Let the password after $i$-th query be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$. 297 298 Inductive step — The $(i+1)$-th query will be $q_{i+1}$. So, the password after $(i+1)$-th query will be $(x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i})\oplus q_{i+1}$ $= x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}\oplus q_{i+1}$. 299 300 Hence, proved by induction. 301 302 Now notice that after $x$ queries, the password will become $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$. And our $(x+1)$-th query will be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$ which is the same as the current password. So, the problem will be solved after $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved in at most $n$ queries. 303 304 But we are not done yet. We can't afford to calculate the value of each query naively in $\mathcal{O}(n)$ because this will time out. To handle this, we need to maintain a prefix XOR whose value will be $p=q_1\oplus q_2\oplus \ldots \oplus q_{i-1} \oplus q_i$ after $i$ queries. For the $(i+1)$-th query, find $q_{i+1}=p\oplus i$ and update $p=p\oplus q_{i+1}$. 305 306 **Time Complexity** 307 308 $\mathcal{O}(n)$ or $\mathcal{O}(n\cdot \log_{2} n)$ depending upon the implementation. 309 310 **Solutions** 311 312 **Solution 1** 313 314 ``` 315 #include <bits/stdc++.h> 316 using namespace std; 317 318 int main() 319 { 320 int t=1; 321 cin >> t; 322 while(t--) 323 { 324 int n,k; 325 cin >> n >> k; 326 for(int i=0;i<n;i++) 327 { 328 if(i==0) 329 cout << 0 << endl; 330 else 331 cout << (i^(i-1)) << endl; 332 int v; 333 cin >> v; 334 if(v==1) 335 break; 336 } 337 } 338 return 0; 339 } 340 ``` 341 342 **Solution 2** 343 344 ``` 345 #include <bits/stdc++.h> 346 using namespace std; 347 348 int main() 349 { 350 int t=1; 351 cin >> t; 352 while(t--) 353 { 354 int n,k; 355 cin >> n >> k; 356 int p=0; 357 for(int i=0;i<n;i++) 358 { 359 int q=p^i; 360 cout << q << endl; 361 p=p^q; 362 int v; 363 cin >> v; 364 if(v==1) 365 break; 366 } 367 } 368 return 0; 369 } 370 ``` 371 372 #### [D2: RPD and Rap Sheet (Hard Version)](https://codeforces.com/contest/1543/problem/D2) 373 374 **Hint 1** 375 376 The generalised $k$-itwise XOR does not satisfy the Self-Inverse property. So, the solution for the Easy Version won't work here. 377 378 **Hint 2** 379 380 Any property which is satisfied by $k$-its will also be satisfied by base $k$ numbers since a base $k$ number is nothing but a concatenation of $k$-its. So, try to prove properties for $k$-its as they are easier to work with. 381 382 **Hint 3** 383 384 Let $x_j$ denote the $j$-th $k$-it of $x$. Then, $x_j\oplus_k z_j=y_j$ $\forall$ valid $j$. Simplifying this, 385 $x_j\oplus_k z_j=y_j$ $\implies$ $(x_j+z_j)\bmod k=y_j$ $\implies$ $z_j=(y_j-x_j)\bmod k$ $\implies$ $z_j=(y_j\ominus_k x_j)$ where $a\ominus_k b$ operation is defined as $a\ominus_k b=(a-b)\bmod k$. 386 387 **Hint 4** 388 389 See Hints 2, 3 and 4 of the Easy Version. 390 391 **Hint 5** 392 393 Try to generalise the solutions for easy version by exploring properties of $\oplus_k$ and $\ominus_k$ operators. 394 395 **Tutorial** 396 397 Note — It is strongly recommended to read the proofs also to completely understand why the solutions work. 398 399 The solutions described for the easy version won't work here because the general $k$-itwise operation does not satisfy self-inverse property, *i.e.*, $a\oplus_k a\neq 0$. 400 401 In this whole solution, we will work in base $k$ only and we will convert the numbers to decimal only for I/O purpose. Notice that any property which is satisfied by $k$-its will also be satisfied by base $k$ numbers since a base $k$ number is nothing but a concatenation of $k$-its. 402 403 When we make an incorrect guess, the system changes the password to $z$ such that $x\oplus_k z=y$. Let's denote the $j$-th $k$-it of $x$ by $x_j$. Expanding this according to the definition of $k$-itwise XOR, for all individual $k$-its $(x_j+z_j)\bmod k=y_j$ $\implies z_j=(y_j-x_j)\bmod k$. So, let's define another $k$-itwise operation $a\ominus_k b$ $= (a-b)\bmod k$. Then, $z=y\ominus_k x$. Now, let's extend the solutions of the Easy Version for this version. 404 405 **Method 1** 406 407 Before moving to the solution, let's see some properties of the $\ominus_k$ operation over $k$-its. 408 409 Property 1 — $(a\ominus_k b)\ominus_k(a\ominus_k c)=c\ominus_k b$ 410 411 **Proof** 412 413 $(a\ominus_k b)\ominus_k(a\ominus_k c)$ $= ((a-b)\bmod k - (a-c)\bmod k)\bmod k$ $=(a-b-a+c)\bmod k$ $=(c-b)\bmod k$ $= c\ominus_k b$ 414 415 Property 2 — $(b\ominus_k a)\ominus_k(c\ominus_k a)=b\ominus_k c$ 416 417 **Proof** 418 419 $(b\ominus_k a)\ominus_k(c\ominus_k a)$ $= ((b-a)\bmod k - (c-a)\bmod k)\bmod k$ $=(b-a-c+a)\bmod k$ $=(b-c)\bmod k$ $= b\ominus_k c$ 420 421 Solution - 422 423 Let $q_i$ denote the $i$-th query. Then, 424 425 * $q_1=0$, 426 * $q_i=(i-2)\ominus_k (i-1)$ if $i$ is even and 427 * $q_i=(i-1)\ominus_k (i-2)$ if $i$ is odd. 428 429 Let's see why this works. 430 431 Claim — If the original password was $x$, after $i$ queries, the password becomes 432 433 * $x\ominus_k (i-1)$ if $i$ is even and 434 * $(i-1)\ominus_k x$ if $i$ is odd. 435 436 **Proof** 437 438 Let's prove this by induction. 439 440 Base Case — $q_1=0$. So, after $1$-st query, the password becomes $0\ominus_k x = (1-1)\ominus_k x$. 441 442 **Case 1 — $i$ is even** 443 444 Induction hypothesis — Let the current password after $i$ queries be $x\ominus_k (i-1)$. 445 446 Inductive step — $(i+1)$ is odd. So, the $(i+1)$-th query is $i\ominus_k (i-1)$. The new password will be $(i\ominus_k (i-1))\ominus_k(x\ominus_k (i-1))$ $= i\ominus_k x$ by Property 2. 447 448 **Case 2 — $i$ is odd** 449 450 Induction hypothesis — Let the current password after $i$ queries be $(i-1)\ominus_k x$. 451 452 Inductive step — $(i+1)$ is even. So, the $(i+1)$-th query is $(i-1)\ominus_k i$. The new password will be $((i-1)\ominus_k i)\ominus_k((i-1)\ominus_k x)$ $= x\ominus_k i$ by Property 1. 453 454 Hence, proved by induction. 455 456 Now notice that after $x$ queries, the password will become $x\ominus_k (x-1)$ if $x$ is even or $(x-1)\ominus_k x$ if $x$ is odd which will be equal to the $(x+1)$-th query. Hence, the problem will be solved after exactly $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved after at most $n$ queries. 457 458 **Method 2** 459 460 Again, let's denote the $i$-th query by $q_i$. 461 462 Then, $q_i=q_{i-1}\ominus_k\bigg[q_{i-2}\ominus_k\Big[q_{i-3}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k(i-1)]\big]\ldots\Big]\bigg]$ 463 464 Let's see why this works. 465 466 Claim — If the original password was $x$, after $i$ queries, the password will be $q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$ 467 468 **Proof** 469 470 Let's prove this by induction. 471 472 Base Case — After the $1$-st query which is $0$, the password will be $0\ominus_k x = q_1\ominus_k x$. 473 474 Induction hypothesis — Let the password after $i$ queries be $q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$ 475 476 Inductive Step — The $(i+1)$-th query is $q_{i+1}$. After $(i+1)$ queries, the password will becomes $q_{i+1}\ominus_k\Bigg[q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]\Bigg]$ 477 478 Hence, proved by induction. 479 480 Now notice that after $x$ queries, the password will become $q_{x}\ominus_k\bigg[q_{x-1}\ominus_k\Big[q_{x-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$ which will be equal to the $(x+1)$-th query. Hence, the problem will be solved after exactly $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved after at most $n$ queries. 481 482 But we are not done yet. This solution is $\mathcal{O}(n^2)$ which will time out. The solution for this isn't as simple as what we did for the Easy version because the $\ominus_k$ operation is neither associative nor commutative. So, it's time to explore some more properties of these operations. 483 484 Property 3 — $a\ominus_k(b\ominus_k c) = (a\ominus_k b)\oplus_k c$ 485 486 **Proof** 487 488 $a\ominus_k(b\ominus_k c)$ $= (a-(b-c)\bmod k)\bmod k$ $= (a-b+c)\bmod k$ $= ((a-b)\bmod k+c)\bmod k$ $= (a\ominus_k b)\oplus_k c$ 489 490 Property 4 — $a\ominus_k(b\oplus_k c) = (a\ominus_k b)\ominus_k c$ 491 492 **Proof** 493 494 $a\ominus_k(b\oplus_k c)$ $= (a-(b+c)\bmod k)\bmod k$ $= (a-b-c)\bmod k$ $= ((a-b)\bmod k-c)\bmod k$ $= (a\ominus_k b)\ominus_k c$ 495 496 Now, let's try to simplify our queries. 497 498 * $q_1=0$ 499 * $q_2=q_1\ominus_k 1$ 500 * $q_3=q_2\ominus_k [q_1\ominus_k 2]=[q_2\ominus_k q_1]\oplus_k 2$ (by Property 3) 501 * $q_4=q_3\ominus_k \big[q_2\ominus_k [q_1\ominus_k 3]\big]=q_3\ominus_k \big[[q_2\ominus_k q_1]\oplus_k 3\big]=\big[q_3\ominus_k[q_2\ominus_k q_1]\big]\ominus_k 3$ (by Property 4) 502 * $\ldots$ 503 504 See the pattern? 505 506 You can generalize the $i$-th query as - 507 508 * $q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\oplus_k (i-1)$ if $i$ is odd 509 * $q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\ominus_k (i-1)$ if $i$ is even 510 511 So, we will maintain a prefix Negative XOR whose value after $i$ queries will be $p=q_{i}\ominus_k\Big[q_{i-1}\ominus_k\big[q_{i-2}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]$ 512 513 Then, 514 515 * $q_{i+1}=p\ominus_k i$ if $i$ is odd 516 * $q_{i+1}=p\oplus_k i$ if $i$ is even 517 518 Then update $p=q_{i+1}\ominus_k p$ 519 520 **Notes** 521 522 * Both the operations $\ominus_k$ and $\oplus_k$ can be implemented naively by converting the decimal numbers to base $k$, finding the $k$-itwise XOR of the base $k$ numbers and finally converting it back to decimal. The time complexity for each of these operations will be $\mathcal{O}(\log_k n)$. 523 * At any stage, the maximum number that we could be dealing with will be non-negative and will not exceed $n\times k$ as the $k$-itwise operations do not add extra $k$-its. This fits well within the limits of $y$ which is $2\cdot 10^7$. 524 * The total time complexity of the solution will be $\mathcal{O}(n\log_k n)$. 525 526 **Solutions** 527 528 **Solution 1** 529 530 ``` 531 #include <bits/stdc++.h> 532 using namespace std; 533 534 int knxor(int x,int y,int k) 535 { 536 int z=0; 537 int p=1; 538 while(x>0 || y>0) 539 { 540 int a=x%k; 541 x=x/k; 542 int b=y%k; 543 y=y/k; 544 int c=(a-b+k)%k; 545 z=z+p*c; 546 p=p*k; 547 } 548 return z; 549 } 550 551 int main() 552 { 553 int t=1; 554 cin >> t; 555 while(t--) 556 { 557 int n,k; 558 cin >> n >> k; 559 for(int i=0;i<n;i++) 560 { 561 if(i==0) 562 cout << 0 << endl; 563 else if(i%2==0) 564 cout << knxor(i,i-1,k) << endl; 565 else 566 cout << knxor(i-1,i,k) << endl; 567 int v; 568 cin >> v; 569 if(v==1) 570 break; 571 } 572 } 573 return 0; 574 } 575 ``` 576 577 **Solution 2** 578 579 ``` 580 #include <bits/stdc++.h> 581 using namespace std; 582 583 int knxor(int x,int y,int k) 584 { 585 int z=0; 586 int p=1; 587 while(x>0 || y>0) 588 { 589 int a=x%k; 590 x=x/k; 591 int b=y%k; 592 y=y/k; 593 int c=(a-b+k)%k; 594 z=z+p*c; 595 p=p*k; 596 } 597 return z; 598 } 599 600 int kxor(int x,int y,int k) 601 { 602 int z=0; 603 int p=1; 604 while(x>0 || y>0) 605 { 606 int a=x%k; 607 x=x/k; 608 int b=y%k; 609 y=y/k; 610 int c=(a+b)%k; 611 z=z+p*c; 612 p=p*k; 613 } 614 return z; 615 } 616 617 int main() 618 { 619 int t=1; 620 cin >> t; 621 while(t--) 622 { 623 int n,k; 624 cin >> n >> k; 625 int p=0; 626 for(int i=0;i<n;i++) 627 { 628 if(i==0) 629 cout << 0 << endl; 630 else if(i%2==0) 631 { 632 int q = kxor(p,i,k); 633 cout << q << endl; 634 p=knxor(q,p,k); 635 } 636 else 637 { 638 int q = knxor(p,i,k); 639 cout << q << endl; 640 p=knxor(q,p,k); 641 } 642 int v; 643 cin >> v; 644 if(v==1) 645 break; 646 } 647 } 648 return 0; 649 } 650 ``` 651 652 **About the Adaptive Grader** 653 654 This part may be interesting for hackers and those who would like to understand what goes in the background checkers and interactors which determine the correctness of their solutions. 655 656 You must have noticed a large number of submissions failing on Test 1 itself. If you check the checker logs of those solutions, you will find that they fail on many different test cases although the test itself has 1 or 2 test cases. This is because the grader is also adaptive apart from the Rap Sheet System being adaptive. The initial password is not fixed and the grader checks if the solution will give correct answer or not for all possible initial passwords in just a single run! Here is how this is implemented. 657 658 The grader maintains a set which initially contains all possible initial passwords. Whenever you ask a query, the grader finds out which initial password will give correct answer for this query. This is found using the generalised expression of queries derived in the Method 2 solution. Take some time to convince yourself that this initial password will be unique. It then removes this initial password from the set if it still exists. After that, if the set is empty, the grader returns 1 (meaning that there is no other password for which the solution can give Wrong Answer), otherwise 0 (obviously after checking the constraints on $y$). In this way, only a solution which gives correct answers for all possible initial passwords for a particular $n$ and $k$ defined in the input will manage to pass. 659 660 Sometimes, checkers and adaptive interactors are more difficult to write than the solution itself! This was one such case. 661 662 #### [E: The Final Pursuit](https://codeforces.com/contest/1543/problem/E) 663 664 **Hint 1** 665 666 In a simple $n$-Dimensional Hypercube, two vertices are connected if and only if they differ by exactly $1$ bit in their binary representation. 667 668 **Hint 2** 669 670 The $n$-Dimensional Hypercubes are highly symmetric and all vertices are equivalent. 671 672 **Hint 3** 673 674 If we select a particular vertex, then all directions in which the edges connected to it goes are also equivalent. 675 676 **Hint 4** 677 678 For any two vertices $a$ and $b$ separated at a distance of exactly $2$, there are exactly $2$ vertices connected to both $a$ and $b$. 679 680 **Hint 5** 681 682 Any permuted $n$-Dimensional Hypercube is isomorphic to the simple $n$-Dimensional Hypercube. So, its structure is same as the simple $n$-Dimensional Hypercube. 683 684 **Hint 6** 685 686 You can find the permutation greedily 687 688 **Tutorial: Part 1 - Finding the Permutation** 689 690 Before moving to the solution, notice a very important property of simple $n$-Dimensional Hypercubes — Two vertices $a$ and $b$ are connected if and only if $a$ and $b$ differ by exactly one bit in their binary representations. 691 692 The permutation can be found using the following greedy algorithm — First, assign any arbitrary vertex as $p_0$. This is obvious since all vertices are equivalent. Then, in the simple $n$-Dimensional Hypercube, all powers of $2$ must be connected to the vertex $0$. Moreover, these vertices are added only when we are adding another dimension to the cube. Since all directions are also equivalent, it does not matter in which direction we add a new dimension. So, we can assign all the $n$ vertices connected to $p_0$ in the permuted $n$-Dimensional Hypercube as $p_1$, $p_2$, $p_4$, $p_8$, $\ldots$, $p_{2^{n-1}}$ in any arbitrary order. Now, we will find $p_u$ for the remaining vertices in increasing order of $u$. 693 694 In order to find $p_u$, first find a set $S$ of vertices $v$ such that $v \lt u$ and $v$ is connected to $u$ in the simple $n$-Dimensional Hypercube. Then find any vertex $w$ connected to all the vertices $p_v$ such that $v\in S$ in the permuted $n$-Dimensional Hypercube and assign $p_u=w$. I claim that we can never make a wrong choice because we will never have a choice! There will only be one such vertex $w$ for any $u$. Let's prove it. 695 696 **Proof** 697 698 Consider two vertices $v_1$ and $v_2$ in the set $S$. These vertices will differ by exactly $2$ bits in their binary representation. Let the bits in which they differ be $b_x$ and $b_y$. Then, they will have the form $v_1=\ldots b_x\ldots b_y\ldots$ and $v_2=\ldots b^{'}_{x}\ldots b^{'}_{y}\ldots$ where $\ldots$ represent the same bits. Now, only two vertices $u_1=\ldots b_{x}\ldots b^{'}_{y}\ldots$ and $u_2=\ldots b^{'}_{x}\ldots b_{y}\ldots$ can be connected to both $v_1$ and $v_2$. Since a permuted $n$-Dimensional Hypercube is isomorphic to a simple $n$-Dimensional Hypercube, there will only be two vertices connected to both $p_{v_1}$ and $p_{v_2}$ in the permuted $n$-Dimensional Hypercube also. 699 700 If we iterate over $u$ in increasing order, then $b_x\neq b_y$, otherwise one of $v_1$ or $v_2$ will be greater than $u$ which is a contradiction. So, the only vertices connected to both $v_1$ and $v_2$ will have the forms $u_1=\ldots 0\ldots 0\ldots$ and $u_2=\ldots 1\ldots 1\ldots$. Now since $u_1 \lt v_1$ and $u_1 \lt v_2$, $p_{u_1}$ has already been calculated and so, one of the vertex connected to both $p_{v_1}$ and $p_{v_2}$ in the permuted $n$-Dimensional Hypercube has already been used. So, we are left with only one choice for such a vertex $w$. 701 702 **Alternate method of finding the permutation (by mshiladityam)** 703 704 Let's call the vertex connected to a given vertex and which is in the opposite constituent smaller hypercube the ***image*** of the given vertex. 705 706 Lemma — if there is an edge $(a, b)$ in the $n$-Dimensional hypercube where vertices $a$ and $b$ lie in different constituent $(n-1)$-Dimensional Hypercubes (in other words, $a$ and $b$ are images of each other), then for all vertices $q$ adjacent to $a$, the image of $q$ is adjacent to $b$. 707 708 This lemma can be proved by using the fact that two vertex are connected if and only if they differ by exactly $1$ bit. 709 710 Select any two vertices $a$ and $b$. They form a starting point: we treat them as two vertices in opposite constituents (by symmetry, we can prove that any pairs can be treated as such). 711 712 Now let us perform *multisource BFS* with $a$ and $b$ as source nodes. Due to the lemma, the nodes which are discovered from $a$ first lie in the component of $a$, and those which are discovered from $b$ first lie in the component of $b$ (it is easy again to prove it using induction on depth of already discovered vertices). So we have separated these two constituent smaller dimension hypercubes. Lets call a recursive function on any one of them: this recursive function returns a permutation which transforms the permutated hypercube to the simple hypercube. Now, we find for each vertex, in the constituent hypercube whose permutation we just found, its image. Then we can find the permutation for the other constituent by just adding $2^{n-1}$ to the corresponding image. Hence we perform the merging process of recursion. 713 714 The time complexity of this approach is $\mathcal{O}(n\cdot 2^{n})$ 715 716 **Hint 7** 717 718 Instead of colouring the permuted $n$-Dimensional Hypercube, try to colour the simple $n$-Dimensional Hypercube and map these colours to the permuted one in the end using the permutation found in Part 1. 719 720 **Hint 8** 721 722 The number of vertices of each colour will be equal. 723 724 **Hint 9** 725 726 Try to colour a simple $4$-Dimensional Hypercube. This is not a graph problem, rather a constructive problem. 727 728 **Hint 10** 729 730 The way in which vertices are connected in a simple $n$-Dimensional Hypercube suggests something related to Bitwise XOR. 731 732 **Tutorial: Part 2 - Colouring the Hypercube** 733 734 Let's try to colour the simple $n$-Dimensional Hypercube instead of the permuted one. We can map the colours to the permuted one in the end using the permutation found in Part 1. 735 736 I claim that if $n$ is not a power of $2$, then no colouring exists. A simple explanation is that the graph is symmetric and also the colours. So, it is natural that the number of vertices of each colour must be equal meaning $2^n$ must be divisible by $n$ or in other words, $n$ must be a power of $2$ itself. But if symmetry doesn't satisfy you, I have a formal proof too. 737 738 **Proof** 739 740 According to the condition, every vertex must be connected to at least one vertex of every colour or equivalently, *exactly* one vertex of every colour since there are $n$ colours and $n$ neighbours of each vertex. So, if we consider the set of neighbours of any vertex, every colour will appear exactly once in that set. If we consider the multi-set of neighbours of all vertices, every colour will appear $2^n$ times in that set. But every vertex has been counted $n$ times in this multi-set because a particular vertex is the neighbour of $n$ other vertices. So, if we consider the set of all vertices, every colour will appear $\frac{2^n}{n}$ times in that set. Obviously, this number must be a whole number. So, $2^n$ must be divisible by $n$ or in other words, $n$ must itself be a power of $2$ for a colouring to exist. Otherwise, it doesn't exist. To show that a colouring exists if $n$ is a power of $2$, we will construct a colouring. 741 742 **Construction -** This is the most interesting and difficult part of the whole problem. The following construction works — 743 744 Consider a vertex $u$. Let its binary representation be $b_{n-1}b_{n-2}\ldots b_2 b_1 b_0$. Then the colour of this vertex will be $\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$. Let's show why this works. 745 746 * $\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$ will always lie between $0$ and $n-1$ inclusive because $n$ is a power of $2$. 747 * If we are at a vertex $u$ with a colour $c_1$ and we want to reach a vertex of colour $c_2$, we can reach the vertex $v=u\oplus(1\ll (c_1\oplus c_2))$. This is a vertex adjacent to $u$ since it differs from it by exactly $1$ bit and this is the $(c_1\oplus c_2)$-th bit. Notice that the colour of this vertex $v$ will be $c_1\oplus (c_1\oplus c_2) = c_2$. 748 * $(c_1\oplus c_2)$ will always lie between $0$ and $n-1$ because $n$ is a power of $2$. So, $v$ will always be a valid vertex number. 749 750 You can see that many of these facts break when $n$ is not a power of $2$. So, this colouring will not work in such cases. 751 752 Finally, after colouring the simple hypercube, we need to restore the vertex numbers of the permuted hypercube. This can be simply done by replacing all vertices $u$ with $p_u$ using the permutation we found in Part 1. 753 754 **Visualise the Colouring** 755 756 Well, that's enough of theoretical stuff. For those who like visualising things, here is a 4-D Hypercube and its colouring - 757 758  759 760 **Time Complexity** 761 762 Finding the permutation takes $\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$ time if implemented using set or $\mathcal{O}(n^2\cdot 2^n)$ time if implemented using vector. Constructing the colouring for the simple $n$-Dimensional Hypercube takes $\mathcal{O}(n\cdot 2^n)$ time. Restoring colours for the permuted $n$-Dimensional Hypercube takes $\mathcal{O}(2^n)$ time. 763 764 So, the overall time complexity is $\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$ or $\mathcal{O}(n^2\cdot 2^n)$ depending upon implementation. 765 766 **Solution** 767 768 ``` 769 #include <bits/stdc++.h> 770 using namespace std; 771 772 void permuteHypercube(int n,int m,vector<int> adj[],set<int> s[],int p[]) 773 { 774 for(int i=0;i<m;i++) 775 p[i]=-1; 776 bool used[m]; 777 for(int i=0;i<m;i++) 778 used[i]=false; 779 p[0]=0; 780 used[0]=true; 781 for(int u=1;u<m;u++) 782 { 783 vector<int> req; 784 for(int i=0;i<n;i++) 785 { 786 int v=u^(1<<i); 787 if(v<u) 788 req.push_back(v); 789 } 790 if(req.size()==1) 791 { 792 int v=req[0]; 793 for(int i=0;i<adj[p[v]].size();i++) 794 { 795 int w=adj[p[v]][i]; 796 if(used[w]) 797 continue; 798 p[u]=w; 799 used[w]=true; 800 break; 801 } 802 } 803 else 804 { 805 int v=req[0]; 806 for(int i=0;i<adj[p[v]].size();i++) 807 { 808 int w=adj[p[v]][i]; 809 if(used[w]) 810 continue; 811 if(s[w].find(p[req[1]])!=s[w].end()) 812 { 813 p[u]=w; 814 used[w]=true; 815 break; 816 } 817 } 818 } 819 } 820 } 821 822 int main() 823 { 824 ios_base::sync_with_stdio(false); 825 cin.tie(NULL); 826 int t; 827 cin >> t; 828 while(t--) 829 { 830 int n; 831 cin >> n; 832 int m = (1<<n); 833 int p[m]; 834 set<int> s[m]; 835 vector<int> adj[m]; 836 for(int i=0;i<n*m/2;i++) 837 { 838 int u,v; 839 cin >> u >> v; 840 adj[u].push_back(v); 841 adj[v].push_back(u); 842 s[u].insert(v); 843 s[v].insert(u); 844 } 845 permuteHypercube(n,m,adj,s,p); 846 for(int i=0;i<m;i++) 847 cout << p[i] << " "; 848 cout << '\n'; 849 if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16) 850 { 851 cout << -1 << '\n'; 852 continue; 853 } 854 int temp[m]; 855 for(int i=0;i<m;i++) 856 { 857 int clr=0; 858 for(int j=0;j<n;j++) 859 { 860 if(i&(1<<j)) 861 clr=clr^j; 862 } 863 temp[i]=clr; 864 } 865 int c[m]; 866 for(int i=0;i<m;i++) 867 c[p[i]]=temp[i]; 868 for(int i=0;i<m;i++) 869 cout << c[i] << " "; 870 cout << '\n'; 871 } 872 } 873 ``` 874 875 **Alternative Solution (by mshiladityam)** 876 877 ``` 878 #include <iostream> 879 #include <iomanip> 880 #include <vector> 881 #include <cmath> 882 #include <algorithm> 883 #include <set> 884 #include <utility> 885 #include <queue> 886 #include <map> 887 #include <assert.h> 888 #include <stack> 889 #include <string> 890 #include <ctime> 891 #include <chrono> 892 #include <random> 893 using namespace std; 894 895 const int MAX=65536; 896 int power[21]={0}; 897 vector<int> adj[MAX+1]; 898 bool xtra[MAX+1]; 899 bool in[MAX+1]; 900 vector<int> f(vector<int> s) 901 //given a set of vertices [graph], returns the permutation that was applied to the simple hypercube to get this graph 902 { 903 /* 904 cout << "set\n"; 905 for (auto it : s) 906 { 907 cout << it << " "; 908 } 909 cout << '\n'; 910 */ 911 if ((int)s.size()==2) 912 { 913 vector<int> p(2); 914 p[0]=s[0]; 915 p[1]=s[1]; 916 return p; 917 } 918 for (auto i: s) in[i]=true; 919 int v1=s[0]; 920 int v2=-1; 921 922 for (auto i: adj[v1]) 923 { 924 if (in[i]) 925 { 926 v2=i; 927 break; 928 } 929 } 930 assert(v2!=-1); 931 //cout << "v1= " << v1 << " v2 = " << v2 << '\n'; 932 vector<int> component; 933 //multisource BFS from (v1, v2) 934 { 935 queue<int> q; 936 q.push(v1); 937 q.push(v2); 938 map<int, bool> vis; 939 vis[v1]=true; 940 vis[v2]=true; 941 map<int, bool> cmp; 942 cmp[v1]=true; 943 component.push_back(v1); 944 while (!q.empty()) 945 { 946 auto u=q.front(); 947 q.pop(); 948 for (auto i: adj[u]) 949 { 950 if ((!vis[i])&&in[i]) 951 { 952 vis[i]=true; 953 q.push(i); 954 cmp[i]=cmp[u]; 955 if (cmp[i]) component.push_back(i); 956 } 957 } 958 } 959 } 960 for (auto i: s) in[i]=false; 961 for (auto i: component) in[i]=true; 962 vector<int> p1=f(component); 963 for (auto i: s) in[i]=true; 964 for (auto i: component) xtra[i]=true; 965 966 vector<int> p((int)s.size()); 967 968 int z=component.size(); 969 assert(2*z==(int)s.size()); 970 971 for (int i=0; i<z; i++) p[i]=p1[i]; 972 973 for (int i=0; i<z; i++) 974 { 975 //i+z 976 int g=-1; 977 for (auto i: adj[p[i]]) 978 { 979 if (in[i]&&(!xtra[i])) 980 { 981 g=i; 982 break; 983 } 984 } 985 assert(g!=-1); 986 p[z+i]=g; 987 } 988 for (auto i: component) xtra[i]=false; 989 for (auto i: s) in[i]=false; 990 return p; 991 } 992 993 vector<int> colorit(int n) 994 { 995 vector<int> ret(n); 996 for (int i=0; i<n; i++) 997 { 998 int res=0; 999 for (int z=0; z<20; z++) res^=z*((power[z]&i)!=0); 1000 ret[i]=res; 1001 } 1002 return ret; 1003 } 1004 1005 void solve() 1006 { 1007 int n; 1008 cin>>n; 1009 for (int i = 0; i < power[n]; i++) adj[i].clear(); 1010 for (int j = 0; j < n * power[n - 1]; j++) 1011 { 1012 int u, v; 1013 cin >> u >> v; 1014 adj[u].push_back(v); 1015 adj[v].push_back(u); 1016 } 1017 vector<int> p; 1018 1019 { 1020 vector<int> s; 1021 for (int i=0; i<power[n]; i++) s.push_back(i); 1022 p=f(s); 1023 } 1024 1025 for (int i=0; i<power[n]; i++) cout<<p[i]<<' '; 1026 cout<<'\n'; 1027 1028 if (power[n]%n) 1029 { 1030 cout<<-1<<'\n'; 1031 return; 1032 } 1033 vector<int> col=colorit(power[n]); 1034 vector<int> out(power[n]); 1035 for (int i=0; i<power[n]; i++) 1036 { 1037 out[p[i]]=col[i]; 1038 } 1039 for (int i=0; i<power[n]; i++) cout<<out[i]<<' '; 1040 cout<<'\n'; 1041 return; 1042 } 1043 1044 signed main() 1045 { 1046 ios::sync_with_stdio(0); 1047 cin.tie(NULL); cout.tie(NULL); 1048 int t; 1049 cin >> t; 1050 //t=1; 1051 1052 power[0]=1; 1053 for (int j=1; j<=20; j++) power[j]=power[j-1]*2; 1054 1055 while (t--) 1056 { 1057 solve(); 1058 } 1059 return 0; 1060 } 1061 ```