codeforces-scrape

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

675.md (6769B)


      1 Source: https://codeforces.com/blog/entry/44902
      2 
      3 Someday I will arrange C and D correctly :)
      4 
      5 [675A - Infinite Sequence](/contest/675/problem/A "Codeforces Round 353 (Div. 2)")
      6 
      7 Firstly, in case *c* = 0 we should output YES if *a* = *b* else answer is NO.
      8 
      9 If *b* belongs to sequence *b* = *a* + *k* * *c* where k is non-negative integer.
     10 
     11 So answer is YES if (*b* - *a*) / *c* is non-negative integer else answer is NO.
     12 
     13 **Code**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17  
     18 using namespace std;
     19  
     20 int main() {
     21     int a, b, c;
     22     cin >> a >> b >> c;
     23  
     24     if (c == 0) {
     25         if (a == b) cout << "YESn";
     26         else cout << "NOn";
     27     } else {
     28         if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn";
     29         else cout << "NOn";
     30     }
     31 }
     32 ```
     33 
     34 [675B - Restoring Painting](/contest/675/problem/B "Codeforces Round 353 (Div. 2)")
     35 
     36 x a y
     37 
     38 b m c
     39 
     40 z d w
     41 
     42 Number in the center may be any from 1 to *n* because number in the center belongs to all subsquares 2 × 2. So, let's find answer with fixed number in the center and then multiply answer by *n*.
     43 
     44 Let's iterate over all possible *x*. Sums of each subsquare 2 × 2 are the same so *x* + *b* + *a* + *m* = *y* + *c* + *a* + *m* and *y* = *x* + *b* - *c*.
     45 
     46 Similarly, *z* = *x* + *a* - *d* and *w* = *a* + *y* - *d* = *z* + *b* - *c*.
     47 
     48 This square is legal if 1 ≤ *y*, *z*, *w* ≤ *n*. We should just check it.
     49 
     50 Also we can solve this problem in *O*(1).
     51 
     52 **Code**
     53 
     54 ```
     55 #include <iostream>
     56 
     57 using namespace std;
     58 
     59 int main() {
     60     int n, a, b, c, d;
     61     cin >> n >> a >> b >> c >> d;
     62 
     63     long long ans = 0;
     64     for (int x = 1; x <= n; x++) {
     65         int y = x + b - c;
     66         int z = x + a - d;
     67         int w = a + y - d;
     68         if (1 <= y && y <= n && 1 <= z && z <= n && 1 <= w && w <= n) {
     69             ans++;
     70         }
     71     }
     72     ans *= n;
     73 
     74     cout << ans << endl;
     75 }
     76 ```
     77 
     78 [675C - Money Transfers](/contest/675/problem/C "Codeforces Round 353 (Div. 2)")
     79 
     80 We have array *a**i* and should make all numbers in it be equal to zero with minimal number of operations. Sum of all *a**i* equals to zero.
     81 
     82 We can divide array into parts of consecutive elements with zero sum. If part has length *l* we can use all pairs of neighbours in operations and make all numbers be equal to zero with *l* - 1 operations.
     83 
     84 So, if we sum number of operations in each part we get *ans* = *n* - *k* where *k* is number of parts. We should maximize *k* to get the optimal answer.
     85 
     86 One of the part consists of some prefix and probably some suffix. Each of other parts is subarray of *a*.
     87 
     88 Let's calculate prefix sums. Each part has zero sum so prefix sums before each part-subarray are the same.
     89 
     90 So we can calculate *f* — number of occurencies of the most frequent number in prefix sums and answer will be equal to *n* - *f*.
     91 
     92 Bonus: how to hack solutions with overflow?
     93 
     94 **Code**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 
     99 using namespace std;
    100 
    101 int main() {
    102     ios_base::sync_with_stdio(false); cin.tie(0);
    103 
    104     int n;
    105     cin >> n;
    106     map<long long, int> d;
    107     long long sum = 0;
    108     int ans = n - 1;
    109     for (int i = 0; i < n; i++) {
    110         int t;
    111         cin >> t;
    112         sum += t;
    113         d[sum]++;
    114         ans = min(ans, n - d[sum]);
    115     }
    116 
    117     cout << ans << endl;
    118 }
    119 ```
    120 
    121 [675D - Tree Construction](/contest/675/problem/D "Codeforces Round 353 (Div. 2)")
    122 
    123 We have binary search tree (BST) and should insert number in it with good time complexity.
    124 
    125 Let we should add number *x*. Find numbers *l* < *x* < *r* which were added earlier, *l* is maximal possible, *r* is minimal possible (all will be similar if only one of this numbers exists). We can find them for example with std::set and upper_bound in C++.
    126 
    127 We should keep sorted tree traversal (it's property of BST). So *x* must be right child of vertex with *l* or left child of vertex with *r*.
    128 
    129 Let *l* hasn't right child and *r* hasn't left child. Hence lowest common ancestor (lca) of *l* and *r* doesn't equal to *l* or *r*. So lca is between *l* and *r* in tree traversal. But it's impossible because *l* is maximal possible and *r* is minimal possible. So *l* has right child or *r* has left child and we know exactly which of them will be parent of *x*.
    130 
    131 That's all. Time complexity is ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png).
    132 
    133 **Code**
    134 
    135 ```
    136 #include <iostream>
    137 #include <set>
    138 #include <map>
    139 
    140 using namespace std;
    141 
    142 int main() {
    143     ios_base::sync_with_stdio(false); cin.tie(0);
    144 
    145     set<int> numbers;
    146     map<int, int> left;
    147     map<int, int> right;
    148 
    149     int n, v;
    150     cin >> n >> v;
    151     numbers.insert(v);
    152     for (int i = 0; i < n - 1; i++) {
    153         cin >> v;
    154         auto it = numbers.upper_bound(v);
    155         int result;
    156         if (it != numbers.end() && left.count(*it) == 0) {
    157             left[*it] = v;
    158             result = *it;
    159         } else {
    160             it--;
    161             right[*it] = v;
    162             result = *it;
    163         }
    164         numbers.insert(v);
    165         cout << result;
    166         if (i == n - 2) cout << 'n';
    167         else cout << ' ';
    168     }
    169 }
    170 ```
    171 
    172 [675E - Trains and Statistic](/contest/675/problem/E "Codeforces Round 353 (Div. 2)")
    173 
    174 Let the indexation will be from zero. So we should subtract one from all *a**i*. Also let *a**n* - 1 = *n* - 1.
    175 
    176 *dp**i* is sum of shortests pathes from *i* to *i* + 1... *n* - 1.
    177 
    178 *dp**n* - 1 = 0
    179 
    180 *dp**i* = *dp**m* - (*a**i* - *m*) + *n* - *i* - 1 where *m* belongs to range from *i* + 1 to *a**i* and *a**m* is maximal. We can find *m* with segment tree or binary indexed tree or sparse table.
    181 
    182 Now answer equals to sum of all *dp**i*.
    183 
    184 **Code**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 
    189 using namespace std;
    190 
    191 const int maxn = 1 << 18;
    192 pair<int, int> tree[maxn * 2];
    193 
    194 void build(const vector<int> &a, int n) {
    195     for (int i = 0; i < n; i++) tree[maxn + i] = {a[i], i};
    196     for (int i = maxn - 1; i > 0; i--)
    197         tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    198 }
    199 
    200 int get(int l, int r) {
    201     pair<int, int> ans{-1, -1};
    202     for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
    203         if (l & 1) ans = max(ans, tree[l++]);
    204         if (r & 1) ans = max(ans, tree[--r]);
    205     }
    206     return ans.second;
    207 }
    208 
    209 int main() {
    210     ios_base::sync_with_stdio(false); cin.tie(0);
    211 
    212     int n;
    213     cin >> n;
    214     vector<int> a(n);
    215     a[n - 1] = n - 1;
    216     for (int i = 0; i < n - 1; i++) {
    217         cin >> a[i];
    218         a[i]--;
    219     }
    220 
    221     build(a, n);
    222     vector<long long> dp(n);
    223     long long ans = 0;
    224     dp[n - 1] = 0;
    225     for (int i = n - 2; i >= 0; i--) {
    226         int m = get(i + 1, a[i]);
    227         dp[i] = dp[m] - (a[i] - m) + n - i - 1;
    228         ans += dp[i];
    229     }
    230 
    231     cout << ans << 'n';
    232 }
    233 ```