1537.md (8657B)
1 Source: https://codeforces.com/blog/entry/91381 2 3 [1537A - Arithmetic Array](/contest/1537/problem/A "Codeforces Round 726 (Div. 2)") 4 5 **Tutorial** 6 7 To make the arithmetic mean be equal to exactly $1$ the sum needs to be equal to the number of elements in the array. 8 9 Let's consider $3$ cases for this problem: 10 11 1) The sum of the array equals $n$: Here the answer is $0$ since the arithmetic mean of the array is initially $1$. 12 13 2) The sum of the array is smaller than $n$: The answer is always $1$ since we can add a single integer $k$ such that $sum + k = n + 1$ is satisfied and more specifically $k = n - sum + 1$. 14 15 3) The sum of the array is greater than $n$: If we add any number apart from $0$ will add to the sum more or equal than to the number of elements. The number of $0$'s to add can be found by a loop of adding $0$'s until the number of elements is equal to the sum or by the simple formula of $sum-n$. 16 17 **Code** 18 19 ``` 20 #include "bits/stdc++.h" 21 using namespace std; 22 23 int main() 24 { 25 int t; 26 cin >> t; 27 while(t--){ 28 int n; 29 cin >> n; 30 int sum = 0; 31 for (int i = 0;i < n; i++){ 32 int a; 33 cin >> a; 34 sum += a; 35 } 36 if(sum < n)cout << "1\n"; 37 else cout << sum - n << "\n"; 38 } 39 } 40 ``` 41 42 [1537B - Bad Boy](/contest/1537/problem/B "Codeforces Round 726 (Div. 2)") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Code** 49 50 ``` 51 #include "bits/stdc++.h" 52 using namespace std; 53 54 int main() 55 { 56 int t; 57 cin >> t; 58 while(t--){ 59 int n, m, i, j; 60 cin >> n >> m >> i >> j; 61 62 cout << 1 << " " << 1 << " " << n << " " << m << "\n"; 63 } 64 } 65 ``` 66 67 [1537C - Challenging Cliffs](/contest/1537/problem/C "Codeforces Round 726 (Div. 2)") 68 69 **Tutorial** 70 71 Tutorial is loading... 72 73 **Code** 74 75 ``` 76 #include "bits/stdc++.h" 77 using namespace std; 78 79 int main() 80 { 81 int t; 82 cin >> t; 83 while(t--){ 84 int n; 85 cin >> n; 86 vector<int> h(n); 87 88 for (int i = 0;i < n; i++){ 89 cin >> h[i]; 90 } 91 sort(h.begin(), h.end()); 92 93 if(n == 2){ 94 cout << h[0] << " " << h[1] << "\n"; 95 continue; 96 } 97 98 int pos = -1, mn = INT_MAX; 99 100 for (int i = 1;i < n; i++){ 101 if(mn > abs(h[i] - h[i - 1])){ 102 pos = i; 103 mn = abs(h[i] - h[i - 1]); 104 } 105 } 106 107 for (int i = pos;i < n; i++){ 108 cout << h[i] << " "; 109 } 110 for(int i = 0;i < pos; i++){ 111 cout << h[i] << " "; 112 } 113 114 cout << "\n"; 115 116 } 117 } 118 ``` 119 120 [1537D - Deleting Divisors](/contest/1537/problem/D "Codeforces Round 726 (Div. 2)") 121 122 **Tutorial** 123 124 Tutorial is loading... 125 126 **Code** 127 128 ``` 129 #include "bits/stdc++.h" 130 using namespace std; 131 132 int main() 133 { 134 int t; 135 cin >> t; 136 137 while(t--){ 138 139 int n; 140 cin >> n; 141 if(n % 2 == 1){ 142 cout << "Bob\n"; 143 continue; 144 } 145 int cnt = 0; 146 while(n % 2 == 0){ 147 cnt++; 148 n /= 2; 149 } 150 151 if(n > 1){ 152 cout << "Alice\n"; 153 }else if(cnt % 2 == 0){ 154 cout << "Alice\n"; 155 }else cout << "Bob\n"; 156 } 157 } 158 ``` 159 160 [1537E1 - Erase and Extend (Easy Version)](/contest/1537/problem/E1 "Codeforces Round 726 (Div. 2)") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Code** 167 168 ``` 169 #include "bits/stdc++.h" 170 using namespace std; 171 172 string get(string s, int k){ 173 while((int)s.size() < k){ 174 s = s + s; 175 } 176 while((int)s.size() > k) 177 s.pop_back(); 178 return s; 179 } 180 int main() 181 { 182 int n, k; 183 string s; 184 cin >> n >> k; 185 cin >> s; 186 187 string pref = ""; 188 pref += s[0]; 189 190 string mn = get(pref, k); 191 192 for(int i = 1;i < n;i++){ 193 if(s[i] > s[0])break; 194 pref += s[i]; 195 mn = min(mn, get(pref, k)); 196 } 197 cout << mn << "\n"; 198 } 199 ``` 200 201 [1537E2 - Erase and Extend (Hard Version)](/contest/1537/problem/E2 "Codeforces Round 726 (Div. 2)") 202 203 **Tutorial** 204 205 We know that the final string is some prefix repeated a bunch of times. Incrementally for $i$ from $1$ to $n$ we will keep the longest among the first $i$ prefixes that gives the best answer we've seen so far. 206 207 So assume the $m-th$ prefix is currently the best and we're considering position $p$. If the $p-th$ character is greater than the corresponding character in $s_{1..m} \cdot (a lot)$ then the $p-th$ prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the $p-th$ are all less than or equal to the corresponding characters in $s_1..m \cdot (a lot)$, so if the $p-th$ is smaller than the corresponding we set the $p-th$ prefix as the best. 208 209 Now the interesting case is if the current character is the same as the corresponding one. Say then that $p = m + t$, by the logic of the previous paragraph we must have $s_{(m + 1)..(m + t)} = s_{1..t}$. If $t = m$ then the new prefix is just the old one twice, so set $p$ as the best prefix now. This ensures that otherwise $t \lt m$. 210 211 Denote $A = s_{1..t}$ and $B = s_{(t + 1)..m}$, so the string formed by the current best prefix is $ABABABABA...$ and the new one is $ABAABAABA...$ Now if $AB = BA$ then these strings are in fact the same, so set $m + t$ as the new best prefix. Otherwise we can find the first position where $AB$ and $BA$ differ, and use that to determine whether the new prefix is better. This can be done in $O(1)$ with Z function, thus giving a linear solution for the full problem. 212 213 Solution by [Ari](/profile/Ari "Grandmaster Ari"). 214 215 **Code** 216 217 ``` 218 #include <bits/stdc++.h> 219 using namespace std; 220 using ll = long long; 221 222 string s; 223 int n, k; 224 225 vector<int> z_func(string &s) { 226 int n = s.size(), L = -1, R = -1; 227 vector<int> z(n); 228 z[0] = n; 229 for(int i = 1; i < n; i++) { 230 if(i <= R) 231 z[i] = min(z[i - L], R - i + 1); 232 while(i + z[i] < n && s[i + z[i]] == s[z[i]]) 233 z[i]++; 234 if(i + z[i] - 1 > R) { 235 L = i; 236 R = i + z[i] - 1; 237 } 238 } 239 return z; 240 } 241 242 void finish(int m) { 243 for(int i = 0; i < k; i++) 244 cout << s[i % m]; 245 cout << '\n'; 246 exit(0); 247 } 248 249 int main() { 250 ios_base::sync_with_stdio(false); 251 cin.tie(0); 252 253 cin >> n >> k >> s; 254 auto z = z_func(s); 255 256 int cur = 1; 257 for(int i = 1; i < n; i++) { 258 if(s[i] > s[i % cur]) 259 finish(cur); 260 if(s[i] < s[i % cur]) { 261 cur = i + 1; 262 continue; 263 } 264 int off = i - cur + 1; 265 if(off == cur) { 266 cur = i + 1; 267 continue; 268 } 269 if(z[off] < cur - off) { 270 if(cur + off + z[off] >= k) { 271 cur = i + 1; 272 continue; 273 } 274 if(s[off + z[off]] > s[z[off]]) 275 cur = i + 1; 276 continue; 277 } 278 if(z[cur - off] < off) { 279 if(2 * cur + z[cur - off] >= k) { 280 cur = i + 1; 281 continue; 282 } 283 if(s[cur - off + z[cur - off]] < s[z[cur - off]]) 284 cur = i + 1; 285 continue; 286 } 287 cur = i + 1; 288 } 289 290 finish(cur); 291 } 292 ``` 293 294 [1537F - Figure Fixing](/contest/1537/problem/F "Codeforces Round 726 (Div. 2)") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Code** 301 302 ``` 303 #include "bits/stdc++.h" 304 using namespace std; 305 306 const int N = 2e5 + 10; 307 vector<long long> adj[N]; 308 long long s[N], n, m; 309 bool bipartite() 310 { 311 bool bip = true; 312 313 for(long long i = 0;i < n;i++) 314 s[i] = -1; 315 316 queue<long long> q; 317 318 for(long long i = 0;i < n;i++){ 319 if(s[i] != -1)continue; 320 321 q.push(i); 322 s[i] = 0; 323 324 while(!q.empty()){ 325 long long v = q.front(); 326 q.pop(); 327 328 for(long long u: adj[v]){ 329 if(s[u] == -1){ 330 s[u] = s[v] ^ 1; 331 q.push(u); 332 }else bip &= s[u] != s[v]; 333 } 334 } 335 } 336 return bip; 337 } 338 339 int main() 340 { 341 ios_base::sync_with_stdio(0);cin.tie(0); 342 long long T; 343 cin >> T; 344 while(T--) 345 { 346 cin >> n >> m; 347 for(long long i = 0;i < n;i++) 348 adj[i].clear(); 349 350 vector<long long> v(n), t(n); 351 long long p1 = 0, p2 = 0; 352 for(long long i = 0;i < n; i++){ 353 cin >> v[i]; 354 p1 = (p1 + abs(v[i])) % 2; 355 } 356 for (long long i = 0;i < n; i++){ 357 cin >> t[i]; 358 p2 = (p2 + abs(t[i])) % 2; 359 } 360 361 for(long long i = 0;i < m;i++){ 362 long long a, b; 363 cin >> a >> b; 364 --a, --b; 365 adj[a].push_back(b); 366 adj[b].push_back(a); 367 } 368 369 if(p1 != p2){ 370 cout << "NO\n"; 371 continue; 372 } 373 374 if(bipartite() == false){ 375 cout << "YES\n"; 376 }else{ 377 vector<long long> c(2, 0); 378 379 for(int i = 0;i < n;i++){ 380 c[s[i]] += v[i] - t[i]; 381 } 382 383 if(c[0] == c[1]){ 384 cout << "YES\n"; 385 }else cout << "NO\n"; 386 } 387 } 388 389 } 390 ```