1860.md (7830B)
1 Source: https://codeforces.com/blog/entry/119504 2 3 [1860A - Not a Substring](/contest/1860/problem/A "Educational Codeforces Round 153 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 ios::sync_with_stdio(false); cin.tie(0); 20 int t; 21 cin >> t; 22 while (t--) { 23 string s; 24 cin >> s; 25 int n = s.size(); 26 string a, b; 27 for (int i = 0; i < 2 * n; ++i) { 28 a += "()"[i & 1]; 29 b += ")("[i < n]; 30 } 31 if (a.find(s) == string::npos) { 32 cout << "YES\n" << a << '\n'; 33 } else if (b.find(s) == string::npos) { 34 cout << "YES\n" << b << '\n'; 35 } else { 36 cout << "NO\n"; 37 } 38 } 39 } 40 ``` 41 42 [1860B - Fancy Coins](/contest/1860/problem/B "Educational Codeforces Round 153 (Rated for Div. 2)") 43 44 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution 1 (BledDest)** 51 52 ``` 53 #include<bits/stdc++.h> 54 55 using namespace std; 56 57 int main() 58 { 59 int t; 60 cin >> t; 61 for(int i = 0; i < t; i++) 62 { 63 int m, k, a1, ak; 64 cin >> m >> k >> a1 >> ak; 65 int taken_k = m / k; 66 int taken_1 = m % k; 67 int taken_fancy_1 = max(0, taken_1 - a1); 68 int left_regular_1 = max(0, a1 - taken_1); 69 int taken_fancy_k = max(0, taken_k - ak); 70 int to_replace = min(left_regular_1 / k, taken_fancy_k); 71 int ans = taken_fancy_1 + taken_fancy_k - to_replace; 72 cout << ans << endl; 73 } 74 } 75 ``` 76 77 **Solution 2 (BledDest)** 78 79 ``` 80 #include<bits/stdc++.h> 81 82 using namespace std; 83 84 int main() 85 { 86 int t; 87 cin >> t; 88 for(int i = 0; i < t; i++) 89 { 90 int m, k, a1, ak; 91 cin >> m >> k >> a1 >> ak; 92 // function which calculates the number of fancy coins taken 93 // if we take exactly x coins of value k 94 auto f = [m, k, a1, ak](int x) 95 { 96 int taken_1 = m - k * x; 97 return max(0, taken_1 - a1) + max(0, x - ak); 98 }; 99 100 int lf = 0; 101 int rg = m / k; 102 while(rg - lf > 2) 103 { 104 int mid = (lf + rg) / 2; 105 if(f(mid) < f(mid + 1)) 106 rg = mid + 1; 107 else 108 lf = mid; 109 } 110 int ans = 1e9; 111 for(int i = lf; i <= rg; i++) ans = min(ans, f(i)); 112 cout << ans << endl; 113 } 114 } 115 ``` 116 117 [1860C - Game on Permutation](/contest/1860/problem/C "Educational Codeforces Round 153 (Rated for Div. 2)") 118 119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution (Neon)** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 using namespace std; 131 132 int main() { 133 ios::sync_with_stdio(false); cin.tie(0); 134 int t; 135 cin >> t; 136 while (t--) { 137 int n; 138 cin >> n; 139 int ans = 0; 140 int mn = n + 1, mnWin = n + 1; 141 while (n--) { 142 int x; 143 cin >> x; 144 if (mn < x && x < mnWin) { 145 ans += 1; 146 mnWin = x; 147 } 148 mn = min(mn, x); 149 } 150 cout << ans << '\n'; 151 } 152 } 153 ``` 154 155 [1860D - Balanced String](/contest/1860/problem/D "Educational Codeforces Round 153 (Rated for Div. 2)") 156 157 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 158 159 **Tutorial** 160 161 Tutorial is loading... 162 163 **Solution (Neon)** 164 165 ``` 166 #include <bits/stdc++.h> 167 168 using namespace std; 169 170 using li = long long; 171 172 const int N = 111; 173 174 int n; 175 string s; 176 int dp[2][N][N * N]; 177 178 int main() { 179 cin >> s; 180 n = s.size(); 181 dp[0][0][0] = 0; 182 for (int i = 0; i < n; ++i) { 183 for (int j = 0; j <= i + 1; ++j) { 184 for (int cnt = 0; cnt <= j * (i + 1 - j); ++cnt) { 185 dp[1][j][cnt] = n; 186 } 187 } 188 for (int j = 0; j <= i; ++j) { 189 for (int cnt = 0; cnt <= j * (i - j); ++cnt) { 190 dp[1][j + 1][cnt] = min(dp[1][j + 1][cnt], dp[0][j][cnt] + (s[i] != '0')); 191 dp[1][j][cnt + j] = min(dp[1][j][cnt + j], dp[0][j][cnt] + (s[i] != '1')); 192 } 193 } 194 swap(dp[0], dp[1]); 195 } 196 int cnt0 = count(s.begin(), s.end(), '0'); 197 cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n'; 198 } 199 ``` 200 201 [1860E - Fast Travel Text Editor](/contest/1860/problem/E "Educational Codeforces Round 153 (Rated for Div. 2)") 202 203 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 204 205 **Tutorial** 206 207 Tutorial is loading... 208 209 **Solution (awoo)** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 #define forn(i, n) for (int i = 0; i < int(n); i++) 215 216 using namespace std; 217 218 const int INF = 1e9; 219 const int AL = 26; 220 221 struct query{ 222 int f, t, ans; 223 }; 224 225 struct edge{ 226 int u, w; 227 }; 228 229 int main() { 230 cin.tie(0); 231 iostream::sync_with_stdio(false); 232 string s; 233 cin >> s; 234 int n = s.size(); 235 236 int m; 237 cin >> m; 238 vector<query> a(m); 239 forn(i, m){ 240 cin >> a[i].f >> a[i].t; 241 --a[i].f, --a[i].t; 242 a[i].ans = abs(a[i].f - a[i].t); 243 } 244 245 int k = n - 1 + AL * AL; 246 vector<vector<edge>> g(k); 247 forn(i, n - 1){ 248 int j = n - 1 + (s[i] - 'a') * AL + (s[i + 1] - 'a'); 249 g[i].push_back({j, 0}); 250 g[j].push_back({i, 1}); 251 if (i > 0){ 252 g[i].push_back({i - 1, 1}); 253 g[i - 1].push_back({i, 1}); 254 } 255 } 256 257 for (int st = n - 1; st < k; ++st){ 258 vector<int> d(k, INF); 259 d[st] = 0; 260 deque<int> q; 261 q.push_back(st); 262 while (!q.empty()){ 263 int v = q.front(); 264 q.pop_front(); 265 for (auto it : g[v]){ 266 if (d[it.u] <= d[v] + it.w) continue; 267 d[it.u] = d[v] + it.w; 268 if (it.w == 0) q.push_front(it.u); 269 else q.push_back(it.u); 270 } 271 } 272 forn(i, m){ 273 a[i].ans = min(a[i].ans, d[a[i].f] + d[a[i].t] - 1); 274 } 275 } 276 277 forn(i, m) cout << a[i].ans << '\n'; 278 return 0; 279 } 280 ``` 281 282 [1860F - Evaluate RBS](/contest/1860/problem/F "Educational Codeforces Round 153 (Rated for Div. 2)") 283 284 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 285 286 **Tutorial** 287 288 Tutorial is loading... 289 290 **Solution (awoo)** 291 292 ``` 293 #include <bits/stdc++.h> 294 295 #define forn(i, n) for (int i = 0; i < int(n); i++) 296 297 using namespace std; 298 299 const int INF = 1e9; 300 301 struct bracket{ 302 int a, b, c; 303 }; 304 305 struct point{ 306 int x, y; 307 }; 308 309 long long cross(const point &a, const point &b){ 310 return a.x * 1ll * b.y - a.y * 1ll * b.x; 311 } 312 313 long long dot(const point &a, const bracket &b){ 314 return a.x * 1ll * b.a + a.y * 1ll * b.b; 315 } 316 317 bool operator <(const point &a, const point &b){ 318 return cross(a, b) > 0; 319 } 320 321 int main() { 322 int t; 323 cin >> t; 324 while (t--){ 325 int n; 326 cin >> n; 327 vector<bracket> val; 328 forn(i, 2 * n){ 329 int a, b; 330 string c; 331 cin >> a >> b >> c; 332 val.push_back({a, b, c[0] == '(' ? 1 : -1}); 333 } 334 map<point, vector<int>> opts; 335 forn(i, 2 * n) forn(j, 2 * n){ 336 int dx = val[i].b - val[j].b; 337 int dy = val[j].a - val[i].a; 338 if (dx <= 0 || dy <= 0) continue; 339 opts[{dx, dy}].push_back(i); 340 opts[{dx, dy}].push_back(j); 341 } 342 opts[{1, INF}]; 343 vector<int> ord(2 * n), rord(2 * n); 344 iota(ord.begin(), ord.end(), 0); 345 sort(ord.begin(), ord.end(), [&](int i, int j){ 346 long long di = dot({INF, 1}, val[i]); 347 long long dj = dot({INF, 1}, val[j]); 348 if (di != dj) return di < dj; 349 return val[i].c > val[j].c; 350 }); 351 forn(i, 2 * n) rord[ord[i]] = i; 352 int neg = 0, cur = 0; 353 vector<int> bal(1, 0); 354 for (int i : ord){ 355 cur += val[i].c; 356 bal.push_back(cur); 357 neg += cur < 0; 358 } 359 bool ans = neg == 0; 360 vector<int> prv; 361 for (auto it : opts){ 362 vector<int> tot = prv; 363 for (int x : it.second) tot.push_back(x); 364 sort(tot.begin(), tot.end(), [&](int i, int j){ 365 return rord[i] < rord[j]; 366 }); 367 tot.resize(unique(tot.begin(), tot.end()) - tot.begin()); 368 for (int x : tot) neg -= bal[rord[x] + 1] < 0; 369 vector<int> tmp = tot; 370 sort(tot.begin(), tot.end(), [&](int i, int j){ 371 long long di = dot(it.first, val[i]); 372 long long dj = dot(it.first, val[j]); 373 if (di != dj) return di < dj; 374 return val[i].c > val[j].c; 375 }); 376 vector<int> nrord(tot.size()); 377 forn(i, tot.size()) nrord[i] = rord[tmp[i]]; 378 forn(i, tot.size()) rord[tot[i]] = nrord[i]; 379 for (int x : tot){ 380 bal[rord[x] + 1] = bal[rord[x]] + val[x].c; 381 neg += bal[rord[x] + 1] < 0; 382 } 383 if (neg == 0){ 384 ans = true; 385 break; 386 } 387 prv = it.second; 388 } 389 puts(ans ? "YES" : "NO"); 390 } 391 return 0; 392 } 393 ```