codeforces-scrape

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

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: