codeforces-scrape

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

279.md (11105B)


      1 Source: https://codeforces.com/blog/entry/95148
      2 
      3 [Continuing](https://codeforces.com/blog/entry/83942) with the theme of absent editorials for old rounds, here is an editorial for [Codeforces Round 171 (Div. 2)](/contest/279 "Codeforces Round 171 (Div. 2)"). Even though there is an official editorial, it is only in russian and doesn't have solution for the last problem.
      4 
      5 A
      6 
      7 **Editorial**
      8 
      9 ### [279A - Point on Spiral](/contest/279/problem/A "Codeforces Round 171 (Div. 2)")
     10 
     11 Since constraints are small, you can just simulate the whole process, but I'll explain an $O(1)$ solution. Let's look at the path
     12 
     13 ![](/predownloaded/29/e8/29e8a60536c8c2797c2e180f9fc640ee2eebc428.png)
     14 
     15 Now it's easy to see that the plane can be divided into four parts
     16 
     17 ![](/predownloaded/7a/21/7a21eb1014e8b41ee5a7d0bdf5563015c2123a56.png)
     18 
     19 And then we can calculate answer for each part separately, just be careful with borders. For example, for the right part the answer is $4x - 3$.
     20 
     21 **Code**
     22 
     23 ```
     24 #include "bits/stdc++.h"
     25 
     26 using namespace std;
     27 
     28 int main() {
     29     int x, y;
     30     cin >> x >> y;
     31     if (x == 0 && y == 0) {
     32         cout << 0 << '\n';
     33     } else if (-x + 1 < y && y <= x) {
     34         cout << 1 + (x - 1) * 4 << '\n';
     35     } else if (-y <= x && x < y) {
     36         cout << 2 + (y - 1) * 4 << '\n';
     37     } else if (x <= y && y < -x) {
     38         cout << 3 + (-x - 1) * 4 << '\n';
     39     } else {
     40         cout << 4 + (-y - 1) * 4 << '\n';
     41     }
     42 
     43     return 0;
     44 }
     45 ```
     46 
     47 B
     48 
     49 **Editorial**
     50 
     51 ### [279B - Books](/contest/279/problem/B "Codeforces Round 171 (Div. 2)")
     52 
     53 The problem can be written in the following way: for each index $i$ denote $r_i$ as the largest index such that $a_i + \ldots + a_{r_i} \leqslant t$. The problem is to find $max(r_i - i + 1)$.
     54 
     55 One can see that $r_i$ are nondecreasing, so the problem can be solved with two pointers: iterate over $i$ and keep a pointer to corresponding $r_i$.
     56 
     57 **Code**
     58 
     59 ```
     60 #include "bits/stdc++.h"
     61 
     62 using namespace std;
     63 
     64 int main() {
     65     int n, t;
     66     cin >> n >> t;
     67     vector<int> a(n);
     68     for (int& k : a)
     69         cin >> k;
     70 
     71     int r = 0;
     72     int sm = 0;
     73     int ans = 0;
     74     for (int i = 0; i < n; ++i) {
     75         while (r < n && sm + a[r] <= t) {
     76             sm += a[r];
     77             ++r;
     78         }
     79         ans = max(ans, r - i);
     80         sm -= a[i];
     81     }
     82 
     83     cout << ans << '\n';
     84 
     85     return 0;
     86 }
     87 ```
     88 
     89 C
     90 
     91 **Editorial**
     92 
     93 ### [279C - Ladder](/contest/279/problem/C "Codeforces Round 171 (Div. 2)")
     94 
     95 Let's calculate two arrays before answering queries. $tol[i]$ is the smallest index such that $[b_{tol[i]},\, \ldots,\, b_{i}]$ is nonincreasing, and $tor[i]$ is the largest index such that $[b_{i},\, \ldots,\, b_{tor[i]}]$ is nondecreasing. Then for each query we can take $tor[l]$ and $tol[r]$ and compare them. The answer is "Yes" iff $tor[l] \geqslant tol[r]$. In other words, we are checking if the largest nondecreasing segment from $l$ and largest nonincreasing segment from $r$ are intersecting.
     96 
     97 To calculate $tol[i]$, go over $i$ from $1$ to $n$ and maintain largest nonincreasing suffix. For $tor$ do the same in reverse.
     98 
     99 **Code**
    100 
    101 ```
    102 #include "bits/stdc++.h"
    103 
    104 using namespace std;
    105 
    106 int main() {
    107     int n, m;
    108     cin >> n >> m;
    109     vector<int> a(n);
    110     for (int& k : a)
    111         cin >> k;
    112 
    113     vector<int> tor(n), tol(n);
    114     iota(tol.begin(), tol.end(), 0);
    115     iota(tor.begin(), tor.end(), 0);
    116 
    117     tol[0] = 0;
    118     for (int i = 1; i < n; ++i)
    119         if (a[i - 1] >= a[i])
    120             tol[i] = tol[i - 1];
    121 
    122     tor[n - 1] = n - 1;
    123     for (int i = n - 2; i >= 0; --i)
    124         if (a[i] <= a[i + 1])
    125             tor[i] = tor[i + 1];
    126 
    127     while (m--) {
    128         int l, r;
    129         cin >> l >> r;
    130         --l; --r;
    131         cout << (tol[r] <= tor[l] ? "Yes" : "No") << '\n';
    132     }
    133 
    134     return 0;
    135 }
    136 ```
    137 
    138 D
    139 
    140 **Editorial**
    141 
    142 ### [279D - The Minimum Number of Variables](/contest/279/problem/D "Codeforces Round 171 (Div. 2)")
    143 
    144 You can notice that when we want to perform some operation, we are only interested in a subset of current values of variables (including zeros). So let's create $dp[i][mask] = bool$, which is $1$ if we can perform first $i$ operations and end up with the values from $mask$. Here $k$-bit in the mask corresponds to the value $vals[k]$, where array $vals$ stores all numbers in $a$ and a zero, and $k$-th bit is set iff the value of one of the variables is $vals[k]$.
    145 
    146 To make transition from $dp[i][mask]$ to $dp[i + 1][new\_mask]$, let's look at the operation. We have to find two values in the $mask$ such that their sum is $a[i + 1]$. Then to calculate $new\_mask$ we have to set $k$-th bit in the $mask$, where $k$ is such that $vals[k] = a[i + 1]$. Also, while writing new variable we can overwrite any existing variable, so we have an option to disable any bit in the $mask$.
    147 
    148 Now it looks like we have $O(2^nn)$ states and $n$ transitions from each state (disabling each bit). But actually if we only make transition from $dp[i][mask] = 1$, the complexity will be $O(2^nn)$, because for each $i$ there are at most $2^{i+1}$ masks that we can achieve, since there are only $i$ distinct numbers on the current prefix plus an additional zero. And $\sum_{i=1}^n 2^{i+1}\cdot n = O(2^nn)$.
    149 
    150 The only problem left is to check if we can build some number $y$ from $vals$ using numbers from $mask$. This can be precomputed in $O(2^nn)$: let's calculate array $possible[mask] = x$, where $i$-th bit in $x$ is set iff we can get number $vals[i]$ from mask on the next step. To calculate it, first for each $mask$ with at most $2$ bits just calculate all possible $x$ with any straightforward approach, since there are only $O(n^2)$ such masks. For any other mask notice that we can get $y$ iff sum of some two values equals to $y$. So we can iterate over all submasks such that they differ from $mask$ in exactly one bit and update $possible[mask]$ with $possible[submask]$. And since $mask$ has at least $3$ bits, if there is a pair which sums up to $y$, this pair will be included into at least one of the submasks. One can even notice that we only need any $3$ such submasks to cover every pair of bits.
    151 
    152 The answer is minimum number of bits over all masks such that $dp[n][mask] = 1$.
    153 
    154 **Code**
    155 
    156 ```
    157 #include "bits/stdc++.h"
    158 
    159 using namespace std;
    160 
    161 int main() {
    162     int n;
    163     cin >> n;
    164     vector<int> a(n);
    165     for (int& k : a)
    166         cin >> k;
    167 
    168     auto vals = a;
    169     vals.push_back(0);
    170     sort(vals.begin(), vals.end());
    171     vals.erase(unique(vals.begin(), vals.end()), vals.end());
    172 
    173     vector<int> pos(n);
    174     for (int i = 0; i < n; ++i) {
    175         pos[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    176     }
    177 
    178     vector<int> possible(1 << vals.size(), 0);
    179     for (int i = 1; i < possible.size(); ++i) {
    180         int k = 0;
    181         for (int j = 0; j < vals.size() && k < 3; ++j) {
    182             if ((i >> j) & 1) {
    183                 possible[i] |= possible[i ^ (1 << j)];
    184                 ++k;
    185             }
    186         }
    187         if (__builtin_popcount(i) <= 2) {
    188             for (int j = 0; j < vals.size(); ++j) {
    189                 if (!((i >> j) & 1)) continue;
    190                 for (int k = 0; k < vals.size(); ++k) {
    191                     if (!((i >> k) & 1)) continue;
    192                     int val = vals[j] + vals[k];
    193                     int ind = lower_bound(vals.begin(), vals.end(), val) - vals.begin();
    194                     if (ind < vals.size() && vals[ind] == val)
    195                         possible[i] |= (1 << ind);
    196                 }
    197             }
    198         }
    199     }
    200 
    201     vector<char> dp_cur(1 << vals.size(), 0);
    202     dp_cur[1 << pos[0]] = 1;
    203     dp_cur[(1 << pos[0]) | (1 << 0)] = 1;
    204 
    205     auto can_sum = [&](int mask, int pos) {
    206         return (possible[mask] >> pos) & 1;
    207     };
    208 
    209     vector<char> dp_next;
    210     for (int i = 1; i < n; ++i) {
    211         dp_next.assign(dp_cur.size(), false);
    212         for (int j = 0; j < dp_cur.size(); ++j) {
    213             if (dp_cur[j] && can_sum(j, pos[i])) {
    214                 int mask = j;
    215                 mask |= (1 << pos[i]);
    216                 dp_next[mask] = 1;
    217                 for (int k = 0; k < vals.size(); ++k)
    218                     if (((mask >> k) & 1) && vals[k] != a[i])
    219                         dp_next[mask ^ (1 << k)] = 1;
    220             }
    221         }
    222         swap(dp_cur, dp_next);
    223     }
    224 
    225     int ans = -1;
    226     for (int i = 0; i < dp_cur.size(); ++i) {
    227         if (!dp_cur[i]) continue;
    228         int sz = __builtin_popcount(i);
    229         if (ans == -1 || ans > sz)
    230             ans = sz;
    231     }
    232     cout << ans << '\n';
    233 
    234     return 0;
    235 }
    236 ```
    237 
    238 E
    239 
    240 **Editorial**
    241 
    242 ### [279E - Beautiful Decomposition](/contest/279/problem/E "Codeforces Round 171 (Div. 2)")
    243 
    244 First of all it's easy to notice that we will use each power of $2$ at most once.
    245 
    246 Let's look at the highest bit in the current number, suppose it's $2^k$. Since the sum of all powers of $2$ below $k$ is less than $2^k$, we will have to add at least one power of two $2^x$ with $x \geqslant k$. One can see that adding $2^{k+2}$ is not optimal, since then we will have to subtract at least $2^{k+1}$ and $2^{k+2} - 2^{k+1}$ can be replaced with $2^{k+1}$. So the only choices are $2^k$ or $2^{k+1}$. If we add $2^k$, we have to solve a problem for remaining number, which is a suffix or our current binary string. Otherwise, $2^{k+1}$ is larger than our current number, so we just need the answer for $m = 2^{k+1} - n$. Let's call such $m$ a complement for a number $n$ (notice that we don't need $k$ in the definition because $k$ is defined as largest bit in $n$)
    247 
    248 Now let's look at $m$. To calculate it, we have to flip all bits in $n$ and add $1$ to the result. Now it's easy to see that if $m$ is a complement for $n$, then for any suffix of $n$ (in binary form), the corresponding suffix of $m$ is a complement for it. Also, $n$ is a complement for $m$.
    249 
    250 So during our calculations we will only deal with $n$, $m$, suffixes of $n$ and suffixes of $m$. And this leads to a following dp solution: let $v[1] = n$, $v[2] = m$. Then $dp[ind][suf]$ is the smallest answer for a binary number represented by a suffix of number $v[ind]$ starting from index $suf$. We can calculate this $dp$ starting from $dp[\ldots][n]$ and the answer will be $dp[1][1]$.
    251 
    252 **Code**
    253 
    254 ```
    255 #include "bits/stdc++.h"
    256 
    257 using namespace std;
    258 
    259 int main() {
    260     string n;
    261     cin >> n;
    262     string m = n;
    263     {
    264         for (char& c : m) {
    265             c ^= '1' ^ '0';
    266         }
    267         int ind = m.size() - 1;
    268         while (ind >= 0 && m[ind] == '1') {
    269             m[ind] = '0';
    270             --ind;
    271         }
    272         if (ind == -1) {
    273             m.insert(m.begin(), '1');
    274             n.insert(n.begin(), '0');
    275         } else {
    276             m[ind] = '1';
    277         }
    278     }
    279 
    280     int sz = n.size();
    281 
    282     vector<string> v = {n, m};
    283     vector<array<int, 2>> dp(sz);
    284 
    285     dp[sz - 1][0] = (v[0].back() == '1');
    286     dp[sz - 1][1] = (v[1].back() == '1');
    287 
    288     for (int i = sz - 2; i >= 0; --i) {
    289         for (int b = 0; b < 2; ++b) {
    290             if (v[b][i] == '0') {
    291                 dp[i][b] = dp[i + 1][b];
    292             } else {
    293                 dp[i][b] = min(dp[i + 1][b] + 1, dp[i + 1][b ^ 1] + 1);
    294             }
    295         }
    296     }
    297 
    298     cout << dp[0][0] << '\n';
    299 
    300     return 0;
    301 }
    302 ```