codeforces-scrape

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

2163.md (20815B)


      1 Source: https://codeforces.com/blog/entry/148239
      2 
      3 **Comment**
      4 
      5 B turned out to be harder than expected. I apologize for this, but I hope there are still problems that are fun and educational for you to solve in this round.
      6 
      7 Regardless, I hope this round encourages authors to include communication problems in their future rounds, and in earlier positions as well.
      8 
      9 [Problem A — Souvlaki VS. Kalamaki](https://codeforces.com/contest/2163/problem/A)
     10 
     11 **Solution**
     12 
     13 Suppose it Kalamaki's turn on some even round $2k$. Kalamaki can swap element $a_{2k}$ with $a_{2k+1}$. If $a_{2k} \gt a_{2k+1}$, he will not swap the elements, but if $a_{2k} \lt a_{2k+1}$, he will swap them. In both cases he wins the game, because the array will never be sorted. Therefore, if $a_{2k} \neq a_{2k+1}$, Kalamaki will win no matter what.
     14 
     15 Now assume every time Kalamaki plays, the two elements he can swap have the same value, because otherwise we have shown that he wins. Suppose that it is Souvlaki's turn on round $2k+1$. We know that $a_{2k} = a_{2k+1}$ from the previous assumption. If $a_{2k+1} \gt a_{2k+2}$, we know that $a_{2k+1} = a_{2k} \gt a_{2k+2}$, but he is unable to swap $a_{2k}$ and $a_{2k+2}$, therefore he loses. Otherwise, if $a_{2k+1} \le a_{2k+2}$ he will not do anything, and he proceeds to the next round.
     16 
     17 From these observations, we see that $a$ is winnable by Souvlaki if and only if: $a_1 \le a_2 = a_3 \le a_4 = a_5 \le \ldots$, or $a_2 \le a_1 = a_3 \le a_4 = a_5 \le \ldots$. It is obvious now that Souvlaki, before the start of the game, will sort $a$ in non-decreasing order. To determine if Souvlaki wins or not it is enough to check the above condition is satisfied after sorting.
     18 
     19 **Implementation**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 using namespace std;
     24  
     25 void solve() {
     26     int n; cin >> n;
     27     int a[n+1];
     28     for (int i = 1; i <= n; i++) cin >> a[i];
     29     sort(a+1, a+n+1);
     30     for (int i = 2; i <= n - 1; i+=2) {
     31         if (a[i] != a[i+1]) {
     32             cout << "NO\n";
     33             return;
     34         }
     35     }
     36     cout << "YES\n";
     37 }
     38  
     39 int main() {
     40     int t; cin >> t;
     41     while (t--) solve();
     42     return 0;
     43 }
     44 ```
     45 
     46 **Rate the Problem**
     47 
     48 * Amazing
     49 * Good
     50 * Average
     51 * Bad
     52 
     53 **Rate the Difficulty**
     54 
     55 * Very Hard
     56 * Hard
     57 * Average
     58 * Easy
     59 * Very Easy
     60 
     61 [Problem B — Siga ta Kymata](https://codeforces.com/contest/2163/problem/B)
     62 
     63 **Solution**
     64 
     65 Let the position of integer $x$ in the permutation $p$ be denoted by $pos_x$.
     66 
     67 Let's see for which indices $i$ we can never set $s_i$ to $1$, even with an infinite number of operations. First of all, in an operation $(l, r)$, we only consider indices $i$ such that $l \lt i \lt r$. This means that we can never set $s_1$ or $s_n$ to $1$. In addition, we only consider indices $i$ such that $p_i$ is between $p_l$ and $p_r$, but not equal to those. This means that we can never set $s_{pos_1}$ or $s_{pos_n}$ to $1$. In general, if $x_1 = 1$, $x_n = 1$, $x_{pos_1} = 1$, or $x_{pos_n} = 1$, it is impossible to solve the problem.
     68 
     69 Now I will show that the problem is always solvable for any binary string $x$ such that $x_1 = x_n = x_{pos_1} = x_{pos_n} = 0$, within $5$ operations.
     70 
     71 WLOG, assume $pos_1 \lt pos_n$. It is natural to think about using $pos_1$ and $pos_n$ as endpoints for our operations. For example, by using the operations $(1, pos_1)$ and $(1, pos_n)$, we will have set $s_i = 1$ for every $1 \lt i \lt pos_1$. Likewise, with the operations $(pos_1, n)$ and $(pos_n, n)$, we will have set $s_i = 1$ for every $pos_n \lt i \lt n$. By using the operation $(pos_1, pos_n)$, we have set $s_i = 1$ for every $pos_1 \lt i \lt pos_n$.
     72 
     73 With these $5$ operations, we have finally set $s_i = 1$ for every $i$ in $(1, pos_1) \cup (pos_1, pos_n) \cup (pos_n, n)$, which guarantees we have solved the problem.
     74 
     75 **Implementation**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 using namespace std;
     80  
     81 void solve() {
     82     int n; cin >> n;
     83     vector<int> a(n+1);
     84     int mn = 1, mx = 1;
     85     for (int i = 1; i <= n; i++) {
     86         cin >> a[i];
     87         if (a[i] < a[mn]) mn = i;
     88         if (a[i] > a[mx]) mx = i;
     89     }
     90     string t; cin >> t;
     91     t = " " + t;
     92     if (t[1] == '1' || t[n] == '1') {
     93         cout << -1 << "\n";
     94         return;
     95     }
     96     if (t[mn] == '1' || t[mx] == '1') {
     97         cout << -1 << "\n";
     98         return;
     99     }
    100     cout << 5 << "\n";
    101     cout << 1 << " " << mn << "\n";
    102     cout << 1 << " " << mx << "\n";
    103     cout << mn << " " << n << "\n";
    104     cout << mx << " " << n << "\n";
    105     cout << min(mn, mx) << " " << max(mn, mx) << "\n";
    106 }
    107  
    108 int main() {
    109     int t; cin >> t;
    110     while (t--) solve();
    111     return 0;
    112 }
    113 ```
    114 
    115 **Rate the Problem**
    116 
    117 * Amazing
    118 * Good
    119 * Average
    120 * Bad
    121 
    122 **Rate the Difficulty**
    123 
    124 * Very Hard
    125 * Hard
    126 * Average
    127 * Easy
    128 * Very Easy
    129 
    130 [Problem C — Monopati](https://codeforces.com/contest/2163/problem/C)
    131 
    132 **Solution**
    133 
    134 We call a pair of integers $(l, r)$ good if and only if $1 \le l \le r \le 2n$ and in $f(l, r)$ there is a down-right path from $(1, 1)$ to $(2, n)$ of cells with value of $1$. For some fixed left endpoint $l$ from $1$ to $2n$, let $r_l$ denote the minimum integer such that the pair $(l, r_l)$ is good. If there does not exist such an integer, for convenience we say $r_l = n+1$.
    135 
    136 The first observation is that if $(l, r)$ is good, and $r \lt 2n$, then $(l, r+1)$ is also good. The reason is obvious: every cell that has value of $1$ in $f(l, r)$ has value of $1$ in $f(l, r+1)$. Therefore, if we find $r_1, r_2, \ldots, r_{2n}$, the answer will be $(2n - r_1 + 1) + (2n - r_2 + 1) + \ldots + (2n - r_{2n} + 1)$. (In other words, we are counting all pairs $(l, r_l), (l, r_l+1), \ldots, (l, 2n)$, for all $1 \le l \le 2n$).
    137 
    138 The second observation follows: $r_1 \le r_2 \le \ldots \le r_{2n}$. It is clear that the only difference between grids $f(l, r_l)$ and $f(l+1, r_l)$ is that $f(l+1, r_l)$ has the same or a greater amount of cells with value of $0$, and if some cell has value of $1$ in $f(l+1, r_l)$, it has value of $1$ in $f(l, r_l)$. If we do not have a down-right path anymore in $f(l+1, r_l)$, there is no down right path in any $f(l+1, r)$ with $r \le r_l$. It follows that $r_{l+1} \ge r_l$.
    139 
    140 This observation allows us to use two pointers. For some fixed $l$ and $r$, if $(l, r)$ is not good, we will keep increasing $r$ until it is good, or in other words find $r_l$. We activate all cells with value of $r+1$. To check if the pair $(l, r+1)$ is good, we get the first de-activated cell in the first row and the last de-activated cell in the last row (a cell is de-activated if it does not belong in the range we are currently considering). This can be done by keeping two sets of de-activated cells, one for each row. Suppose that those are at columns $a$ and $b$ respectively. There exists a down-right path in $f(l, r+1)$ if and only if $a - 1 \gt b$ (we can reach cell $(1, a-1)$, then go to cell $(2, a-1)$ and the proceed to $(2, n)$). Once we find $r_l$, we will increase $l$, de-activate every cell with value of $l$, and keep increasing $r_l$ until we find $r_{l+1}$, and so on.
    141 
    142 **Implementation**
    143 
    144 ```
    145 // nifeshe
    146 
    147 #ifdef LOCAL
    148     #include <bits/include_all.h>
    149 #else
    150     #include <bits/stdc++.h>
    151     #include <ext/pb_ds/assoc_container.hpp>
    152     #include <ext/pb_ds/tree_policy.hpp>
    153 #endif
    154 
    155 #pragma GCC target ("avx2")
    156 #pragma GCC optimize ("Ofast")
    157 #pragma GCC optimize ("unroll-loops")
    158 
    159 #define all(x) (x).begin(), (x).end()
    160 #define rall(x) (x).rbegin(), (x).rend()
    161 #define int long long
    162 
    163 using namespace std;
    164 using namespace __gnu_pbds;
    165 
    166 template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    167 template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
    168 template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
    169 
    170 typedef long long ll;
    171 typedef long double ld;
    172 typedef pair<int, int> pii;
    173 
    174 const ll mod = 998244353;
    175 const ll inf = 1e18;
    176 const int MAX = 2e5 + 42;
    177 
    178 random_device rd;
    179 mt19937 gen(rd());
    180 uniform_int_distribution<ll> dis(1, inf);
    181 
    182 void solve() {
    183     int n;
    184     cin >> n;
    185     vector<vector<int>> a(2, vector<int>(n));
    186     for(auto &i : a) {
    187         for(auto &j : i) {
    188             cin >> j;
    189         }
    190     }
    191 
    192     vector<vector<pii>> pos(2 * n + 1);
    193     for(int i = 0; i < 2; i++) {
    194         for(int j = 0; j < n; j++) {
    195             pos[a[i][j]].push_back({i, j});
    196         }
    197     }
    198 
    199     array<set<int>, 2> st;
    200     st[0].insert(inf);
    201     st[1].insert(-inf);
    202     for(int i = 0; i < n; i++) st[0].insert(i);
    203     for(int i = 0; i < n; i++) st[1].insert(i);
    204 
    205     auto add = [&](int x) {
    206         for(auto [i, j] : pos[x]) {
    207             st[i].erase(j);
    208         }
    209     };
    210 
    211     auto del = [&](int x) {
    212         for(auto [i, j] : pos[x]) {
    213             st[i].insert(j);
    214         }
    215     };
    216 
    217     auto check = [&]() {
    218         if(st[0].count(0)) return false;
    219         if(st[1].count(n - 1)) return false;
    220         if(*st[0].begin() - 1 <= *st[1].rbegin()) return false;
    221 
    222         return true;
    223     };
    224 
    225     int ans = 0;
    226     int r = 0;
    227     for(int l = 1; l <= 2 * n; l++) {
    228         while(r + 1 <= 2 * n && !check()) {
    229             add(++r);
    230         }
    231         if(!check()) break;
    232 
    233         ans += 2 * n - r + 1;
    234         del(l);
    235     }
    236 
    237     cout << ans << '\n';
    238 }
    239 
    240 signed main() {
    241     ios_base::sync_with_stdio(0); cin.tie(0);
    242     int ttt = 1;
    243     cin >> ttt;
    244     while(ttt--) {
    245         solve();
    246     }
    247 }
    248 ```
    249 
    250 **Rate the Problem**
    251 
    252 * Amazing
    253 * Good
    254 * Average
    255 * Bad
    256 
    257 **Rate the Difficulty**
    258 
    259 * Very Hard
    260 * Hard
    261 * Average
    262 * Easy
    263 * Very Easy
    264 
    265 [Problem D1 — Diadrash (Easy Version)](https://codeforces.com/contest/2163/problem/D1)
    266 
    267 **Solution**
    268 
    269 First, observe that if a range is completely inside another, it is useless. Specifically, assume we have two ranges $[l_1, r_1]$ and $[l_2, r_2]$. If $1 \le l_2 \le l_1 \le r_1 \le r_2 \le n$, then we know that $\operatorname{MEX}(p[l_1 \ldots r_1]) \le \operatorname{MEX}(p[l_2 \ldots r_2])$. So we must only consider the range $[l_2, r_2]$.
    270 
    271 After cleaning out those ranges, we are left with at most $n$ ranges. This is obvious because for every possible left endpoint, we have at most one possible right endpoint (the maximum one among all given ranges).
    272 
    273 Now, suppose we also knew the position of $0$. Let it be $p_0$. We know that if some range does not include $p_0$, it is also useless. I claim that removing these ranges leaves at most $\lceil \frac{n}{2} \rceil$ possible ranges we must consider. Specifically, if $p_0 \le \frac{n}{2}$, we only consider ranges with left endpoint before than $p_0$. Otherwise, if $p_0 \ge \frac{n}{2}$, we only consider ranges with right endpoint after $p_0$. In both cases, it is obvious we consider at most $\lceil \frac{n}{2} \rceil$ ranges.
    274 
    275 Finally, notice that we do not care about the exact value of $p_0$, but only if it is in the first half or the second half. Therefore, we will do a query of the form $[1, \frac{n}{2}]$, determine which half $p_0$ is in, clean out useless ranges and query the rest. This results to at most $\lceil \frac{n}{2} \rceil + 1$ queries, and the problem is solved.
    276 
    277 **Implementation**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 using namespace std;
    282  
    283 int LIM, Q;
    284  
    285 int ask(int l, int r) {
    286     Q++;
    287     assert(Q <= LIM);
    288     cout << "? " << l << " " << r << endl;
    289     int ans; cin >> ans;
    290     return ans;
    291 }
    292  
    293 bool inside(int l, int r, bool toL, int n) {
    294     int midL = n / 2;
    295     if (toL) {
    296         return l <= midL;
    297     }
    298     else return r > midL;
    299 }
    300  
    301 void solve() {
    302     int n, q; cin >> n >> q;
    303     Q = 0;
    304     LIM = max(30, n / 2 + n % 2 + 5);
    305     vector<int> maxR(n+1, 0);
    306     for (int i = 1; i <= q; i++) {
    307         int l, r; cin >> l >> r;
    308         maxR[l] = max(maxR[l], r);
    309     }
    310     bool toL = (ask(1, n/2) > 0);
    311     int ans = 0, mx = 0;
    312     for (int i = 1; i <= n; i++) {
    313         if (maxR[i] > mx && inside(i, maxR[i], toL, n)) {
    314             ans = max(ans, ask(i, maxR[i]));
    315         }
    316         mx = max(mx, maxR[i]);
    317     }
    318     cout << "! " << ans << endl;
    319 }
    320  
    321 int main() {
    322     int t; cin >> t;
    323     while (t--) solve();
    324     return 0;
    325 }
    326 ```
    327 
    328 **Rate the Problem**
    329 
    330 * Amazing
    331 * Good
    332 * Average
    333 * Bad
    334 
    335 **Rate the Difficulty**
    336 
    337 * Very Hard
    338 * Hard
    339 * Average
    340 * Easy
    341 * Very Easy
    342 
    343 [Problem D2 — Diadrash (Hard Version)](https://codeforces.com/contest/2163/problem/D2)
    344 
    345 Special thanks to [Friedrich](/profile/Friedrich "Master Friedrich") for figuring out the better solution.
    346 
    347 **Solution**
    348 
    349 Please read the first two paragraphs of the solution to the Easy Version first. Suppose we have cleaned out the ranges that are completely inside other ranges.
    350 
    351 A useful property to consider, is that for a range $[l, r]$ it holds that $\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$. To prove this, consider the first non-negative integer $k$ such that it does not appear in $p[l...r]$. In other words, $\operatorname{MEX}(p[l...r]) = k$. If $k$ appears to the left of the range, we have $\operatorname{MEX}(p[1...r]) \gt k$ and $\operatorname{MEX}(p[l...n]) = k$. Otherwise, we have $\operatorname{MEX}(p[1...r]) = k$ and $\operatorname{MEX}(p[l...n]) \gt k$. In both cases, it holds $k = \operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$.
    352 
    353 Consider a set of ranges $S$, such that no range is completely inside another. Picking a range $[l, r]$ of this set splits $S$ to two subsets: one set $L$ includes all ranges $[l_1, r_1]$ such that $l_1 \lt l$, and the other set $R$ includes all ranges $[l_2, r_2]$ such that $l \lt l_2$. If we could find the best subset to keep searching in depending on $[l, r]$, we could perform binary search and find the answer quickly.
    354 
    355 So we now have the subproblem: given a range $[l, r]$, figure out if the oprimal subset to search is $L$ or $R$. We will use the following properties:
    356 
    357 * $\operatorname{MEX}(p[1...i]) \le \operatorname{MEX}(p[1...i+1])$.
    358 * $\operatorname{MEX}(p[i+1...n]) \le \operatorname{MEX}(p[i...n])$.
    359 * $\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$
    360 
    361 Suppose $a = \operatorname{MEX}(p[1...r])$ and $b = \operatorname{MEX}(p[l...n])$. If $a \lt b$, we have no reason to go to $L$. This is because the prefix $\operatorname{MEX}$ will keep decreasing, but the suffix $\operatorname{MEX}$ will keep increasing, so we will always pick the prefix which is definitely not as great as the current $a$. Therefore, we will move to $R$. Likewise, if $a \gt b$, we will move to $L$. Note that the case $a = b$ is only possible if $[l..r] = [1...n]$, in which case the answer is $n$.
    362 
    363 Therefore, for each range we consider we make $2$ queries, and we do this with binary search at most $\log{n}$ times. We have solved the problem in $2\log{n}$ queries.
    364 
    365 **Implementation**
    366 
    367 ```
    368 #include <bits/stdc++.h>
    369 using namespace std;
    370 #define int long long
    371  
    372 int ask(int l, int r) {
    373     cout << "? " << l << " " << r << endl;
    374     int ans; cin >> ans;
    375     return ans;
    376 }
    377  
    378 void solve() {
    379     int n, q; cin >> n >> q;
    380     vector<int> maxR(n+1, -1);
    381     for (int i = 1; i <= q; i++) {
    382         int u, v; cin >> u >> v;
    383         maxR[u] = max(maxR[u], v);
    384     }
    385     vector<pair<int, int>> ranges;
    386     int mr = 0;
    387     for (int i = 1; i <= n; i++) {
    388         if (maxR[i] > mr) {
    389             mr = maxR[i];
    390             ranges.push_back({i, maxR[i]});
    391         }
    392     }
    393     q = ranges.size();
    394     int lo = 0, hi = q-1;
    395     int ans = 0;
    396     while (lo <= hi) {
    397         int mid = (lo + hi) / 2;
    398         int l = ranges[mid].first;
    399         int r = ranges[mid].second;
    400         int pref = ask(1, r);
    401         int suff = ask(l, n);
    402         ans = max(ans, min(pref, suff));
    403         if (pref > suff) {
    404             hi = mid-1;
    405         }
    406         else lo = mid+1;
    407     }
    408     cout << "! " << ans << endl;
    409 }
    410  
    411 signed main() {
    412     ios_base::sync_with_stdio(0);
    413     cin.tie(0);
    414     int t; cin >> t;
    415     while (t--) solve();
    416     return 0;
    417 }
    418 ```
    419 
    420 **Rate the Problem**
    421 
    422 * Amazing
    423 * Good
    424 * Average
    425 * Bad
    426 
    427 **Rate the Difficulty**
    428 
    429 * Very Hard
    430 * Hard
    431 * Average
    432 * Easy
    433 * Very Easy
    434 
    435 [Problem E — Plegma](https://codeforces.com/contest/2163/problem/E)
    436 
    437 **Solution**
    438 
    439 First, we consider an easier version of the problem: what if every cell of the first column had the same value?
    440 
    441 Suppose that every cell of the first column has value of $1$. We have the following information:
    442 
    443 * No matter which row Player A sends, the first cell of that row has value of $1$.
    444 * Player A has the choice of sending a column full of $1$s.
    445 * If $C = 0$, there exists a cell with value of $0$. ($C = 0$ and every cell having value of $1$ is a contradiction).
    446 
    447 This information leads us to the following strategy. If $C = 1$, Player A may send any row and the first column. Otherwise, if $C = 0$, he can send any row and find a column that has a $0$ in it. Then, Player B can simply compare the first cell of the row with every cell of the column; if they all match, the answer is $1$, and otherwise it is $0$.
    448 
    449 If every cell of the first column is $0$, the solution is the same. Note there must exist at least one $1$ in the grid, as mentioned in the statement (connectivity would not be well defined otherwise). So if $C = 0$ Player A sends any row and the first column, and otherwise if $C = 1$ he sends any row and finds a column which includes a $1$. Again, Player B will compare the value of the first cell of the row with the value every cell of the column, and if they match he answers $0$ and $1$ otherwise.
    450 
    451 Now we can generalize this solution the case where there exists both a $0$ and a $1$ in the first column. Player B always compares the first cell of the row he received: if there exists a cell with different value in the column he determines the answer is the opposite of the value of the first cell of the row. We know the following:
    452 
    453 * Player A can send a column with both a $0$ and a $1$ (The first column).
    454 * Player A can choose a row, such that its first cell has value $0$.
    455 * Player A can choose a row, such that its first cell has value $1$.
    456 
    457 Therefore, Player A can always choose the first column and the appropriate row according to $C$ such that the previous strategy still works for Player B.
    458 
    459 **Implementation**
    460 
    461 ```
    462 #include <bits/stdc++.h>
    463 using namespace std;
    464  
    465 int ask(vector<vector<bool>> &grid, vector<pair<int, int>> arr, int op) {
    466     int ans = 0;
    467     if(op==0) ans=1;
    468     for (auto [a, b]: arr) {
    469         if(op) ans=ans||grid[a][b];
    470         else ans=ans&&grid[a][b];
    471     }
    472     return ans;
    473 }
    474  
    475 void ans(bool x) {
    476     cout << x << endl;
    477 }
    478  
    479 int find_row(vector<vector<bool>> &grid, int need, int n) {
    480     int lo = 1, hi = n;
    481     int fin = 1;
    482     while (lo <= hi) {
    483         int mid = (lo + hi) / 2;
    484         vector<pair<int, int>> qr;
    485         for (int i = 1; i <= mid; i++) qr.push_back({i, 1});
    486         if (need == ask(grid, qr, need)) {
    487             fin = mid;
    488             hi = mid-1;
    489         } 
    490         else lo = mid+1;
    491     }
    492     return fin;
    493 }
    494  
    495 int find_col(vector<vector<bool>> &grid, int need, int n) {
    496     int lo = 1, hi = n;
    497     int fin = 1;
    498     while (lo <= hi) {
    499         int mid = (lo + hi) / 2;
    500         vector<pair<int, int>> qr;
    501         for (int i = 1; i <= n; i++) {
    502             for (int j = 1; j <= mid; j++) {
    503                 qr.push_back({i, j});
    504             }
    505         }
    506         if (need == ask(grid, qr, need)) {
    507             fin = mid;
    508             hi = mid-1;
    509         }
    510         else lo = mid+1;
    511     }
    512     return fin;
    513 }
    514  
    515 void send_grid() {
    516     int n; cin >> n;
    517     bool ans; cin >> ans;
    518     vector<vector<bool>> grid(n+1, vector<bool>(n+1));
    519     for(int i = 0; i < n; i++) {
    520         string s;
    521         cin >> s;
    522         for(int j = 0; j < n; j++) if(s[j]=='1') grid[i+1][j+1]=1;
    523     }
    524     vector<pair<int, int>> qr;
    525     for (int i = 1; i <= n; i++) {
    526         qr.push_back({i, 1});
    527     }
    528     int o = ask(grid, qr, 1), a = ask(grid, qr, 0);
    529     int col, row;
    530     if (o == 1 && a == 0) {
    531         col = 1;
    532         row = find_row(grid, !ans, n);
    533     }
    534     else if (o == 0) {
    535         row = 1;
    536         if (ans == 0) col = 1;
    537         else col = find_col(grid, 1, n);
    538     }
    539     else {
    540         row = 1;
    541         if (ans == 1) col = 1;
    542         else col = find_col(grid, 0, n);
    543     }
    544     cout << row << " " << col << endl; 
    545 }
    546  
    547 void receive_grid() {
    548     int n; cin >> n;
    549     string row,col;
    550     cin >> row >> col;
    551     bool diff = false;
    552     for (int i = 0; i < n; i++) {
    553         if (col[i] != row[0]) diff = true;
    554     }
    555     if (diff) {
    556         ans(!(row[0]=='1'));
    557     }
    558     else {
    559         ans((row[0]=='1'));
    560     }
    561 }
    562  
    563 void solve() {
    564     string run; cin >> run;
    565     int t; cin >> t;
    566     if (run == "first") for (int i = 1; i <= t; i++) send_grid();
    567     else for (int i = 1; i <= t; i++) receive_grid();
    568 }
    569  
    570 int main() {
    571     int t = 1;
    572     while (t--) solve();
    573     return 0;
    574 }
    575 ```
    576 
    577 **Rate the Problem**
    578 
    579 * Amazing
    580 * Good
    581 * Average
    582 * Bad
    583 
    584 **Rate the Difficulty**
    585 
    586 * Very Hard
    587 * Hard
    588 * Average
    589 * Easy
    590 * Very Easy