codeforces-scrape

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

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 ![ ](/predownloaded/d2/cd/d2cdf15521755ebca0b18cfec65ad28d4a3e7dce.png)
    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: ![ ](/predownloaded/ed/c4/edc46e26446a28d1890b8bea6a6c56a3b69d346c.png)
    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 ![ ](/predownloaded/13/c3/13c39c4642b8bf7bf6cf7301c8e25444047aff28.png)
    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 ![ ](/predownloaded/dc/8f/dc8fe15aea1a032a34e3638e7c75cab0e5445ab2.png)
    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 ![](/predownloaded/51/f7/51f7bf17945722b40c4c9b267eba9e76fec7eb6a.png)
    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 ![ ](/predownloaded/2e/e6/2ee6c8a6a4b9cbdf3447e8141c7ae773125e009e.png)
    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 ![ ](/predownloaded/87/da/87da136fc2d6816eeb0c1ea547420f50f7a469a2.png)
    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 ![ ](/predownloaded/13/c3/13c39c4642b8bf7bf6cf7301c8e25444047aff28.png)
    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.