codeforces-scrape

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

1977.md (15583B)


      1 Source: https://codeforces.com/blog/entry/129858
      2 
      3 We hope you enjoyed the problems.
      4 
      5 Problem [1977A - Little Nikita](/contest/1977/problem/A "Codeforces Round 948 (Div. 2)") was created by [Stefan2417](/profile/Stefan2417 "Master Stefan2417") and prepared by [alexchist](/profile/alexchist "Master alexchist").
      6 
      7 Problem [1977B - Binary Colouring](/contest/1977/problem/B "Codeforces Round 948 (Div. 2)") was created by [alexchist](/profile/alexchist "Master alexchist") and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417").
      8 
      9 Problem [1977C - Nikita and LCM](/contest/1977/problem/C "Codeforces Round 948 (Div. 2)") was created and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417").
     10 
     11 Problem [1977D - XORificator](/contest/1977/problem/D "Codeforces Round 948 (Div. 2)") was created and prepared by [alexchist](/profile/alexchist "Master alexchist").
     12 
     13 Problem [1977E - Tensor](/contest/1977/problem/E "Codeforces Round 948 (Div. 2)") was created and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417").
     14 
     15 [1977A - Little Nikita](/contest/1977/problem/A "Codeforces Round 948 (Div. 2)")
     16 
     17 **Tutorial**
     18 
     19 Note that one action with the cube changes the parity of the number of cubes in the tower. Therefore, if the parities of $n$ and $m$ do not match, it is impossible to build the tower. Also, if $n \lt m$, the tower cannot be built either. In all other cases, it is possible to build a tower of height $m$ in $m$ operations, and then add and remove a cube until the operations are exhausted.
     20 
     21 **Author's code**
     22 
     23 ```
     24 #include <bits/stdc++.h>
     25 using namespace std;
     26  
     27 int main () {
     28   ios_base::sync_with_stdio(0); cin.tie(0);
     29   int T;
     30   cin >> T;
     31   while (T--) {
     32     int n, m;
     33     cin >> n >> m;
     34     cout << (n >= m && (n%2) == (m%2) ? "Yes" : "No") << '\n';
     35   }
     36 }
     37 ```
     38 
     39 **Feedback**
     40 
     41 * Good problem
     42 * Average problem
     43 * Bad problem
     44 
     45 [1977B - Binary Colouring](/contest/1977/problem/B "Codeforces Round 948 (Div. 2)")
     46 
     47 **Tutorial**
     48 
     49 We will iterate over the prefix of $i$ bits and construct a correct answer for the number formed by the prefix bits of the number $x$. We are interested in considering only the one bits, as they are the only ones that affect the value of the number $x$.
     50 
     51 If we have already placed a one at position $i$ in the answer, we need to somehow add $2^i$ to the number. To do this, we simply zero out the $i$-th bit in the answer and set it at $i + 1$ — this will add $2 \cdot 2^i = 2^{i+1}$.
     52 
     53 Now, the $i$-th position in the answer holds $0$.
     54 
     55 Let's consider what we placed at position $i-1$ in the answer. If it's $0$, then everything is fine; we just place $1$ at position $i$. If it's $1$, we have a situation of [1 1], which we correct by making it [-1 0 1] — placing $-1$ at $i-1$, leaving $0$ at $i$, and placing $1$ at $i+1$. This will add $2^i$ to the sum because $2^i + 2^{i-1} = 2^{i+1} - 2^{i-1}$. The remaining case is when $i-1$ holds $-1$, but this is impossible because our forward operations only place ones, and $-1$ is placed behind.
     56 
     57 The final time complexity is $O(\log(x))$ per test case.
     58 
     59 **Author's code**
     60 
     61 ```
     62 #include "bits/stdc++.h"
     63 
     64 #define all(a) a.begin(), a.end()
     65 #define pb push_back
     66 typedef long long ll;
     67 using namespace std;
     68 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
     69  
     70 /// Actual code starts here
     71 const int N = 100005;
     72  
     73 void solve() {
     74     ll x;
     75     cin >> x;
     76     vector<int> res(31, 0);
     77     for (int i = 0; i < 30; i++) {
     78         if (1ll & (x >> i)) {
     79             if (res[i]) {
     80                 res[i + 1] = 1;
     81                 res[i] = 0;
     82             } else if (i > 0) {
     83                 if (res[i - 1] == 1) {
     84                     res[i + 1] = 1;
     85                     res[i - 1] = -1;
     86                 } else {
     87                     res[i] = 1;
     88                 }
     89             } else if (i == 0) {
     90                 res[i] = 1;
     91             }
     92         }
     93     }
     94     cout << 31 << '\n';
     95     for (int i = 0; i <= 30; i++) {
     96         cout << res[i] << ' ';
     97     }
     98     cout << '\n';
     99 }
    100  
    101 signed main() {
    102     ios::sync_with_stdio(false);
    103     cin.tie(nullptr);
    104     cout.tie(nullptr);
    105     int tt = 1;
    106     cin >> tt;
    107     while (tt--)
    108         solve();
    109 }
    110 ```
    111 
    112 **Feedback**
    113 
    114 * Good problem
    115 * Average problem
    116 * Bad problem
    117 
    118 [1977C - Nikita and LCM](/contest/1977/problem/C "Codeforces Round 948 (Div. 2)")
    119 
    120 **Hint**
    121 
    122 Try to check if the entire array $a$ can be the answer.
    123 
    124 **Tutorial**
    125 
    126 First, let's understand if we can take the entire array $a$ as the special subsequence.
    127 
    128 To do this, find the LCM($a_1, a_2, \dots, a_n$). If it is greater than max($a_1, a_2, \dots, a_n$), then obviously such a number is not in the subsequence, because $LCM \geq max$.
    129 
    130 After this check, it becomes known that each $a_i \ | \ max(a_1, a_2, \dots, a_n)$.
    131 
    132 Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM.
    133 
    134 If we do this naively, it will be $O(\sqrt{C} + n \cdot d(C) \cdot \log(C))$, but this is already sufficient.
    135 
    136 Note that we can count the occurrence of each number and check only the distinct numbers. Then the complexity will be $O(\sqrt{C} + d(C)^2 \cdot \log(C))$.
    137 
    138 **Author's code**
    139 
    140 ```
    141 #include "bits/stdc++.h"
    142  
    143 #define err(x) cerr << "["#x"]  " << (x) << "\n"
    144 #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
    145 #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
    146 #define all(a) a.begin(), a.end()
    147 #define pb push_back
    148 typedef long long ll;
    149 typedef long double ld;
    150 using namespace std;
    151 const int MOD = 1000000007;
    152 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    153  
    154 template<typename T1, typename T2>
    155 inline bool relaxmi(T1 &a, const T2 &b) {
    156     return a > b ? a = b, true : false;
    157 }
    158  
    159 template<typename T1, typename T2>
    160 inline bool relaxma(T1 &a, const T2 &b) {
    161     return a < b ? a = b, true : false;
    162 }
    163  
    164 double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
    165  
    166 /// Actual code starts here
    167 const int N = 100005;
    168  
    169 int calc(vector<pair<int, int>> &t, int d) {
    170     int LCM = 0, cnt = 0;
    171     for (auto [j, c]: t) {
    172         if (d % j == 0) {
    173             if (LCM == 0) LCM = j;
    174             else LCM = lcm(LCM, j);
    175             cnt += c;
    176         }
    177     }
    178     if (LCM != d) cnt = 0;
    179     return cnt;
    180 }
    181  
    182 void solve() {
    183     int n;
    184     cin >> n;
    185     vector<int> v(n);
    186     for (auto &i: v) cin >> i;
    187     ll LCM = 1;
    188     int mx = *max_element(all(v));
    189     for (auto i: v) {
    190         LCM = lcm(LCM, i);
    191         if (LCM > mx) {
    192             cout << n << '\n';
    193             return;
    194         }
    195     }
    196     map<int, int> cnt;
    197     for (auto i: v) cnt[i]++;
    198     vector<pair<int, int>> t;
    199     for (auto i: cnt)
    200         t.push_back(i);
    201     int res = 0;
    202     for (int i = 1; i * i <= mx; i++) {
    203         if (mx % i == 0) {
    204             if (!cnt.contains(i))
    205                 relaxma(res, calc(t, i));
    206             if (!cnt.contains(mx / i))
    207                 relaxma(res, calc(t, mx / i));
    208         }
    209     }
    210     cout << res << '\n';
    211 }
    212  
    213 signed main() {
    214     ios::sync_with_stdio(false);
    215     cin.tie(nullptr);
    216     cout.tie(nullptr);
    217     int tt = 1;
    218     cin >> tt;
    219     while (tt--)
    220         solve();
    221 }
    222 ```
    223 
    224 **Feedback**
    225 
    226 * Good problem
    227 * Average problem
    228 * Bad problem
    229 
    230 [1977D - XORificator](/contest/1977/problem/D "Codeforces Round 948 (Div. 2)")
    231 
    232 **Hint**
    233 
    234 Try to fix the specialty of column $i$ and the presence of a one in cell $i, j$.
    235 
    236 **Tutorial**
    237 
    238 Let's assume that the value in the $i$-th row and $j$-th column is strictly one and it is the only one in the column.
    239 
    240 Then the entire table is uniquely determined, as well as the XORificator. For each possible state of the XORificator that constructs the required table,
    241 
    242 Let's maintain a counter. Then the state that maximizes the number of columns with exactly one 1 has the maximum counter.
    243 
    244 To efficiently maintain the counter, it is necessary to maintain the hash of the XORificator and quickly recalculate it when moving to the next row.
    245 
    246 The answer can be easily reconstructed by traversing the table again and counting the hash. If the desired hash is obtained, simply output the state of the XORificator.
    247 
    248 The final time complexity is $O(nm \log{(nm)})$ or $O(nm)$ if a hash map is used.
    249 
    250 For hashing, it is convenient to use [Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing).
    251 
    252 **Author's code**
    253 
    254 ```
    255 #include "bits/stdc++.h"
    256  
    257 using namespace std;
    258  
    259 mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
    260  
    261 void solve() {
    262     int n, m;
    263     cin >> n >> m;
    264     vector<vector<bool>> table(n, vector<bool>(m));
    265     for (int i = 0; i < n; ++i) {
    266         for (int j = 0; j < m; ++j) {
    267             char c;
    268             cin >> c;
    269             table[i][j] = c - '0';
    270         }
    271     }
    272     vector<long long> rands(n), rands2(n);
    273     for (int i = 0; i < n; ++i) {
    274         rands[i] = rnd();
    275         rands2[i] = rnd();
    276     }
    277     map<pair<long long, long long>, int> ans;
    278     int res = 0;
    279     pair<int, int> ind_ans = {0, 0};
    280     for (int j = 0; j < m; ++j) {
    281         long long summ = 0, summ2 = 0;
    282         for (int i = 0; i < n; ++i) {
    283             if (table[i][j]) {
    284                 summ ^= rands[i];
    285                 summ2 ^= rands2[i];
    286             }
    287         }
    288         for (int i = 0; i < n; ++i) {
    289             summ ^= rands[i];
    290             summ2 ^= rands2[i];
    291             ans[{summ, summ2}]++;
    292             if (res < ans[{summ, summ2}]) {
    293                 res = ans[{summ, summ2}];
    294                 ind_ans = {j, i};
    295             }
    296             summ ^= rands[i];
    297             summ2 ^= rands2[i];
    298         }
    299     }
    300     cout << res << "\n";
    301     string inds(n, '0');
    302     for (int i = 0; i < n; ++i) {
    303         if (table[i][ind_ans.first]) {
    304             if (i != ind_ans.second) {
    305                 inds[i] = '1';
    306             }
    307         } else if (ind_ans.second == i) {
    308             inds[i] = '1';
    309         }
    310     }
    311     cout << inds << "\n";
    312 }
    313  
    314 signed main() {
    315     ios::sync_with_stdio(false);
    316     cin.tie(nullptr);
    317     int tt = 1;
    318     cin >> tt;
    319     while (tt--) {
    320         solve();
    321     }
    322 }
    323 ```
    324 
    325 **Feedback**
    326 
    327 * Good problem
    328 * Average problem
    329 * Bad problem
    330 
    331 [1977E - Tensor](/contest/1977/problem/E "Codeforces Round 948 (Div. 2)")
    332 
    333 **Tutorial**
    334 
    335 First, let's understand why 2 colors are indeed sufficient.
    336 
    337 Notice that the reachability relation in a graph defines a [Partially Ordered Set](https://en.wikipedia.org/wiki/Partially_ordered_set).
    338 
    339 According to [Dilworth's Theorem](https://en.wikipedia.org/wiki/Dilworth%27s_theorem), the size of the maximum antichain is equal to the minimum number of chains that cover the Partially Ordered Set.
    340 
    341 Note that the condition on the reachability of pairs of vertices within any triplet implies a constraint on the maximum size of the antichain. It is simply no more than 2. Therefore, 2 colors are indeed sufficient.
    342 
    343 The remaining task is to understand how to explicitly construct these 2 chains.
    344 
    345 We will build this inductively. Let's maintain 3 stacks — the last vertices painted in black, white, and red respectively. These will correspond to the chains we are building.
    346 
    347 Suppose we have built chains on $n$ vertices and want to build them on $n + 1$:
    348 
    349 * If the white or black stacks are empty, simply add vertex $n+1$ to the empty stack.
    350 * If the red stack is empty:
    351 * + Ask about the reachability of the last vertices in the white and black stacks from vertex $n+1$.
    352 * + If both vertices are reachable, put vertex $n+1$ in the red stack.
    353 * + If only one vertex is reachable, put vertex $n+1$ in the stack whose last vertex is reachable from $n+1$.
    354 * + The case where neither vertex is reachable is impossible as it contradicts the condition.
    355 * If the red stack is not empty:
    356 * + Ask about the reachability of the last vertex in the red stack from vertex $n+1$.
    357 * + If it is reachable, put it in the red stack.
    358 * + If it is not reachable, ask about the end of the white stack.
    359 * + If the vertex at the end of the white stack is not reachable, then the vertex at the end of the black stack must be reachable, otherwise, it contradicts the problem's condition.
    360 * + Color vertex $n+1$ black if the black vertex is reachable or white if the white vertex is reachable.
    361 * + Recolor all vertices in the red stack to the opposite color relative to vertex $n+1$. We can do this because, by construction, all vertices in the white and black stacks are reachable from all vertices in the red stack.
    362 * + Do not forget to clear the red stack.
    363 
    364 Each time a new vertex is added, no more than 2 queries are used. Therefore, we will use no more than $2 \cdot n$ queries in total.
    365 
    366 During the algorithm, all operations are performed in $O(1)$ time, resulting in an overall complexity of $O(n)$.
    367 
    368 As an exercise for the reader, try to prove the lower bound on the number of queries.
    369 
    370 **Author's code**
    371 
    372 ```
    373 #include "bits/stdc++.h"
    374  
    375 #define err(x) cerr << "["#x"]  " << (x) << "\n"
    376 #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
    377 #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
    378 #define all(a) a.begin(), a.end()
    379 #define pb push_back
    380 typedef long long ll;
    381 typedef long double ld;
    382 using namespace std;
    383 const int MOD = 1000000007;
    384 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    385  
    386 template<typename T1, typename T2>
    387 inline bool relaxmi(T1 &a, const T2 &b) {
    388     return a > b ? a = b, true : false;
    389 }
    390  
    391 template<typename T1, typename T2>
    392 inline bool relaxma(T1 &a, const T2 &b) {
    393     return a < b ? a = b, true : false;
    394 }
    395  
    396 double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
    397  
    398 /// Actual code starts here
    399 const int N = 100005;
    400  
    401 bool ask(int i, int j) {
    402     cout << "? " << j << ' ' << i << endl;
    403     string resp;
    404     cin >> resp;
    405     if (resp == "-1") assert(false);
    406     if (resp == "YES") return true;
    407     else return false;
    408 }
    409  
    410 void solve() {
    411     int n;
    412     cin >> n;
    413     vector<int> st, st2, st3;
    414     st = {1};
    415     for (int i = 2; i <= n; i++) {
    416         if (st2.empty()) {
    417             if (ask(i, st.back())) {
    418                 st.push_back(i);
    419             } else {
    420                 st2.push_back(i);
    421             }
    422         } else if (st3.empty()) {
    423             int ok1 = ask(i, st.back()), ok2 = ask(i, st2.back());
    424             if (ok1 && ok2) {
    425                 st3.push_back(i);
    426             } else if (ok1) {
    427                 st.push_back(i);
    428             } else if (ok2) {
    429                 st2.push_back(i);
    430             } else {
    431                 assert(false);
    432             }
    433         } else {
    434             if (ask(i, st3.back())) {
    435                 st3.push_back(i);
    436             } else {
    437                 if (ask(i, st.back())) {
    438                     st.push_back(i);
    439                     for (auto j: st3)
    440                         st2.push_back(j);
    441                     st3.clear();
    442                 } else {
    443                     st2.push_back(i);
    444                     for (auto j: st3)
    445                         st.push_back(j);
    446                     st3.clear();
    447                 }
    448             }
    449         }
    450     }
    451     if (!st3.empty()) {
    452         for (auto i: st3)
    453             st.push_back(i);
    454         st3.clear();
    455     }
    456     vector<int> colors(n + 1);
    457     for (auto i: st2)
    458         colors[i] = 1;
    459     cout << "! ";
    460     for (int i = 1; i <= n; i++) cout << colors[i] << ' ';
    461     cout << endl;
    462 }
    463  
    464 signed main() {
    465     ios::sync_with_stdio(false);
    466     cin.tie(nullptr);
    467     cout.tie(nullptr);
    468     int tt = 1;
    469     cin >> tt;
    470     while (tt--)
    471         solve();
    472 }
    473 ```
    474 
    475 **Feedback**
    476 
    477 * Good problem
    478 * Average problem
    479 * Bad problem