1673.md (22195B)
1 Source: https://codeforces.com/blog/entry/102389 2 3 I am sorry for the weak tests in B, for C being a little standardish and for misjudging the relative difficulties of E and F. Nevertheless, I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that I can improve upon them the next time. 4 5 #### [A. Subtle Substring Subtraction](https://codeforces.com/contest/1673/problem/A) 6 7 **Hint 1** 8 9 Greedy 10 11 **Hint 2** 12 13 The answer depends on whether the length of $s$ is even or odd and on the first and last characters of $s$ if the length is odd. 14 15 **Tutorial** 16 17 The problem can be solved greedily. Let $n$ be the length of the given string. 18 19 * If the $n$ is even, it is always optimal for Alice to remove the whole string. 20 * If the $n$ is odd, it is always optimal for Alice to remove either $s_1s_2\ldots s_{n-1}$ or $s_2s_3\ldots s_n$ based on which gives the higher score and then Bob can remove the remaining character ($s_n$ or $s_1$ respectively). This is optimal because if Alice chooses to remove a substring of even length $2k$ such that $2k \lt n-1$ then Bob can remove the remaining $n-2k\geq 3$ characters, one of which will always be either $s_1$ or $s_n$, thus increasing Bob's score and decreasing Alice's score. 21 22 **Bonus tasks** 23 24 Prove that - 25 26 1. Bob can win if and only if the length of the string is $1$. 27 2. A draw is impossible. 28 29 **Solution** 30 31 ``` 32 #include <bits/stdc++.h> 33 using namespace std; 34 35 int main() 36 { 37 int tc; 38 cin >> tc; 39 while(tc--) 40 { 41 string s; 42 cin >> s; 43 int n=s.length(),alice=0; 44 for(int i=0;i<n;i++) 45 alice += s[i]-'a'+1; 46 if(n%2==0) 47 cout << "Alice " << alice << '\n'; 48 else 49 { 50 int bob; 51 if(s[0]<=s[n-1]) 52 bob = s[0]-'a'+1; 53 else 54 bob = s[n-1]-'a'+1; 55 alice -= bob; 56 if(alice > bob) 57 cout << "Alice " << alice-bob << '\n'; 58 else if(alice < bob) 59 cout << "Bob " << bob-alice << '\n'; 60 else 61 cout << "Draw " << 0 << '\n'; 62 } 63 } 64 } 65 ``` 66 67 **Feedback** 68 69 * Good problem: 70 * Ok problem: 71 * Bad problem: 72 * Did not attempt: 73 74 #### [B. A Perfectly Balanced String?](https://codeforces.com/contest/1673/problem/B) 75 76 **Hint 1** 77 78 The string is perfectly balanced if it is periodic and the repeating pattern contains all distinct alphabets. 79 80 **Tutorial** 81 82 Let the number of distinct characters in $s$ be $k$ and length of $s$ be $n$. Then, $s$ will be perfectly balanced if and only if $s_{i}, s_{i+1}, \ldots, s_{i+k-1}$ are all pairwise distinct for every $i$ in the range $1\leq i\leq n-k+1$. 83 84 **Proof why this condition is necessary** 85 86 If there exists some $i$ in the range $1\leq i\leq n-k+1$ for which the characters $s_{i}, s_{i+1}, \ldots, s_{i+k-1}$ are not pairwise distinct, there will be atleast one character $u$ in the substring $t=s_{i} s_{i+1}\ldots s_{i+k-1}$ such that $f_t(u)\geq 2$ and by pigeonhole principle, there will be atleast one character $v$ present in $s$ such that $f_t(v)=0$. So, for the triple $(t,u,v)$, $f_t(u)-f_t(v)\geq 2$, violating the criteria for the $s$ to be perfectly balanced. 87 88 **Proof why this condition is sufficient** 89 90 Suppose the following condition is met. Let's pick up any substring $t=s_is_{i+1}\ldots s_j$. Let's divide $t$ into $\Big\lceil \frac{j-i+1}{k}\Big\rceil$ blocks each of length $k$ except probably the last block. For each of these blocks, the frequency of all characters is equal to $1$ (because there are $k$ distinct characters in a block as well as in $s$) and for the last block, the frequency of some characters is equal to $1$ wheras the frequency of rest of the characters is equal to $0$. So, the frequency of some characters in $t$ will be equal to $\Big\lceil \frac{j-i+1}{k}\Big\rceil$ while that for the other characters will be equal to $\Big\lceil \frac{j-i+1}{k}\Big\rceil-1$. If we pick any two characters $u$ and $v$, $\lvert f_t(u)-f_t(v)\rvert\leq 1$ meaning that $s$ is perfectly balanced. 91 92 **Bonus task** 93 94 Prove that the condition is equivalent to the following two conditions - 95 96 1. The first $k$ characters of $s$ are pairwise distinct. 97 2. For each $i$ in the range $1\leq i\leq n-k$, $s_i=s_{i+k}$. 98 99 **Solution** 100 101 ``` 102 #include <bits/stdc++.h> 103 using namespace std; 104 105 int main() 106 { 107 int tc; 108 cin >> tc; 109 while(tc--) 110 { 111 string s; 112 cin >> s; 113 int n = s.length(); 114 set<char> c; 115 bool ok = true; 116 int k; 117 for(k=0;k<n;k++) 118 { 119 if(c.find(s[k])==c.end()) 120 c.insert(s[k]); 121 else 122 break; 123 } 124 for(int i=k;i<n;i++) 125 { 126 if(s[i]!=s[i-k]) 127 ok = false; 128 } 129 if(ok) 130 cout << "YES\n"; 131 else 132 cout << "NO\n"; 133 } 134 } 135 ``` 136 137 **Feedback** 138 139 * Good problem: 140 * Ok problem: 141 * Bad problem: 142 * Did not attempt: 143 144 #### [C. Palindrome Basis](https://codeforces.com/contest/1673/problem/C) 145 146 **Hint 1** 147 148 The number of palindromes less than $4\cdot 10^4$ is relatively small. 149 150 **Hint 2** 151 152 The rest of the problem is quite similar to the classical partitions problem. 153 154 **Tutorial** 155 156 First, we need to observe that the number of palindromes less than $4\cdot 10^4$ is relatively very small. The number of $5$-digit palindromes are $300$ (enumerate all $3$-digit numbers less than $400$ and append the first two digits in the reverse order). Similarly, the number of $4$-digit, $3$-digit, $2$-digit and $1$-digit palindromes are $90$, $90$, $9$ and $9$ respectively, giving a total of $M=498$ palindromes. 157 158 Now, the problem can be solved just like the classical partitions problem which can be solved using Dynamic Programming. 159 160 Let $dp_{k,m} =$ Number of ways to partition the number $k$ using only the first $m$ palindromes. It is not hard to see that $dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m}$ where $p_m$ denotes the $m^{th}$ palindrome. The first term corresponds to the partitions of $k$ using only the first $m-1$ palindromes and the second term corresponds to those partitions of $k$ in which the $m^{th}$ palindrome has been used atleast once. As base cases, $dp_{k,1}=1$ and $dp_{1,m}=1$. The final answer for any $n$ will be $dp_{n,M}$. 161 162 The time and space complexity is $\mathcal{O}(n\cdot M)$. 163 164 **Bonus Task** 165 166 Try to optimize the space complexity to $\mathcal{O}(n)$. 167 168 **Solution** 169 170 ``` 171 #include <bits/stdc++.h> 172 using namespace std; 173 174 const int N = 40004, M = 502; 175 const long long MOD = 1000000007; 176 long long dp[N][M]; 177 178 int reverse(int n) 179 { 180 int r=0; 181 while(n>0) 182 { 183 r=r*10+n%10; 184 n/=10; 185 } 186 return r; 187 } 188 189 bool palindrome(int n) 190 { 191 return (reverse(n)==n); 192 } 193 194 int main() 195 { 196 vector<int> palin; 197 palin.push_back(0); 198 for(int i=1;i<2*N;i++) 199 { 200 if(palindrome(i)) 201 palin.push_back(i); 202 } 203 for(int j=1;j<M;j++) 204 dp[0][j]=1; 205 for(int i=1;i<N;i++) 206 { 207 dp[i][0]=0; 208 for(int j=1;j<M;j++) 209 { 210 if(palin[j]<=i) 211 dp[i][j]=(dp[i][j-1]+dp[i-palin[j]][j])%MOD; 212 else 213 dp[i][j]=dp[i][j-1]; 214 } 215 } 216 ios_base::sync_with_stdio(false); 217 cin.tie(NULL); 218 int tc; 219 cin >> tc; 220 while(tc--) 221 { 222 int n; 223 cin >> n; 224 cout << dp[n][M-1] << '\n'; 225 } 226 } 227 ``` 228 229 **Feedback** 230 231 * Good problem: 232 * Ok problem: 233 * Bad problem: 234 * Standardish problem and boring to solve: 235 * Standardish problem but learned something new today 236 * Did not attempt: 237 238 #### [D. Lost Arithmetic Progression](https://codeforces.com/contest/1673/problem/D) 239 240 **Hint 1** 241 242 First check if all elements of $C$ are present in $B$ or not. If not, the answer is $0$. 243 244 **Hint 2** 245 246 Then check if the answer is infinite or not. It depends on only the first and last elements of $B$ and $C$. 247 248 **Hint 3** 249 250 If $p$ is the common difference of $A$ then $lcm(p,q)=r$. $p$ must necessarily be a factor of $r$ and $\mathcal{O}(\sqrt n)$ works here. 251 252 **Tutorial** 253 254 If all elements of $C$ are not present in $B$, then the answer is $0$. It is sufficient to check the following $4$ conditions to check if all elements of $C$ are present in $B$ or not - 255 256 * The first term of $B\leq$ The first term of $C$, i.e., $b\leq c$. 257 * The last term of $B\geq$ The last term of $C$, i.e., $b+(y-1)q\geq c+(z-1)r$. 258 * The common difference of $C$ must be divisible by the common difference of $B$, i.e., $r\bmod q=0$. 259 * The first term of $C$ must lie in $B$, i.e., $(c-b)\bmod q=0$. 260 261 Now suppose the following conditions are satisfied. Let's denote an Arithmetic Progression (AP) with first term $a$, common difference $d$ and $n$ number of terms by $[a,d,n]$. 262 263 If $b \gt c-r$ then there are infinite number of progressions which can be $A$ like $[c,r,z]$, $[c-r,r,z+1]$, $[c-2r,r,z+2]$ and so on. Similarly, if $b+(y-1)q \lt c+zr$, there are infinite number of progressions which can be $A$ like $[c,r,z]$, $[c,r,z+1]$, $[c,r,z+2]$ and so on. 264 265 Otherwise, there are a finite number of progressions which can be $A$. Let's count them. Let $A$ be the AP $[a,p,x]$ and $l=a+(x-1)p$. It can be seen that $lcm(p,q)=r$, $(c-a)\bmod p=0$, $a \gt c-r$ and $l \lt c+rz$ for any valid $A$. The first two conditions are trivial. The third condition is necessary because if $a\leq c-r$ then $c-r$ will always be present in both $A$ and $B$ contradicting the fact that $C$ contains all the terms common to $A$ and $B$. Similarly, the fourth condition is also necessary. 266 267 The only possible values $p$ can take according to the first condition are factors of $r$ which can be enumerated in $\mathcal{O}(\sqrt{r})$. The $lcm$ condition can be checked in $\mathcal{O}(\log r)$. For a particular value of $p$, there are $\frac{r}{p}$ possible values of $a$ satisfying conditions 2 and 3 and $\frac{r}{p}$ possible values of $l$ satisfying conditions 2 and 4. Thus, the answer is $\displaystyle\sum_{lcm(p,q)=r}\Big(\frac{r}{p}\Big)^2$. 268 269 Time complexity: $\mathcal{O}(t\,\sqrt{r}\,\log r)$ 270 271 **Solution** 272 273 ``` 274 #include <bits/stdc++.h> 275 using namespace std; 276 277 const long long MOD = 1000000007; 278 279 long long gcd(long long a,long long b) 280 { 281 if(b==0) 282 return a; 283 else 284 return gcd(b,a%b); 285 } 286 287 long long lcm(long long a,long long b) 288 { 289 long long g = gcd(a,b); 290 return (a*b)/g; 291 } 292 293 int main() 294 { 295 int tc; 296 cin >> tc; 297 while(tc--) 298 { 299 long long b,c,q,r,y,z; 300 cin >> b >> q >> y; 301 cin >> c >> r >> z; 302 long long e = b+q*(y-1); 303 long long f = c+r*(z-1); 304 if(c<b || c>e || f<b || f>e || r%q!=0 || (c-b)%q!=0) 305 cout << 0 << '\n'; 306 else if(c-r<b || f+r>e) 307 cout << -1 << '\n'; 308 else 309 { 310 long long ans = 0; 311 for(long long p=1;p*p<=r;p++) 312 { 313 if(r%p==0) 314 { 315 if(lcm(p,q)==r) 316 { 317 long long a = ((r/p)*(r/p))%MOD; 318 ans = (ans+a)%MOD; 319 } 320 if(p*p!=r && lcm(r/p,q)==r) 321 { 322 long long a = (p*p)%MOD; 323 ans = (ans+a)%MOD; 324 } 325 } 326 } 327 cout << ans << '\n'; 328 } 329 } 330 } 331 ``` 332 333 **Feedback** 334 335 * Good problem: 336 * Ok problem: 337 * Bad problem: 338 * Did not attempt: 339 340 #### [E. Power or XOR?](https://codeforces.com/contest/1673/problem/E) 341 342 **Hint 1** 343 344 All numbers in $A$ are powers of $2$ and the modulo is also a power of $2$ and $B_i\geq 1$. 345 346 **Hint 2** 347 348 Fix all operators in a particular subsegment as $\texttt{Power}$ and fix the operators around the segment as $\texttt{XOR}$. Find the contribution of this segment independent of other segments. 349 350 **Hint 3** 351 352 Maximum possible length for such a subsegment which can contribute to the answer is $20$. 353 354 **Hint 4** 355 356 Use Lucas' Theorem or Submasks DP or precomputation in order to count the parity of the number of valid unambiguous expressions in which the subsegment appears as in Hint 2. 357 358 **Tutorial** 359 360 Let's consider a subsegment $[A_{l}\wedge A_{l+1}\wedge A_{l+2}\wedge\ldots\wedge A_r]$. Let all the $\wedge$ symbols in this segment be replaced by $\texttt{Power}$ and the $\wedge$ symbols before $A_l$ and after $A_r$ be replaced by $\texttt{XOR}$. Then the value of this segment will not be affected by the rest of the expression. Moreover, out of all the expressions in which this segment appears as above, it will contribute the same value to the final answer. Since the final answer is also a $\texttt{XOR}$, if the segment $[l\ldots r]$ appears in the above mentioned form in odd number of valid unambiguous expressions, it will contribute $(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$ to the final answer else it will contribute nothing. We can find the contribution of each segment $[l\ldots r]$ independently for all values of $1\leq l \lt r \leq n$. 361 362 Now, there are two things we need to find out: 363 364 1. How much $(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$ will contribute to the final answer, modulo $MOD = 2^{1048576}$. 365 2. What is the parity of the count of valid unambiguous expressions, in which the segment $[l...r]$ appears as $... \oplus (\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r} \oplus \ldots$. 366 367 **Part 1:** Notice that since all the elements of $A$ are powers of $2$, $S(l,r)=(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$ will also be a power of $2$. It means that $\texttt{XOR}$-ing it with answer will flip not more than $1$ bit in the answer. The rest of the calculations is pretty straightforward. $S(l,r) = 2^{B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}}$ by properties of exponents. So, if it contributes to the answer, it will flip the $B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}-$th bit of the answer. Now, note that if $S\geq 2^{1048576}$, it will have no effect on the answer because $S(l,r) \bmod 2^{1048576}$ will then be $0$. So, we care only for those $(l,r)$ for which $S(l,r) \lt 2^{1048576}$. Since $B_i\geq 1$, $A_i\geq 2$ and so, $r-l \leq 20$ because $2^{20} = 1048576$. Thus, it is sufficient to calculate $S(l,r)$ for only $20$ values of $r$ per value of $l$. 368 369 **Part 2:** We have used $r-l$ $\wedge$ operators as $\texttt{Power}$ and $0$, $1$ or $2$ $\wedge$ operators as $\texttt{XOR}$. Let's say that out of the $m$ unused operators, we need to use at least $q$ of them as $\texttt{XOR}$. Then the number of ways to do this is $\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}$. Infact, instead of finding this value, we are only interested in finding whether it is even or odd. So, we need the value of $\big[\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}\big]\bmod 2=$ $\big[\binom{m-1}{q}+\binom{m-1}{q-1} + \binom{m-1}{q+1}+\binom{m-1}{q} + \binom{m-1}{q+2}+\binom{m-1}{q+1} + \ldots + \binom{m-1}{m-1}+\binom{m-1}{m-2} + \binom{m}{m}\big] \bmod 2=$ $\big[\binom{m-1}{q-1} + \binom{m-1}{m-1} + \binom{m}{m}]\bmod 2 =$ $\binom{m-1}{q-1} \bmod 2$ as $(a + a) \bmod 2 = 0$ and $\binom{x}{x} = 1$ by definition. $\binom{m-1}{q-1} \bmod 2$ can be found using [Lucas' Theorem](https://brilliant.org/wiki/lucas-theorem/). It turns out that $\binom{n}{r}$ is odd if and only if $r$ is a submask of $n$, i.e., $n | r = n$. Note that there are also many other ways to find this value (like Submasks DP or using the fact that $r-l\leq 20$ for precomputation) but this is the easiest one. 370 371 Some final notes - 372 373 1. We can maintain the final answer as a binary string of length $1048576$. Find the value $X = B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$ and if the required parity is odd and $X \lt 1048576$, flip the $X-$th bit of the string. 374 2. We need to be careful while calculating $B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$ since $A_i$ can be as large as $2^{1048575}$. But since we are interested in values that evaluate to something smaller than $1048576$, we will never try to multiply $A_i$ for anything with $B_i \gt 20$. 375 3. Calculating the parity of $\binom{n}{r}$ in $\mathcal{O}(\log n)$ may time out. The constraints are strict enough. 376 377 Total time Complexity — $\mathcal{O}(n \log \log MOD)$ 378 379 **Bonus Task** 380 381 Try to solve the problem if $B_i\geq 0$ and if powers are calculated from right to left. 382 383 **Solution** 384 385 ``` 386 #include <bits/stdc++.h> 387 using namespace std; 388 389 const int N = 1048576; 390 long long b[N]; 391 char ans[N]; 392 393 int main() 394 { 395 ios_base::sync_with_stdio(false); 396 cin.tie(NULL); 397 int n,k; 398 cin >> n >> k; 399 for(int i=0;i<n;i++) 400 { 401 cin >> b[i]; 402 } 403 for(int i=0;i<1048576;i++) 404 ans[i]='0'; 405 for(int l=0;l<n;l++) 406 { 407 long long p=1; 408 for(int r=l;r<n;r++) 409 { 410 if(r==l) 411 p*=b[r]; 412 else 413 { 414 if(b[r]>=20) 415 break; 416 else 417 p*=(1ll<<b[r]); 418 } 419 if(p>=1048576) 420 break; 421 int m = n-r+l-3; 422 int q = k-2; 423 if(l==0) 424 { 425 m++; 426 q++; 427 } 428 if(r==n-1) 429 { 430 m++; 431 q++; 432 } 433 if(m>=q && (m==0 || (q>0 && ((m-1)|(q-1))==(m-1)))) 434 ans[p]='1'+'0'-ans[p]; 435 } 436 } 437 bool start=false; 438 for(int i=1048575;i>=0;i--) 439 { 440 if(ans[i]=='0' && start) 441 cout << 0; 442 else if(ans[i]=='1') 443 { 444 cout << 1; 445 start=true; 446 } 447 } 448 if(!start) 449 cout << 0; 450 cout << '\n'; 451 } 452 ``` 453 454 **Feedback** 455 456 * Good problem: 457 * Ok problem: 458 * Bad problem: 459 * Did not attempt: 460 461 #### [F. Anti-Theft Road Planning](https://codeforces.com/contest/1673/problem/F) 462 463 **Hint 1** 464 465 The main goal is to assign numbers $A_{i,j}$ from $0$ to $1023$ to all buildings such that all buildings get distinct numbers and assign the road lengths between buildings $B_{x_1,y_1}$ and $B_{x_2,y_2}$ as $A_{x_1,y_1}\oplus A_{x_2,y_2}$. Among all such assignments, try to find the one which has the least sum of road lengths. 466 467 **Hint 2** 468 469 $2$-Dimensional Gray Code works 470 471 **Tutorial** 472 473 For now, lets ignore $n \lt =32$ and assume $n=32$. 474 475 Let's try to build the roads in such a way that no matter what path the thief takes to reach building $B_{i,j}$, the tracker will always return a fixed value $A_{i,j}$ such that all $A_{i,j}$ are distinct. Then by knowing the values returned by the tracker, one can easily find which building the theft occurred in. The main problem here is not to choose the lengths of the roads, since by choosing the length of road between buildings $B_{x_1,y_1}$ and $B_{x_2,y_2}$ as $A_{x_1,y_1}\oplus A_{x_2,y_2}$, one can always achieve this property. But there is a constraint which needs to be satisfied: The total length of all roads must not exceed $48000$. This is, in fact, a tight constraint (model solution uses $47616$) due to which one needs to choose the values of $A_{i,j}$ very efficiently. 476 477 Consider this problem — Find a permutation of numbers from $0$ to $2^m-1$ such that the sum of XOR of consecutive integers is minimized. The answer to this is [Gray Code or Reflected Binary Code](https://en.wikipedia.org/wiki/Gray_code). In the standard Gray Code, bit $0$ is flipped $2^{m-1}$ times, bit $1$ is flipped $2^{m-2}$ times, bit $2$ is flipped $2^{m-3}$ times, $\ldots$, bit $m-1$ is flipped $1$ time. The idea is to use small bits more number of times compared to the larger ones. 478 479 Our task is to implement this idea in $2$-dimensions. Let's look at the algorithm used to build Gray Code. If we have the Gray Code for $k$ bits, it can be extended to $k+1$ bits by taking a copy of it, reflecting it and appending $1$ to the beginning of the reflected code and $0$ to the beginning of the original one. Here, if we have the Gray Code for $2^k \times 2^k$ matrix, it can be first extended to a Gray Code for $2^k \times 2^{k+1}$ matrix and this can further be extended to a Gray Code for $2^{k+1} \times 2^{k+1}$ matrix. If we build a $2^m \times 2^m$ matrix using this algorithm, the total length of roads used will be $\frac{3}{2}\cdot(4^m)\cdot(2^m-1)$. In this problem, $m = 5$. So, total length of roads used = $\frac{3}{2} \cdot 1024 \cdot 31 = 47616$. 480 481 Once this construction is complete, finding the buildings where thefts occurred is elementary since there can now be only one building corresponding to each value returned by the tracker. 482 483 Now, coming back to the original problem, we can simply take the first $n$ rows and the first $n$ columns from the constructed matrix. The cost won't increase and the properties still hold. 484 485 **Solution** 486 487 ``` 488 #include <bits/stdc++.h> 489 using namespace std; 490 491 const int N = 32; 492 493 int maxpower2(int n) 494 { 495 int p=1; 496 while(n%2==0) 497 { 498 p*=2; 499 n/=2; 500 } 501 return p; 502 } 503 504 int main() 505 { 506 int n,k; 507 cin >> n >> k; 508 int h[N][N-1]; 509 for(int i=0;i<N;i++) 510 { 511 for(int j=1;j<=N-1;j++) 512 { 513 h[i][j-1]=maxpower2(j)*maxpower2(j); 514 } 515 } 516 for(int i=0;i<n;i++) 517 { 518 for(int j=0;j<n-1;j++) 519 { 520 cout << h[i][j] << " "; 521 } 522 cout << endl; 523 } 524 int v[N-1][N]; 525 for(int i=1;i<=N-1;i++) 526 { 527 for(int j=0;j<N;j++) 528 { 529 v[i-1][j]=2*maxpower2(i)*maxpower2(i); 530 } 531 } 532 for(int i=0;i<n-1;i++) 533 { 534 for(int j=0;j<n;j++) 535 { 536 cout << v[i][j] << " "; 537 } 538 cout << endl; 539 } 540 int b[n][n]; 541 b[0][0]=0; 542 for(int j=1;j<n;j++) 543 { 544 b[0][j]=b[0][j-1]^h[0][j-1]; 545 } 546 for(int i=1;i<n;i++) 547 { 548 for(int j=0;j<n;j++) 549 { 550 b[i][j]=b[i-1][j]^v[i-1][j]; 551 } 552 } 553 map<int,pair<int,int> > m; 554 for(int i=0;i<n;i++) 555 { 556 for(int j=0;j<n;j++) 557 { 558 m[b[i][j]]={i,j}; 559 } 560 } 561 int y=0; 562 while(k--) 563 { 564 int x; 565 cin >> x; 566 pair<int,int> ans = m[x^y]; 567 cout << ans.first+1 << " " << ans.second+1 << endl; 568 y^=x; 569 } 570 } 571 ``` 572 573 **Feedback** 574 575 * Good problem: 576 * Ok problem: 577 * Bad problem: 578 * Did not attempt: