1934.md (18990B)
1 Source: https://codeforces.com/blog/entry/126423 2 3 [1934A — Too Min Too Max](https://codeforces.com/contest/1934/problem/A) 4 5 **Solution** 6 7 **Hint 1** 8 9 What will be answer if there were only $4$ elements in the array? 10 11 **Solution** 12 13 Suppose if there were only $4$ elements in the array. Let them be $a \leq b \leq c \leq d$. Then the answer will be maximum of the three cases which are listed as follows:- 14 15 $|a-b|+|b-c|+|c-d|+|d-a| = 2*d - 2*a$ $|a-b|+|b-d|+|d-c|+|c-a| = 2*d-2*a$ $|a-c|+|c-b|+|b-d|+|d-a| = 2*(d+c)-2*(a+b)$ 16 17 so clearly $2*(d+c)-2*(a+b)$ is the maximum. 18 19 So, to maximize this we can set $d$, $c$ as large as possible and $a$, $b$ as small as possible i.e. $d=a_n$, $c=a_{n-1}$, $b=a_{2}$ and $a=a_{1}$ where $a_i$ means $i^{th}$ element in sorted order of given array. 20 21 **Code (C++)** 22 23 ``` 24 #include <bits/stdc++.h> 25 26 using namespace std; 27 28 int main() 29 { 30 ios::sync_with_stdio(false); 31 cin.tie(nullptr); 32 int testcases; 33 cin >> testcases; 34 for (int t = 1; t <= testcases; t++) 35 { 36 int n; 37 cin >> n; 38 vector<int> v(n); 39 for (int j = 0; j < n; j++) 40 { 41 cin >> v[j]; 42 } 43 sort(v.begin(), v.end()); 44 cout << 2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]) << endl; 45 } 46 } 47 ``` 48 49 **Code (Python)** 50 51 ``` 52 t = int(input()) 53 for i in range(t): 54 n = int(input()) 55 a = list(map(int, input().split())) 56 a = sorted(a) 57 ans = 2 * (a[n - 1] - a[0] + a[n - 2] - a[1]) 58 print(ans) 59 ``` 60 61 [1934B — Yet Another Coin Problem](https://codeforces.com/contest/1934/problem/B) 62 63 **Solution 1** 64 65 **Hint** 66 67 At max how many $1$, $3$, $6$, $10$ are required? 68 69 **Solution** 70 71 **Fact**: You will never need more than $2$ ones, $1$ threes, $4$ sixes and $2$ tens. 72 73 **Reason**: 74 75 For $1$: Suppose if you used $k$ > $2$ ones, then you could have used one $3$ and $k$ — $3$ ones. 76 77 For $3$: Suppose if you used $k$ > $1$ threes, then you could have used one $6$ and $k$ — $2$ threes. 78 79 For $6$: Suppose if you used $k$ > $4$ sixes, then you could have used two $15$'s and $k$ — $5$ sixes. 80 81 For $10$: Suppose if you used $k$ > $2$ tens, then you could have used two $15$'s and $k$ — $3$ tens. 82 83 now since bound on their count is less, we can bruteforce on these count. 84 85 **Code (C++)** 86 87 ``` 88 #include <bits/stdc++.h> 89 90 using namespace std; 91 92 int main() 93 { 94 ios::sync_with_stdio(false); 95 cin.tie(nullptr); 96 int testcases; 97 cin >> testcases; 98 for (int t = 1; t <= testcases; t++) 99 { 100 int n; 101 cin >> n; 102 int ans = 1e9; 103 for(int ones = 0; ones <= 2; ones++){ 104 for(int threes = 0; threes <= 1; threes++){ 105 for(int sixes = 0; sixes <= 4; sixes++){ 106 for(int tens = 0; tens <= 2; tens++){ 107 int brute_sum = 1*ones + 3*threes + 6*sixes + 10*tens; 108 if(brute_sum <= n && (n-brute_sum)%15 == 0){ 109 ans = min(ans, ones + threes + sixes + tens + (n-brute_sum)/15); 110 } 111 } 112 } 113 } 114 } 115 cout << ans << endl; 116 } 117 } 118 ``` 119 120 **Solution 2** 121 122 **Hint** 123 124 When will the greedy logic of choosing the higher-valued coin first work? 125 126 **Solution** 127 128 **Fact $1$**: If coins of value $1$, $3$, $6$ and $15$ were only present the greedy logic of selecting the higher valued first would work. 129 130 **Reason**: We use coins of value one at most $2$ times, coins of value three at most $1$ time, coins of value six at most $2$ times (if it was used $3$ times, it would be better to use two coins $15 + 3$) But we can't use the coin of value $3$ and both coins of value $6$ simultaneously, because we would prefer just using $15$. 131 It means that these coins may sum up to $1 + 1 + 3 + 6 = 11$ or $1 + 1 + 6 + 6 = 14$ at max. So, we may use the value $15$ greedily, because the remaining part is less than $15$. When we are left with only the values $1$, $3$, and $6$, greedily solving is obviously correct, because each coin is a divisor of the next coin. 132 133 **Fact $2$**: We don't need more than $2$ ten coins. 134 135 **Reason**: Better to use $2$ fifteen coins instead of $3$ ten coins. 136 137 Using the above two facts it can be shown that the answer will have $k \lt 3$ ten coin, therefore, answer = $\min$($\text{answer}(n-10*k)+k$ assuming $1$, $3$, $6$ and $15$ coins are only present). 138 139 **Code (C++)** 140 141 ``` 142 #include<bits/stdc++.h> 143 144 using namespace std; 145 146 int getAns(int n){ 147 int ans=0; 148 ans+=n/15; 149 n%=15; 150 ans+=n/6; 151 n%=6; 152 ans+=n/3; 153 n%=3; 154 ans+=n; 155 return ans; 156 } 157 158 int main(){ 159 ios::sync_with_stdio(false), cin.tie(nullptr); 160 161 int testcases; 162 cin>>testcases; 163 for(int i=1;i<=testcases;i++){ 164 int n;cin>>n; 165 if(n<10){ 166 cout<<getAns(n)<<endl; 167 }else if(n<20){ 168 cout<<min(getAns(n),getAns(n-10)+1)<<endl; 169 }else{ 170 cout<<min({getAns(n),getAns(n-10)+1,getAns(n-20)+2})<<endl; 171 } 172 } 173 } 174 ``` 175 176 [1934C — Find a Mine](https://codeforces.com/contest/1934/problem/C) 177 178 **Hint 1** 179 180 After querying "$?$ $1$ $1$" What do we know about the location of mines? 181 182 **Answer** 183 184 If the answer is $a_1$ the location of one of the mines is $(x, y)$ such that $x+y = a_1+2$. 185 186 **Solution 1** 187 188 **Solution** 189 190 First, we query "$?$ $1$ $1$" then you get a value $a_1$ and you know that at least one of the mine is on the line $x+y=a_1+2$. 191 192 Now we make two more queries on both ends of this line where it touches the grid. After these two queries, we get two possible locations of the mine. We query one of these positions if we receive $0$ as the answer then this location otherwise the other location is the answer. 193 194 **Reason**: One of that two locations contains a mine. The other mine could spoil the result of the query only from one end. If it was closer from the other mine to both of the ends, it would mean that going from one end to the other is shorter through that mine, than through the diagonal. That's impossible. 195 196 **Code (C++)** 197 198 ``` 199 #include <bits/stdc++.h> 200 using namespace std; 201 202 int main(){ 203 ios_base::sync_with_stdio(0); 204 cin.tie(0); 205 int T; 206 cin >> T; 207 while (T--){ 208 int n, m; 209 cin >> n >> m; 210 auto query = [&](int x, int y){ 211 if (x < 1 || x > n || y < 1 || y > m) 212 return -1; 213 cout << "? " << x << ' ' << y << endl; 214 int z; 215 cin >> z; 216 return z; 217 }; 218 int d = query(1, 1); 219 int lx = max(1, 2 + d - m); 220 int p = query(lx, 2 + d - lx); 221 int rx = max(1, 2 + d - n); 222 int q = query(2 + d - rx, rx); 223 if (query(lx + p / 2, 2 + d - lx - p / 2) == 0){ 224 cout << "! " << lx + p / 2 << " " << 2 + d - lx - p / 2<<endl; 225 }else{ 226 cout << "! " << 2 + d - rx - q / 2 << " " << rx + q / 2 << endl; 227 } 228 } 229 } 230 ``` 231 232 **Solution 2** 233 234 **Hint 2** 235 236 What if we made the second query as "$?$ $n$ $m$"? 237 238 **Answer** 239 240 If the answer is $a_2$ the location of one of the mines is $(x, y)$ such that $x+y = n+m-a_2$. 241 242 **Solution** 243 244 Using Hint $1$ and Hint $2$ if we get the same line equation i.e. $n+m-a_2=a_1-2$ we can just query one of the endpoints of this line and get the answer. 245 246 Otherwise, we can query "$?$ $1$ $m$" and we will get one more line perpendicular to the earlier two. One of the mines has to be on this line therefore there will be a mine either on the intersection of line we got from query $1$ and query $3$ or on the intersection of line we got from query $2$ and query $3$. 247 248 We can make our next query on any of these intersections if we get the answer as $0$, then this point is the answer otherwise the other point is the answer. 249 250 **Code (C++)** 251 252 ``` 253 #include <bits/stdc++.h> 254 255 using namespace std; 256 257 using ll = long long; 258 259 ll query(ll x, ll y) { 260 cout << "? " << x << ' ' << y << endl; 261 ll d; 262 cin >> d; 263 return d; 264 } 265 266 int main() { 267 ios::sync_with_stdio(false), cin.tie(nullptr); 268 269 ll t; 270 cin >> t; 271 272 while (t--) { 273 ll n, m; 274 cin >> n >> m; 275 276 ll sum1 = query(1, 1) + 2; 277 ll sum2 = n + m - query(n, m); 278 ll dif1 = query(1, m) + 1 - m; 279 280 auto simplify = [&](ll num, ll lim)->ll{ 281 return max(min(num, lim), 1LL); 282 }; 283 ll x1 = simplify((sum1+dif1)/2, n), y1 = simplify((sum1-dif1)/2, m); 284 ll x2 = simplify((sum2+dif1)/2, n), y2 = simplify((sum2-dif1)/2, m); 285 286 if (query(x1, y1)) cout << "! " << x2 << ' ' << y2 << endl; 287 else cout << "! " << x1 << ' ' << y1 << endl; 288 } 289 return 0; 290 } 291 ``` 292 293 [1934D1 — XOR Break — Solo Version](https://codeforces.com/contest/1934/problem/D1) 294 295 **Hint** 296 297 To generate any possible $m$, it takes at most two operations. 298 299 **Solution** 300 301 Let's determine the achievable values of $m$ for a given $n$. 302 303 If $n$ is a perfect power of $2$, then it cannot be broken down further, and no $m \lt n$ is achievable. Otherwise, if $n$ has at least two set bits, let's denote the most significant bit as $a$ and the second most significant bit as $b$. 304 305 **Fact 1**: All $m$ values less than $n$ are achievable if their most significant bit does not lie between $b+1$ and $a-1$. 306 307 **Reason**: For instance, $1001????$ can be decomposed into $1000????$ and $0001????$, or $1001????$ and $0000????$. In either case, we can never flip the $6^{th}$ or $7^{th}$ bit. 308 309 Using the above fact, we can break the problem into two cases: 310 311 **Case 1**: If the most significant bit of $m$ is at position $\leq b$. 312 313 Perform the first operation as $2^{b+1} - 1$ and $n \oplus (2^{b+1} - 1)$ ($10001????$ -> $10000????$ and $000011111$ in binary form). Then, any submask of $2^{b+1} - 1$ can be created in the next operation. 314 315 **Case 2**: If the most significant bit of $m$ is at position $a$. 316 317 If the most significant bit of $m$ is at position $a$, then $m$ can be obtained in one operation as $m$ and $m \oplus n$, since $m \lt n$ as given in the question, and $n \oplus m$ has its most significant bit $ \lt a$. 318 319 **Code** 320 321 ``` 322 #include<bits/stdc++.h> 323 324 using namespace std; 325 326 using ll = long long; 327 328 int main() { 329 ios::sync_with_stdio(false), cin.tie(nullptr); 330 331 ll t; 332 cin >> t; 333 334 while (t--) { 335 ll n, m; 336 cin >> n >> m; 337 338 ll hi = 0, sec_hi = 0; 339 for (ll p = (1LL<<62); p > 0; p >>= 1) { 340 if (p & n) { 341 if (!hi) hi = p; 342 else if (!sec_hi) sec_hi = p; 343 } 344 } 345 bool flag = (sec_hi && ((m & hi) || (m < sec_hi*2))); 346 if (!flag) { 347 cout << -1 << '\n'; 348 continue; 349 } 350 vector<ll> ans = {n, m}; 351 if (!(m & hi) && !(m & sec_hi)) ans = {n, m^sec_hi, m}; 352 353 cout << (ll)ans.size()-1 << '\n'; 354 for (auto &x: ans) cout << x << ' '; 355 cout << '\n'; 356 } 357 return 0; 358 } 359 ``` 360 361 [1934D2 — XOR Break — Game Version](https://codeforces.com/contest/1934/problem/D2) 362 363 **Hint 1** 364 365 If both $p_1$ and $p_2$ are perfect powers of $2$, it is a losing state since you cannot perform a break operation on either of those. 366 367 **Hint 2** 368 369 If either $p_1$ or $p_2$ has a bit count of $2$, then this is a winning state. 370 371 **Reason** 372 373 You can force your opponent into the state described in Hint $1$ using the number which has $2$ bitcount. 374 375 **Solution** 376 377 **Fact 1**: If $p_1$ has an odd bit count, then it can only be broken into two numbers such that one has an odd bit count and the other has an even bit count. 378 379 **Fact 2**: If either $p_1$ or $p_2$ has an even bit count, then this is a winning state. 380 381 **Reason** : If either $p_1$ or $p_2$ has an even bit count, without loss of generality, assume it's $p_1$. Then break it into $2^{msb \text{ of } p_1}$ and $p_1 \oplus 2^{msb \text{ of } p_1}$, where $msb$ is the most significant bit. 382 383 If the opponent chooses $2^{msb \text{ of } p_1}$, they instantly lose (using Hint $1$), so they are forced to choose the other number with an odd bit count. From Fact $1$, we can conclude that in the next turn, the state will remain conserved for the current player. 384 385 Because we eliminate the most significant bit in every query, this game will go on for at most $60$ turns for the player who reached this position first. At one point, the player who is at this state will have a number with two set bits. 386 387 Hence, from Hint $2$, we can say this player will win. So, as Alice, you will start first if $n$ has an even number of bits and start second if it has an odd number of bits. Proceed using the strategy discussed above. So as Alice you have will start first if $n$ has even number of bits and start second if it has odd number of bits. Any proceed using the strategy discussed above. 388 389 **Code** 390 391 ``` 392 #include<bits/stdc++.h> 393 394 using namespace std; 395 396 int main(){ 397 ios::sync_with_stdio(false); 398 cin.tie(nullptr); 399 400 int testcases;cin>>testcases; 401 402 for(int testcase=1;testcase<=testcases;testcase++){ 403 long long n;cin>>n; 404 long long curr=n; 405 int parity=0; 406 if(__builtin_popcountll(n)%2){ 407 cout<<"secoNd"<<endl; 408 }else{ 409 cout<<"firSt"<<endl; 410 parity=1; 411 } 412 int turn=0; 413 while(1){ 414 if(turn%2==parity){ 415 long long p1,p2;cin>>p1>>p2; 416 if (p1 == 0 && p2 == 0) 417 break; 418 if(__builtin_popcountll(p1)%2==0){ 419 curr=p1; 420 }else{ 421 curr=p2; 422 } 423 }else{ 424 int pos=0; 425 for(int i=0;(1ll<<i)<curr;i++){ 426 if(curr&(1ll<<i)){ 427 pos=i; 428 } 429 } 430 long long p1=(1ll<<pos); 431 long long p2=curr^p1; 432 cout<<p1<<" "<<p2<<endl; 433 curr = p1; 434 } 435 turn++; 436 } 437 } 438 } 439 ``` 440 441 [1934E — Weird LCM Operations](https://codeforces.com/contest/1934/problem/E) 442 443 **Solution** 444 445 **Fact 1**: If for $(x, y, z)$ their pairwise GCDs are equal to their common GCD (this means that $(x, y, z)$ = $(g * X, g * Y, g * Z)$ where $(X, Y, Z)$ are pairwise coprime), then making an operation on them (gives $(g * X * Y, g * X * Z,g * Y * Z)$) and looking at the subsequences of size EXACTLY 2, we find all three GCD: $x$, $y$, $z$. Let's call such tuple NICE. 446 447 **Result**: If we can split all values in the array into independent NICE tuples, then we can just perform an operation on each of them and the problem is solved. 448 449 **Fact 2**: We don't touch any value $\leq$ $\frac{n}{2}$. If there is $x$ $\leq$ $\frac{n}{2}$, then $2 * x \leq n$. If we don't touch $x$, then we will always have another value that is divisible by $x$ (it's easy to see that performing an operation on a multiple of $x$ leaves us with another multiple of $x$), so we will always have GCD equal to $x$ taking a subsequence $(x, x * A)$. 450 451 **Fact 3**: A sequence of consecutive integers $(x, x+1, x+2, ..., x+11)$ can be partitioned into $4$ disjoint sets of size $3$, each forming a NICE tuple, if $(x+11) \% 4$ equals $2$ or $1$. 452 453 **For $(x+11) \% 4 = 2$**: The sets $(x, x+1, x+2)$, $(x+4, x+5, x+6)$ and $(x+8, x+9, x+10)$ are NICE because, the first and third terms are always odd, and the second term is always even. The set $(x+3, x+7, x+11)$ is NICE because it has the form of $2*(2*n-1)$, $2*(2*n)$, $2*(2*n+1)$, ensuring that the pairwise GCDs are equal to the common GCD. 454 455 **For $(x+11) \% 4 = 1$**: The sets $(x, x+4, x+8)$, $(x+1, x+2, x+3)$, $(x+5, x+6, x+7)$ and $(x+9, x+10, x+11)$ are NICE, the same logic like $(x+11) \% 4 = 2$ follows, 456 457 If $n \% 4 = 3$ we can do one operation as $(1, 2, n)$, and if $n \% 4 = 0$ we can do one operation as $(1, n-1, n)$. Let's group the remaining elements into the groups of size $12$, starting from the end, and continuing until we reach the number $\frac{n}{2}$. 458 459 Eventually, we can count that we used no more than $\lfloor \frac{n}{6} \rfloor + 5$ operations. 460 461 Solutions for $n \leq 13$ should be found manually. 462 463 **Code** 464 465 ``` 466 #include<bits/stdc++.h> 467 468 using namespace std; 469 vector<vector<vector<int>>> pans(14); 470 int main(){ 471 472 ios::sync_with_stdio(false), cin.tie(nullptr); 473 474 int t;cin>>t; 475 476 pans[3]={{1,2,3}}; 477 pans[4]={{1,3,4}}; 478 pans[5]={{3,4,5}}; 479 pans[6]={{1,3,5},{2,4,6}}; 480 pans[7]={{2,4,6},{3,5,7}}; 481 pans[8]={{2,6,8},{3,5,7}}; 482 pans[9]={{1,3,5},{2,4,6},{7,8,9}}; 483 pans[10]={{3,4,5},{2,6,8},{7,9,10}}; 484 pans[11]={{2,6,8},{3,5,7},{9,10,11}}; 485 pans[12]={{1,11,12},{6,8,10},{5,7,9}}; 486 pans[13]={{1,12,13},{7,9,11},{6,8,10}}; 487 for(int tt=0;tt<t;tt++){ 488 int n;cin>>n; 489 if(n<=2){ 490 cout<<-1<<endl; 491 }else if(n<14){ 492 cout<<pans[n].size()<<endl; 493 for(auto w: pans[n]){ 494 cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl; 495 } 496 }else{ 497 vector<int> v(n); 498 for(int i=0;i<n;i++){ 499 v[i]=i+1; 500 } 501 vector<vector<int>> ans; 502 while (2*v.size()>n){ 503 if(v.size()%4==2){ 504 vector<int> buf; 505 for(int i=0;i<12;i++){ 506 buf.push_back(v.back()); 507 v.pop_back(); 508 } 509 reverse(buf.begin(),buf.end()); 510 ans.push_back({buf[0],buf[1],buf[2]}); 511 ans.push_back({buf[4],buf[5],buf[6]}); 512 ans.push_back({buf[8],buf[9],buf[10]}); 513 ans.push_back({buf[3],buf[7],buf[11]}); 514 }else if(v.size()%4==1){ 515 vector<int> buf; 516 for(int i=0;i<12;i++){ 517 buf.push_back(v.back()); 518 v.pop_back(); 519 } 520 reverse(buf.begin(),buf.end()); 521 ans.push_back({buf[1],buf[2],buf[3]}); 522 ans.push_back({buf[5],buf[6],buf[7]}); 523 ans.push_back({buf[9],buf[10],buf[11]}); 524 ans.push_back({buf[0],buf[4],buf[8]}); 525 }else if(v.size()%4==3){ 526 vector<int> buf; 527 buf.push_back(v.back()); 528 v.pop_back(); 529 buf.push_back(2); 530 buf.push_back(1); 531 reverse(buf.begin(),buf.end()); 532 ans.push_back({buf[0],buf[1],buf[2]}); 533 }else{ 534 vector<int> buf; 535 buf.push_back(v.back()); 536 v.pop_back(); 537 buf.push_back(v.back()); 538 v.pop_back(); 539 buf.push_back(1); 540 reverse(buf.begin(),buf.end()); 541 ans.push_back({buf[0],buf[1],buf[2]}); 542 } 543 } 544 cout<<ans.size()<<endl; 545 for(auto w: ans){ 546 cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl; 547 } 548 } 549 } 550 } 551 ```