2022.md (35234B)
1 Source: https://codeforces.com/blog/entry/135095 2 3 Hola Codeforces community! Sorry for the delay, we were solving some details of our national contest. We hope you enjoyed and learned a lot from this contest, we made it with much love. Our team worked day and night these last days to make sure you had a valuable experience :)). If you have any doubts about the editorial, please let us know in the comments, we are happy to help you. The editorial was prepared by [jampm](/profile/jampm "Expert jampm") and me. Btw, [best meme of the round](https://codeforces.com/blog/entry/134997#comment-1208155). 4 5 ## [2022A - Bus to Pénjamo](/contest/2022/problem/A "Codeforces Round 978 (Div. 2)") 6 7 **Step 1** 8 9 The key to maximizing happiness is to seat family members together as much as possible. If two members of the same family sit in the same row, both will be happy, and we only use two seats. However, if they are seated separately, only one person is happy, but two seats are still used. Therefore, we prioritize seating family pairs together first. 10 11 **Step 2** 12 13 Once all possible pairs are seated, there may still be some family members left to seat. If a family has an odd number of members, one person will be left without a pair. Ideally, we want to seat this person alone in a row to make them happy. However, if there are no remaining rows to seat them alone, we’ll have to seat them with someone from another family. This means the other person might no longer be happy since they are no longer seated alone. 14 15 **Step 3** 16 17 The easiest way to handle part 2 is to check the number of remaining rows and people. If the number of remaining rows is greater than or equal to the number of unpaired people, all unpaired people can sit alone and remain happy. Otherwise, some people will have to share a row, and their happiness will be affected. In that case, the number of happy people will be $2 \times$ *remaining rows* $-$ *remaining people*. 18 19 **Code:** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 25 int main() { 26 int t; 27 cin>>t; 28 while(t--) 29 { 30 int n,r; 31 cin>>n>>r; 32 vector<int>arr(n); 33 int leftalone=0; 34 int happy=0; 35 for(int k=0;k<n;k++) 36 { 37 cin>>arr[k]; 38 happy+=(arr[k]/2)*2; 39 r-=arr[k]/2; 40 leftalone+=arr[k]%2; 41 } 42 if(leftalone>r) 43 happy+=r*2-leftalone; 44 else 45 happy+=leftalone; 46 cout<<happy<<endl; 47 } 48 } 49 ``` 50 51 **Key Takeaway** 52 53 * Write down key observations and mix them to solve the problem 54 55 ## [2022B - Kar Salesman](/contest/2022/problem/B "Codeforces Round 978 (Div. 2)") 56 57 **Step 1** 58 59 Since no customer can buy more than one car from the same model, the minimum number of clients we need is determined by the model with the most cars. Therefore, we need at least: 60 61 $\max\{a_1, a_2, \cdots a_n\}$ 62 63 clients, because even if a customer buys cars from other models, they cannot exceed this limit for any single model. 64 65 **Step 2** 66 67 Each client can buy up to $x$ cars from different models. To distribute all the cars among the clients, we also need to consider the total number of cars. Thus, the minimum number of clients needed is at least: 68 69 $\displaystyle\left\lceil \frac{a_1 + a_2 + \cdots + a_n}{x}\right\rceil$ 70 71 This ensures that all cars can be distributed across the clients, respecting the limit of $x$ cars per customer. 72 73 **Step 3** 74 75 The actual number of clients required is the maximum of the two values: 76 77 $\displaystyle\max\left\{\left\lceil \frac{a_1 + a_2 + \cdots + a_n}{x}\right\rceil, \max\{a_1, a_2, \cdots a_n\}\right\}$ 78 79 This gives us a lower bound for the number of clients required, satisfying both constraints (the maximum cars of a single model and the total number of cars). 80 81 **Alternative Solution** 82 83 Apply binary search on the answer. 84 85 **Proof 1** 86 87 To demonstrate that this is always sufficient, we can reason that the most efficient strategy is to reduce the car count for the models with the largest numbers first. By doing so, we maximize the benefit of allowing each client to buy up to $x$ cars from different models. 88 89 After distributing the cars, two possible outcomes will arise: 90 91 * All models will have the same number of remaining cars, and this situation will be optimal when the total cars are evenly distributed (matching the $\displaystyle\left\lceil \frac{a_1 + a_2 + ... + a_n}{x}\right\rceil$ bound). 92 * There will be still a quantity of models less than or equal to x remaining, which matches the case where the maximum number of cars from a single model $\max(a_1, a_2, ..., a_n)$ determines the bound. 93 94 **Proof 2 (by Errorgorn)** 95 96 Imagine a grid of size $w \times x$, where $w$ represents the minimum number of clients needed: 97 98 $\displaystyle w = \max\left\{\left\lceil \frac{a_1 + a_2 + \cdots + a_n}{x}\right\rceil, \max\{a_1, a_2, \cdots a_n\}\right\}$ 99 100 Now, place the cars in this grid by filling it column by column, from the first model to the $n$-th model. This method ensures that each client will buy cars from different models and no client exceeds the $x$ car limit. Since the total number of cars is less than or equal to the size of the grid, this configuration guarantees that all cars will be sold within $w$ clients. 101 102 **Code:** 103 104 ``` 105 #include <bits/stdc++.h> 106 using namespace std; 107 108 int main() { 109 int t; 110 cin>>t; 111 while(t--) 112 { 113 long long n,x; 114 cin>>n>>x; 115 vector<long long>arr(n); 116 long long sum=0; 117 long long maximo=0; 118 for(int k=0;k<n;k++) 119 { 120 cin>>arr[k]; 121 maximo=max(maximo,arr[k]); 122 sum+=arr[k]; 123 } 124 long long sec=(sum+x-1)/(long long)x; 125 cout<<max(maximo,sec)<<endl; 126 } 127 } 128 ``` 129 130 **Key Takeaway** 131 132 * If you don't know how to solve a problem, try to solve for small cases to find a pattern. 133 134 ## [2022C - Gerrymandering](/contest/2022/problem/C "Codeforces Round 978 (Div. 2)") 135 136 **Step 1** 137 138 We will use dynamic programming to keep track of the maximum number of votes Álvaro can secure as we move from column to column (note that there are many ways to implement the DP, we will use the easiest to understand). 139 140 An important observation is that if you use a horizontal piece in one row, you also have to use it in the other to avoid leaving holes. 141 142 **Step 2:** 143 144 Let $dp[i][j]$ represent the maximum number of votes Álvaro can get considering up to the $i$-th column. The second dimension $j$ represents the current configuration of filled cells: 145 146 * $j = 0$: All cells up to the $i$-th column are completely filled (including $i$-th). 147 * $j = 1$: All cells up to the i-th column are completely filled (including $i$-th), and there’s one extra cell filled in the first row of the next column. $j = 2$: The $i$-th column is filled, and there’s one extra cell filled in the second row of the next column. 148 149 **Step 3:** 150 151 For simplicity, we will call "L", "second L", "third L", and "fourth L" respectively the next pieces: 152 153  154 155 * **From $dp[k][0]$ (Both rows filled at column $k$):** 156 + You can place a horizontal piece in both rows, leading to $dp[k+3][0]$. 157 + You can place a first L piece, leading to $dp[k+1][1]$. 158 + You can place an L piece, leading to $dp[k+1][2]$. 159 * **From $dp[k][1]$ (One extra cell in the first row of the next column):** 160 + You can place a horizontal piece in the first row occupying from $k+2$ to $k+4$ and also a horizontal piece in the second row from $k+1$ to $k+3$, leading to $dp[k+3][1]$. 161 + You can place a fourth L, leading to $dp[k+2][0]$. 162 * **From $dp[k][2]$ (One extra cell in the second row of the next column):** 163 + You can place a horizontal piece in the first row occupying from $k+1$ to $k+3$ and also a horizontal piece in the second row from $k+2$ to $k+4$, leading to $dp[k+3][2]$. 164 + You can place a third L, leading to $dp[k+2][0]$. 165 166 **Step 4:** 167 168 More formally for each DP state, the following transitions are possible: 169 170 From $dp[k][0]$: 171 172 $ dp[k+3][0] = max(dp[k+3][0], dp[k][0] + \text{vot}) $ $ dp[k+1][1] = max(dp[k+1][1], dp[k][0] + \text{vot}) $ $ dp[k+1][2] = max(dp[k+1][2], dp[k][0] + \text{vot}) $ 173 174 From $dp[k][1]$: 175 176 $ dp[k+3][1] = max(dp[k+3][1], dp[k][1] + \text{vot}) $ $ dp[k+2][0] = max(dp[k+2][0], dp[k][1] + \text{vot}) $ 177 178 From $dp[k][2]$: 179 180 $ dp[k+3][2] = max(dp[k+3][2], dp[k][2] + \text{vot}) $ $ dp[k+2][0] = max(dp[k+2][0], dp[k][2] + \text{vot}) $ 181 182 To implement the DP solution, you only need to handle the transitions for states $dp[i][0]$ and $dp[i][1]$. For $dp[i][2]$, the transitions are the same as $dp[i][1]$, with the rows swapped. 183 184 **Code:** 185 186 ``` 187 #include <bits/stdc++.h> 188 using namespace std; 189 void solve() 190 { 191 int n; 192 cin>>n; 193 vector<string>cad(n); 194 vector<vector<int> >vot(2,vector<int>(n+8)); 195 for(int k=0;k<2;k++) 196 { 197 cin>>cad[k]; 198 for(int i=0;i<n;i++) 199 if(cad[k][i]=='A') 200 vot[k][i+1]=1; 201 } 202 vector<vector<int> >dp(n+9,vector<int>(3,-1)); 203 dp[0][0]=0; 204 for(int k=0;k<=n-1;k++) 205 { 206 for(int i=0;i<3;i++) 207 { 208 if(dp[k][i]!=-1) 209 { 210 int vt=0,val=dp[k][i]; 211 if(i==0) 212 { 213 // * 214 // * 215 vt=(vot[0][k+1]+vot[0][k+2]+vot[0][k+3])/2+(vot[1][k+1]+vot[1][k+2]+vot[1][k+3])/2; 216 dp[k+3][0]=max(vt+val,dp[k+3][0]); 217 vt=(vot[1][k+1]+vot[0][k+2]+vot[0][k+1])/2; 218 dp[k+1][1]=max(vt+val,dp[k+1][1]); 219 vt=(vot[1][k+1]+vot[1][k+2]+vot[0][k+1])/2; 220 dp[k+1][2]=max(vt+val,dp[k+1][2]); 221 } 222 if(i==1) 223 { 224 // ** 225 // * 226 vt=(vot[0][k+2]+vot[0][k+3]+vot[0][k+4])/2+(vot[1][k+1]+vot[1][k+2]+vot[1][k+3])/2; 227 dp[k+3][1]=max(vt+val,dp[k+3][1]); 228 vt=(vot[1][k+1]+vot[1][k+2]+vot[0][k+2])/2; 229 dp[k+2][0]=max(vt+val,dp[k+2][0]); 230 } 231 if(i==2) 232 { 233 //* 234 //** 235 vt=(vot[1][k+2]+vot[1][k+3]+vot[1][k+4])/2+(vot[0][k+1]+vot[0][k+2]+vot[0][k+3])/2; 236 dp[k+3][2]=max(vt+val,dp[k+3][2]); 237 vt=(vot[0][k+1]+vot[0][k+2]+vot[1][k+2])/2; 238 dp[k+2][0]=max(vt+val,dp[k+2][0]); 239 } 240 } 241 } 242 } 243 cout<<dp[n][0]<<endl; 244 } 245 int main() { 246 int t; 247 cin>>t; 248 while(t--) 249 solve(); 250 } 251 ``` 252 253 **Key Takeaways** 254 255 * Don't begin to implement until all the details are very clear, this will make your implementation much easier. 256 * Draw images to visualize easier everything. 257 258 ## [2022D1 - Asesino (Easy Version)](/contest/2022/problem/D1 "Codeforces Round 978 (Div. 2)") 259 260 **Hint 1** 261 262 Try to do casework for small $n$. It is also a good idea to simulate it. Think about this problem as a directed graph, where for each query there is a directed edge. 263 264 **Hint 2** 265 266 Observe that if you ask $u \mapsto v$ and $v \mapsto u$, both answers will match if and only if $u$ and $v$ are not the impostor. This can be easily shown by case work. 267 268 **Hint 3** 269 270 We can observe that $n = 3$ and $n = 4$ are solvable with $4$ queries. This strategies are illustrated in the image below:  271 272 **Solution to D1** 273 274 There's many solutions that work. Given that 69 is big enough, we can use the previous observation of asking in pairs and reducing the problem recursively. 275 276 Combining hint 2 with our solutions for $n = 3$ and $n = 4$, we can come up with the following algorithm: 277 278 * While $n \gt 4$, 279 280 + query $n \mapsto n - 1$ and $n - 1 \mapsto n$. 281 - If their answers don't match, one of them is the impostor. Query $n \mapsto n - 2$ and $n - 2 \mapsto n$. 282 * If their answers don't match, $n$ is the impostor. 283 * Otherwise, $n - 1$ is the impostor. 284 - If the answers match, do $n -= 2$. 285 * If $n \gt 4$ doesn't hold and we haven't found the impostor, we either have the $n = 3$ case or the $n = 4$ case, and we can solve either of them in $4$ queries. 286 287 In the worst case, this algorithm uses $n + 1$ queries. I'm also aware of a solution with $n + 4$ queries, $n + 2$ queries, and one with $n + \lceil\log(n)\rceil$ queries. We only present this solution to shorten the length of the blog but feel free to ask about the others in the comments. 288 289 **Code:** 290 291 ``` 292 #include <bits/stdc++.h> 293 using namespace std; 294 295 bool query(int i, int j, int ans = 0) { 296 cout << "? " << i << " " << j << endl; 297 cin >> ans; 298 return ans; 299 } 300 301 int main() { 302 int tt; 303 for (cin >> tt; tt; --tt) { 304 int n, N; cin >> N; n = N; 305 array<int, 2> candidates = {-1, -1}; 306 307 while (n > 4) { 308 if (query(n - 1, n) != query(n, n - 1)) { 309 candidates = {n - 1, n}; break; 310 } else n -= 2; 311 } 312 313 if (candidates[0] != -1) { 314 int not_candidate = (candidates[0] == N - 1) ? N - 2 : N; 315 316 if (query(candidates[0], not_candidate) != query(not_candidate, candidates[0])) { 317 cout << "! " << candidates[0] << endl; 318 } else cout << "! " << candidates[1] << endl; 319 320 } else { 321 322 if (n == 3) { 323 324 if (query(1, 2) == query(2, 1)) cout << "! 3\n"; 325 else { 326 if (query(1, 3) == query(3, 1)) cout << "! 2\n"; 327 else cout << "! 1\n"; 328 } 329 330 } else { 331 332 if (query(1 , 2) != query(2, 1)) { 333 if (query(1, 3) == query(3, 1)) cout << "! 2\n"; 334 else cout << "! 1\n"; 335 } else { 336 if (query(1, 3) != query(3, 1)) cout << "! 3\n"; 337 else cout << "! 4\n"; 338 } 339 340 } 341 } 342 } 343 } 344 ``` 345 346 ## [2022D2 - Asesino (Hard Version)](/contest/2022/problem/D2 "Codeforces Round 978 (Div. 2)") 347 348 **Hint 4** 349 350 What is the minimal value anyway? Our solution to D1 used $n$ queries if $n$ is even and $n + 1$ queries when $n$ is odd. Is this the optimal strategy? Can we find a lower bound? Can we find the optimal strategy for small $n$? 351 352 **Hint 5** 353 354 There's only $9$ possible unlabeled directed graphs with $3$ nodes and at most $3$ edges, you might as well draw them. They are illustrated in the image below for convenience though. Stare at them and convince yourself $4$ queries is the optimal for $n = 3$. 355 356  357 358 **Hint 6** 359 360 We would have to prove that $n - 1 \lt f(n)$ for all $n$ and $n \lt f(n)$ for $n$ odd. How could we structure a proof? 361 362 **Hint 7** 363 364 For $n - 1$ we have some control over the graph. We can show by pigeonhole principle that at least one of them has in-degree $0$, and at least one of them has out-degree $0$. 365 366 * If those two nodes are different, call $A$ the node with in-degree $0$ and $B$ the node with out-degree $0$. Let the grader always reply yes to your queries. 367 368 + $A$ can be the impostor and everyone else Knaves. 369 + $B$ can be the impostor and everyone else Knights. 370 * If those two nodes are the same, then the graph looks like a collection of cycles and one isolated node. The grader will always reply yes except for the last query where it replies no. Let the last query be to player $A$ about player $B$. The two assignments of roles are: 371 372 + $A$ is the impostor and everyone else in the cycle is a Knight. 373 + $B$ is the impostor and everyone else in the cycle is a Knave. 374 375 **Hint 8** 376 377 Note that the structure of our proof is very general and is very easy to simulate for small values of $n$ and small number of queries. Can we extend it to $n$ odd and $n$ queries? Try writing an exhaustive checker and run it for small values. According to our conjecture, $n = 5$ shouldn't solvable with $5$ queries. So we should find a set of answers that for any queries yields two valid assignments with different nodes as the impostor. 378 379 **Hint 9** 380 381 It doesn't exist! Which means $n = 5$ is solvable with $5$ queries. How? Also, observe that if we find a solution to $n = 5$ we can apply the same idea and recursively solve the problem in $n$ queries for all $n \gt 3$. 382 383 **Solution** 384 385 Consider the natural directed graph representation, adding a directed edge with weight $0$ between node $i$ and $j$ if the answer to the query ''? i j'' was yes, and a $1$ otherwise. We will also denote this query by $i \mapsto j$. 386 387 We will use a lemma, that generalizes the idea for D1. 388 389 #### Lemma: 390 391 > The sum of weights of a cycle is odd if and only if the impostor is among us (among the cycle, I mean). 392 393 **Proof** 394 395 * Suppose the impostor is not in the cycle. Then observe that the only time you get an edge with weight $1$ is whenever there are two consecutive nodes with different roles. — Consider consecutive segments of nodes with the same role in this cycle, and compress each of this segments into one node. The image bellow illustrates how, grey edges are queries with answer no. 396 397  398 399 * The new graph is bipartite, and thus has an even number of edges. But all the edges in this new graph, are all the grey edges in the original graph, which implies what we want. 400 * If the impostor is in the cycle, there are three ways of inserting it (assume the cycle has more than $2$ nodes that case is exactly what we proved in hint 2). 401 402 + We can insert the impostor into one of this ``segments'' of consecutive nodes with the same role. This would increase the number of grey edges by $1$, changing the parity, 403 + We can insert it between two segments. 404 + If we have Knight $\mapsto$ Impostor $\mapsto$ Knave, the number of grey edges decreases by $1$. 405 + If thee is Knave $\mapsto$ Impostor $\mapsto$ Knight, the number of grey edges increases by $1$. 406 407 Either way, we changed the parity of the cycle. $\blacksquare$ 408 409 The algorithm that solves the problem is the following: 410 411 If $n = 3$, 412 413 **First case** 414 415  416 417 query $1 \mapsto 2$ and $2 \mapsto 1$, 418 419 * If queries match, $3$ is the impostor. 420 * Else, query $1 \mapsto 3$ and $3 \mapsto 1$. 421 422 + If queries match, $2$ is the impostor. 423 + Else, $1$ is the impostor. 424 425 Else, $n \gt 3$. To solve $n \gt 3$ players with $n$ queries, do: 426 427 * While $n \gt 5$, 428 429 + query $n \mapsto n - 1$ and $n - 1 \mapsto n$. 430 - If their answers don't match, one of them is the impostor. Query $n \mapsto n - 2$ and $n - 2 \mapsto n$. 431 * If their answers don't match, $n$ is the impostor. 432 * Otherwise, $n - 1$ is the impostor. 433 - If the answers match, do $n -= 2$. 434 * If $n \gt 5$ doesn't hold and we haven't found the impostor, we either have the $n = 4$ case or the $n = 5$ case, we solve them optimally in $4$ or $5$ queries each. 435 436 To solve $n = 5$ in $5$ queries, 437 438 **Second case** 439 440 We will form a cycle of size $3$, asking for $1 \mapsto 2$, $2 \mapsto 3$ and $3 \mapsto 2$ (blue edges in the image below). 441 442 * If the cycle has an even number of no's, we know the impostor is among $4$ or $5$. So we ask $3 \mapsto 4$ and $4 \mapsto 3$ (green edges). 443 + If both queries match, $5$ is the impostor. 444 + Else, $4$ is the impostor. 445 * Else, The impostor is among us (among the cycle, I mean). Ask $1 \mapsto 3$ and $2 \mapsto 1$ (purple edges). 446 + If $1 \mapsto 2$ doesn't match with $2 \mapsto 1$ and $1 \mapsto 3$ doesn't match with $3 \mapsto 1$, $1$ is the impostor. 447 + If $1 \mapsto 2$ doesn't match with $2 \mapsto 1$ and $1 \mapsto 3$ matches with $3 \mapsto 1$, $2$ is the impostor. 448 + If $1 \mapsto 2$ matches with $2 \mapsto 1$ and $1 \mapsto 3$ doesn't match with $3 \mapsto 1$, $3$ is the impostor. 449 + It is impossible for $1 \mapsto 2$ to match with $2 \mapsto 1$ and $1 \mapsto 3$ to match with $3 \mapsto 1$, because we know at least one of this cycles will contain the impostor. 450 451  452 453 To solve $n = 4$ in $4$ queries, 454 455 **Third case** 456 457 We will query $1 \mapsto 2$, $2 \mapsto 1$, $1 \mapsto 3$ and $3 \mapsto 1$. 458 459 * If $1 \mapsto 2$ doesn't match with $2 \mapsto 1$ and $1 \mapsto 3$ doesn't match with $3 \mapsto 1$, $1$ is the impostor. 460 + If $1 \mapsto 2$ doesn't match with $2 \mapsto 1$ and $1 \mapsto 3$ matches with $3 \mapsto 1$, $2$ is the impostor. 461 + If $1 \mapsto 2$ matches with $2 \mapsto 1$ and $1 \mapsto 3$ doesn't match with $3 \mapsto 1$, $3$ is the impostor. 462 + If $1 \mapsto 2$ matches with $2 \mapsto 1$ and $1 \mapsto 3$ matches with $3 \mapsto 1$, then $4$ is the impostor. 463 464  465 466 We have proven that that $f(n) \le \max(4, n)$. Now we will prove that $n \le f(n)$. 467 468 **Proof of the lower bound** 469 470 We will show it is impossible to solve the problem for any $n$ with only $n - 1$ queries. We will show that the grader always has a strategy of answering queries, such that there exists at least 2 different assignments of roles that are consistent with the answers given, and have different nodes as the impostor. 471 472 Consider the directed graph generated from the queries. By pigeonhole principle at least one node has in-degree $0$, and at least one node has out-degree $0$. 473 474 * If those two nodes are different, call $A$ the node with in-degree $0$ and $B$ the node with out-degree $0$. Let the grader always reply yes to your queries. 475 476 + $A$ can be the impostor and everyone else Knaves. 477 + $B$ can be the impostor and everyone else Knights. 478 * If those two nodes are the same, then the graph looks like a collection of cycles and one isolated node. The grader will always reply yes except for the last query where it replies no. Let the last query be to player $A$ about player $B$. The two assignments of roles are: 479 480 + $A$ is the impostor and everyone else in the cycle is a Knight. 481 + $B$ is the impostor and everyone else in the cycle is a Knave. 482 483 Thus, we have shown that regardless what the questions asked are, it is impossible to find the impostor among $n$ players, in $n - 1$ queries. $\blacksquare$ 484 485 Now, we prove that $f(3) = 4$: 486 487 **'Proof'** 488 489 Stare at this image: 490 491  492 493 lol, 494 495 Actually, one of the testers coded the exhaustive checker. I will let them post their code if they want to. 496 497 **Code by Marckess:** 498 499 ``` 500 #include <bits/stdc++.h> 501 502 using namespace std; 503 504 int n; 505 506 void answer (int a) { 507 cout << "! " << a << endl; 508 } 509 510 int query (int a, int b) { 511 cout << "? " << a << " " << b << endl; 512 int r; 513 cin >> r; 514 if (r == -1) 515 exit(0); 516 return r; 517 } 518 519 void main_ () { 520 cin >> n; 521 522 if (n == -1) 523 exit(0); 524 525 if (n == 3) { 526 if (query(1, 2) != query(2, 1)) { 527 if (query(1, 3) != query(3, 1)) { 528 answer(1); 529 } else { 530 answer(2); 531 } 532 } else { 533 answer(3); 534 } 535 return; 536 } 537 538 for (int i = 1; i + 1 <= n; i += 2) { 539 if (n % 2 == 1 && i == n - 4) 540 break; 541 542 if ((n % 2 == 0 && i + 1 == n) || query(i, i + 1) != query(i + 1, i)) { 543 int k = 1; 544 while (k == i || k == i + 1) 545 k++; 546 547 if (query(i, k) != query(k, i)) { 548 return answer(i); 549 } else { 550 return answer(i + 1); 551 } 552 } 553 } 554 555 vector<int> v = { 556 query(n - 4, n - 3), 557 query(n - 3, n - 2), 558 query(n - 2, n - 4) 559 }; 560 561 if ((v[0] + v[1] + v[2]) % 2 == 0) { 562 if (query(n - 3, n - 4) != v[0]) { 563 if (query(n - 2, n - 3) != v[1]) { 564 answer(n - 3); 565 } else { 566 answer(n - 4); 567 } 568 } else { 569 answer(n - 2); 570 } 571 } else { 572 if (query(n, 1) != query(1, n)) { 573 answer(n); 574 } else { 575 answer(n - 1); 576 } 577 } 578 } 579 580 int main () { 581 582 int t; 583 cin >> t; 584 585 while (t--) 586 main_(); 587 588 return 0; 589 } 590 ``` 591 592 **Bonus** 593 594 In the Olympiad version, the impostor behaved differently. It could either disguise as a Knight while secretly being a Knave, or disguise as a Knave while secretly being a Knight. Turns out the test cases and the interactor in both versions are practically the same. Why would that be? 595 596 **Main takeaways** 597 598 * Do small cases! Let the pencil (or the computer) do the work and use your brain to look out for patterns. 599 * Try to find the most natural and simple way of modeling the problem. 600 * Learn how to code a decision tree, or other models to exhaustively search for constructions, proof patterns, recursive complete search, etc. and build intuition on that to solve the more general cases of the problem. 601 602 ## [2022E1 - Billetes MX (Easy Version)](/contest/2022/problem/E1 "Codeforces Round 978 (Div. 2)") 603 604 **Hint 1** 605 606 Consider the extremal cases, what is the answer if the grid is empty? What is the answer if the grid is full? What happens if $N = 2$? 607 608 **Hint 2** 609 610 Observe that if $N = 2$, the xor of every column is constant. Can we generalize this idea? 611 612 **Hint 4** 613 614 Imagine you have a valid full grid $a$. For each $i$, change $a[0][i]$ to $a[0][0]\oplus a[0][i]$. Observe that the grid still satisfies the condition! 615 616 **Hint 5** 617 618 Using the previous idea we can show that for any valid grid, there must exist two arrays $X$ and $Y$, such that $a[i][j] = X[i] \oplus Y[j]$. 619 620 **Proof** 621 622 Consider doing the operation described in hint 4 for every row and every column of a full grid that satisfies the condition; 623 624 * That is, for each row, and each column, fix the first element, and change every value in that row or column by their xor with the first element. 625 626 We will be left with a grid whose first row and first column are all zeros. 627 628 But this grid also satisfies the condition! So it must hold that $a[i][j] \oplus a[i][0] \oplus a[0][j] \oplus a[0][0] = 0$, but 3 of this values are zero! 629 630 We can conclude that $a[i][j]$ must also be zero. This shows that there must exist two arrays $X$ and $Y$, such that $a[i][j] = X[i] \oplus Y[j]$, for any valid full grid. 631 632 **Hint 6** 633 634 Think of each tile of the grid that we know of, as imposing a condition between two elements of arrays $X$ and $Y$. For each tile added, we lose one degree of freedom right? We could make a bunch of substitutions to determine new values of the grid. How can we best model the problem now? 635 636 **Hint 7** 637 638 Think about it as a graph where the nodes are rows and columns, and there is an edge between row $i$ and column $j$ with weight $a[i][j]$. Substitutions are now just paths on the graph. If we have a path between the node that represents row $i$ and column $j$, the xor of the weights in this path represents the value of $a[i][j]$. What happens if there's more than one path, and two paths have different values? 639 640 **Hint 8** 641 642 To continue hint 7, we can deduce that if there is a cycle with xor of weights distinct to $0$ in this graph, there would be a contradiction, and arrays $X$ and $Y$ can't exist. How can we check if this is the case? 643 644 **Answer to hint 8** 645 646 Do a dfs on this graph, maintaining an array $p$, such that $p[u]$ is the xor of all edges in the path you took from the root, to node $u$. Whenever you encounter a back edge between nodes $u$ and $v$ with weight $w$, check if $p[u] \oplus p[v] = w$. 647 648 **Hint 9** 649 650 So lets assume there is no contradiction, ie, all cycles have xor 0. What would be the answer to the problem? We know that if the graph is connected, there exists a path between any two tiles and all the values of the tiles would be determined. So, in how many ways can we make a graph connected? 651 652 **Answer to hint 9** 653 654 Say there are $K$ connected components. We can connect them all using $K - 1$ edges. For each edge, there are $2^{30}$ possible values they can have. Thus, the number of ways of making the graph connected is $\left(2^{30} \right)^{K - 1}$. 655 656 **Check your understanding** 657 658 Why is this the answer to the problem? 659 660 **Solution** 661 662 This is just the solution. Please read the hints in order to understand why it works and how to derive it. 663 664 Precompute an array $c$, with $c[i] = 2^{30\cdot i} \pmod{10^9 + 7}$. 665 666 Let $a$ be the 2d array with known values of the grid. Consider the graph formed by adding an edge between node $i$ and node $j + n$ and weight $a[i][j]$ for every known tile $(i, j)$ in the grid. Iterate from $1$ to $n + m$ maintaining an array $p$ initialized in $-1$s. If the current proceed node hasn't been visited, we run a dfs through it. We will use array $p$ to maintain the running xor for each node during the dfs. If we ever encounter a back edge between nodes $u, v$ and weight $w$, we check if $p[u] \oplus p[v] = w$. If not, we the answer is zero. If this condition always holds, let $K$ be the number of times you had to run the dfs. $K$ is also the number of connected components in the graph. The answer is $c[K - 1]$. 667 668 Complexity: $\mathcal{O}(n + m + k)$. 669 670 **Code:** 671 672 ``` 673 #include <bits/stdc++.h> 674 using namespace std; 675 676 int const Mxn = 2e5 + 2; 677 long long int const MOD = 1e9 + 7; 678 long long int precalc[Mxn]; 679 680 vector<vector<array<int, 2>>> adj; 681 682 bool valid = 1; 683 int pref[Mxn]; 684 685 void dfs(int node) { 686 for (auto [child, w] : adj[node]) { 687 if (pref[child] == -1) { 688 pref[child] = pref[node]^w; 689 dfs(child); 690 } else { 691 if ((pref[child]^pref[node]) != w) valid = 0; 692 } 693 } 694 } 695 696 int main() { 697 698 precalc[0] = 1; 699 for (int i = 1; i < Mxn; i++) { 700 precalc[i] = (precalc[i - 1]<<30)%MOD; 701 } 702 703 int tt; 704 for (cin >> tt; tt; --tt) { 705 int N, M, K, Q; 706 cin >> N >> M >> K >> Q; 707 708 adj.clear(); 709 adj.assign(N + M, vector<array<int, 2>>{}); 710 711 int x, y, z; 712 for (int i = 0; i < K; i++) { 713 cin >> x >> y >> z; 714 x--, y--; 715 adj[x].push_back({y + N, z}); 716 adj[y + N].push_back({x, z}); 717 } 718 719 for (int i = 0; i < N + M; i++) pref[i] = -1; 720 valid = 1; 721 int cnt = 0; 722 723 for (int i = 0; i < N + M; i++) { 724 if (pref[i] != -1) continue; 725 cnt++; pref[i] = 0; dfs(i); 726 } 727 728 if (valid) cout << precalc[cnt - 1] << '\n'; 729 else cout << 0 << '\n'; 730 } 731 } 732 ``` 733 734 ## [2022E2 - Billetes MX (Hard Version)](/contest/2022/problem/E2 "Codeforces Round 978 (Div. 2)") 735 736 Please read the solution to E1 beforehand, as well as all the hints. 737 738 **Solution 1** 739 740 Through the observations in E1, we can reduce the problem to the following: We have a graph, we add edges, and we want to determine after each addition if all its cycles have xor 0, and the number of connected components in the graph. 741 742 The edges are never removed, so whenever an edge is added that creates a cycle with xor distinct to zero, this cycle will stay in the graph for all following updates. So we can binary search the first addition that creates a cycle with xor distinct to zero, using the same dfs we used in E1. After the first such edge, the answer will always be zero. 743 744 Now, for all the additions before that, we must determine how many connected components the graph has at each step. But this is easily solvable with Disjoint Set Union. 745 746 Complexity: $\mathcal{O}(\log(q)(n + m + k + q) + \alpha(n + m)(q + k))$. 747 748 **Solution 2** 749 750 We will answer the queries online. Remember that if the graph only contains cycles with xor $0$, the xor of a path between a pair of nodes is unique. We'll use this in our advantage. Let $W(u, v)$ be the unique value of the xor of a path between nodes $u$ and $v$. 751 752 Lets modify a dsu, drop the path compression, and define array $p$, that maintains the following invariant: 753 754 For every node $u$ in a component with root $r$, $W(u, r)$ equals the xor of $p[x]$ for all ancestors $x$ of $u$ in our dsu (we also consider $u$ an ancestor of itself). 755 756 Whenever we add an edge between two nodes $u$ and $v$ in two different components with weight $w$, we consider consider the roots $U$ and $V$ of their respective components. Without loss of generality, assume $U$'s component has more elements than $V$'s. We will add an edge with weight $W(u, U) \oplus W(v, V) \oplus w$ between $V$ and $U$, and make $U$ the root of our new component. 757 758 This last step is the small to large optimization, to ensure the height of our trees is logarithmic. 759 760 With this data structure, we can maintain the number of connected components like in a usual dsu, and whenever an edge $(u, v)$ with weight $w$ is added, and $u$ and $v$ belong to the same component, we can obtain the value of $W(u, v)$ in $\mathcal{O(\log(n))}$, and check if it is equal to $w$. 761 762 This idea is similar to the data structure [described here](https://cp-algorithms.com/data_structures/disjoint_set_union.html#support-the-parity-of-the-path-length-checking-bipartiteness-online), and is useful in other contexts. 763 764 Complexity: $\mathcal{O}(\log(q + k)(n + m + k + q))$. 765 766 **Code by Marckess:** 767 768 ``` 769 #include <bits/stdc++.h> 770 using namespace std; 771 772 int const Mxn = 2e5 + 2; 773 long long int const MOD = 1e9 + 7; 774 775 vector<vector<array<int, 2>>> adj; 776 vector<array<int, 3>> Edges; 777 long long int precalc[Mxn]; 778 779 780 struct DSU { 781 vector<int> leader; 782 vector<int> sz; 783 int components; 784 785 DSU(int N) { 786 leader.resize(N); iota(leader.begin(), leader.end(), 0); 787 sz.assign(N, 1); 788 components = N; 789 } 790 791 int find(int x) { 792 return (leader[x] == x) ? x : (leader[x] = find(leader[x])); 793 } 794 795 void unite(int x, int y) { 796 x = find(x), y = find(y); 797 if (x == y) return; 798 if (sz[x] < sz[y]) swap(x, y); 799 leader[y] = leader[x]; sz[x] += sz[y]; 800 components--; 801 } 802 }; 803 804 bool valid = 1; 805 int pref[Mxn]; 806 807 void dfs(int node = 0) { 808 for (auto [child, w] : adj[node]) { 809 if (pref[child] == -1) { 810 pref[child] = pref[node]^w; 811 dfs(child); 812 } else { 813 if ((pref[child]^pref[node]) != w) valid = 0; 814 } 815 } 816 } 817 818 int main() { 819 precalc[0] = 1; 820 for (int i = 1; i < Mxn; i++) { 821 precalc[i] = (precalc[i - 1]<<30)%MOD; 822 } 823 824 int tt; 825 for (cin >> tt; tt; --tt) { 826 827 int N, M, K, Q; 828 cin >> N >> M >> K >> Q; 829 830 Edges.clear(); 831 adj.clear(); 832 adj.assign(N + M, vector<array<int, 2>>{}); 833 834 DSU dsu(N + M); 835 dsu.components = N + M; 836 837 int x, y, z; 838 for (int i = 0; i < K; i++) { 839 cin >> x >> y >> z; 840 x--, y--; 841 adj[x].push_back({y + N, z}); 842 adj[y + N].push_back({x, z}); 843 dsu.unite(x, y + N); 844 } 845 846 for (int i = 0; i < Q; i++) { 847 cin >> x >> y >> z; 848 x--, y--; 849 Edges.push_back({x, y + N, z}); 850 } 851 852 int firstzero = 0; 853 854 for (int k = 20; k >= 0; k--) { 855 if (firstzero + (1<<k) > Q) continue; 856 857 for (int i = firstzero; i < firstzero + (1<<k); i++) { 858 x = Edges[i][0], y = Edges[i][1], z = Edges[i][2]; 859 adj[x].push_back({y, z}); 860 adj[y].push_back({x, z}); 861 } 862 863 valid = 1; 864 for (int i = 0; i < N + M; i++) pref[i] = -1; 865 for (int i = 0; i < N + M; i++) { 866 if (pref[i] == -1) pref[i] = 0, dfs(i); 867 } 868 869 if (!valid) { 870 for (int i = firstzero + (1<<k) - 1; i >= firstzero; --i) { 871 x = Edges[i][0], y = Edges[i][1]; 872 adj[x].pop_back(); 873 adj[y].pop_back(); 874 } 875 } else { 876 firstzero += (1<<k); 877 } 878 } 879 880 if (firstzero == 0) { 881 valid = 1; 882 for (int i = 0; i < N + M; i++) pref[i] = -1; 883 for (int i = 0; i < N + M; i++) { 884 if (pref[i] == -1) pref[i] = 0, dfs(i); 885 } 886 887 if (!valid) firstzero--; 888 } 889 890 for (int i = 0; i <= Q; i++) { 891 if (i <= firstzero) cout << precalc[dsu.components - 1] << '\n'; 892 else cout << 0 << '\n'; 893 if (i == Q) break; 894 x = Edges[i][0], y = Edges[i][1]; 895 dsu.unite(x, y); 896 } 897 898 } 899 } 900 ``` 901 902 **Bonus** 903 904 In our Olympiad, we had $v_i \le 1$ instead of $v_i \le 2^{30}$, and we also had a final subtask were tiles could change values. How would you solve this? 905 906 We have three different solutions for this problem, one of them found during the Olympiad! I'll let the contestant who found it post it if he wants to. 907 908 **Main takeaways** 909 910 * You can model a grid as a bipartite graph between rows and columns. 911 * Whenever coding or designing a data structure, keep in mind all the invariants you are maintaining. I like to think of data structures as graphs with invariants or monovariants in each node. I have a blog draft on how to use this to design data structures, inspired by [this](https://www.youtube.com/watch?v=oaYsWnohXpA). Maybe I will publish it.