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 . 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 ```