2028.md (9990B)
1 Source: https://codeforces.com/blog/entry/136096 2 3 Thank you everyone for participating in the round! We hope you enjoyed the problems :) 4 5 ### [2028A - Alice's Adventures in ''Chess''](/contest/2028/problem/A "Codeforces Round 986 (Div. 2)") 6 7 **Hint** 8 9 How many times do you have to repeat the string until you know for certain whether Alice will ever reach the Red Queen? 10 11 **Solution** 12 13 Tutorial is loading... 14 15 **Code** 16 17 ``` 18 def solve(): 19 [n, a, b] = list(map(int, input().split())) 20 s = str(input()) 21 x, y = 0, 0 22 for __ in range(100): 23 for c in s: 24 if c == 'N': 25 y += 1 26 elif c == 'E': 27 x += 1 28 elif c == 'S': 29 y -= 1 30 else: 31 x -= 1 32 if x == a and y == b: 33 print("YES") 34 return 35 print("NO") 36 37 t = int(input()) 38 39 for _ in range(t): 40 solve() 41 ``` 42 43 ### [2028B - Alice's Adventures in Permuting](/contest/2028/problem/B "Codeforces Round 986 (Div. 2)") 44 45 **Hint** 46 47 Do casework on whether $b = 0$ or not. 48 49 **Solution** 50 51 Tutorial is loading... 52 53 **Code** 54 55 ``` 56 #include <bits/stdc++.h> 57 using namespace std; 58 59 using ll = long long; 60 using ld = long double; 61 using pii = pair<int, int>; 62 using vi = vector<int>; 63 #define rep(i, a, b) for(int i = a; i < (b); ++i) 64 #define all(x) (x).begin(), (x).end() 65 #define sz(x) (int)(x).size() 66 #define smx(a, b) a = max(a, b) 67 #define smn(a, b) a = min(a, b) 68 #define pb push_back 69 #define endl '\n' 70 71 const ll MOD = 1e9 + 7; 72 const ld EPS = 1e-9; 73 74 mt19937 rng(time(0)); 75 76 int main() { 77 cin.tie(0)->sync_with_stdio(0); 78 79 int t; cin >> t; 80 while (t--) { 81 ll n, b, c; cin >> n >> b >> c; 82 if (b == 0) { 83 if (c >= n) { 84 cout << n << "\n"; 85 } else if (c >= n - 2) { 86 cout << n - 1 << "\n"; 87 } else { 88 cout << -1 << "\n"; 89 } 90 } else { 91 if (c >= n) cout << n << "\n"; 92 else cout << n - max(0ll, 1 + (n - c - 1) / b) << "\n"; 93 } 94 } 95 } 96 ``` 97 98 ### [2028C - Alice's Adventures in Cutting Cake](/contest/2028/problem/C "Codeforces Round 986 (Div. 2)") 99 100 **Hint 1** 101 102 How can you quickly determine if Alice can ever receive the piece $a[i:j] = [a_i, a_{i+1}, \ldots, a_{j-1}]$? 103 104 **Hint 2** 105 106 For a given $i$, how can you quickly check the maximum $j$ such that Alice can receive the piece $a[i:j]$? 107 108 **Solution** 109 110 Tutorial is loading... 111 112 **Code** 113 114 ``` 115 #include <bits/stdc++.h> 116 using namespace std; 117 118 using ll = long long; 119 using ld = long double; 120 using pii = pair<int, int>; 121 using vi = vector<int>; 122 #define rep(i, a, b) for(int i = a; i < (b); ++i) 123 #define all(x) (x).begin(), (x).end() 124 #define sz(x) (int)(x).size() 125 #define smx(a, b) a = max(a, b) 126 #define smn(a, b) a = min(a, b) 127 #define pb push_back 128 #define endl '\n' 129 130 const ll MOD = 1e9 + 7; 131 const ld EPS = 1e-9; 132 133 mt19937 rng(time(0)); 134 135 int main() { 136 cin.tie(0)->sync_with_stdio(0); 137 138 int t; cin >> t; 139 while (t--) { 140 int n, m; cin >> n >> m; 141 ll v; cin >> v; 142 vector<ll> a(n); 143 rep(i,0,n) cin >> a[i]; 144 145 vector<ll> sums(n + 1); 146 rep(i,0,n) sums[i + 1] = sums[i] + a[i]; 147 148 auto query = [&](int i, int j) { // [i, j) 149 return sums[j] - sums[i]; 150 }; 151 152 auto compute_pfx = [&]() -> vector<int> { 153 vector<int> pfx(n + 1, 0); 154 int end = 0, val = 0; 155 ll sum = 0; 156 for (int start = 0; start < n; start++) { 157 while (end < n && sum < v) { 158 sum += a[end]; 159 ++end; 160 pfx[end] = max(pfx[end], pfx[end - 1]); 161 } 162 if (sum >= v) { 163 pfx[end] = 1 + pfx[start]; 164 } 165 sum -= a[start]; 166 } 167 rep(i,1,n+1) { 168 pfx[i] = max(pfx[i], pfx[i - 1]); 169 } 170 return pfx; 171 }; 172 173 auto pfx = compute_pfx(); 174 reverse(all(a)); 175 auto sfx = compute_pfx(); 176 reverse(all(a)); 177 reverse(all(sfx)); 178 179 if (pfx[n] < m) { 180 cout << "-1\n"; 181 continue; 182 } 183 184 int end = 0; 185 ll ans = 0; 186 for (int start = 0; start < n; start++) { 187 while (end < n && pfx[start] + sfx[end + 1] >= m) ++end; 188 if (pfx[start] + sfx[end] >= m) 189 ans = max(ans, query(start, end)); 190 } 191 cout << ans << "\n"; 192 } 193 } 194 ``` 195 196 ### [2028D - Alice's Adventures in Cards](/contest/2028/problem/D "Codeforces Round 986 (Div. 2)") 197 198 **Hint** 199 200 This is not a graph problem. Try to think about for each card $i$ whether Alice can ever trade up from $i$ to $n$. 201 202 **Solution** 203 204 Tutorial is loading... 205 206 **Code** 207 208 ``` 209 #include <bits/stdc++.h> 210 using namespace std; 211 212 using ll = long long; 213 using ld = long double; 214 using pii = pair<int, int>; 215 using vi = vector<int>; 216 #define rep(i, a, b) for(int i = a; i < (b); ++i) 217 #define all(x) (x).begin(), (x).end() 218 #define sz(x) (int)(x).size() 219 #define smx(a, b) a = max(a, b) 220 #define smn(a, b) a = min(a, b) 221 #define pb push_back 222 #define endl '\n' 223 224 const ll MOD = 1e9 + 7; 225 const ld EPS = 1e-9; 226 227 mt19937 rng(time(0)); 228 229 int main() { 230 cin.tie(0)->sync_with_stdio(0); 231 232 int t; cin >> t; 233 std::string s = "qkj"; 234 while (t--) { 235 int n; cin >> n; 236 vector p(3, vector<int>(n + 1)); 237 rep(i,0,3) rep(j,1,n + 1) cin >> p[i][j]; 238 vector<pair<char, int>> sol(n + 1, {'\0', -1}); 239 array<int, 3> mins = {n, n, n}; // minimizing index 240 for (int i = n - 1; i >= 1; i--) { 241 int win = -1; 242 rep(j,0,3) if (p[j][i] > p[j][mins[j]]) win = j; 243 if (win == -1) continue; 244 sol[i] = {s[win], mins[win]}; 245 rep(j,0,3) if (p[j][i] < p[j][mins[j]]) mins[j] = i; 246 } 247 if (sol[1].second == -1) { 248 cout << "NO\n"; 249 continue; 250 } 251 cout << "YES\n"; 252 vector<pair<char, int>> ans = {sol[1]}; 253 while (ans.back().second >= 0) { 254 ans.push_back(sol[ans.back().second]); 255 } 256 ans.pop_back(); 257 cout << sz(ans) << "\n"; 258 for (auto && [c, i] : ans) { 259 cout << c << " " << i << "\n"; 260 } 261 } 262 } 263 ``` 264 265 **Bonus** 266 267 Solve the same problem, but now with the additional requirement that the solution must use the minimum number of trades (same constraints). 268 269 ### [2028E - Alice's Adventures in the Rabbit Hole](/contest/2028/problem/E "Codeforces Round 986 (Div. 2)") 270 271 **Hint 1** 272 273 What are Alice's and the Red Queen's optimal moves at a given position? 274 275 **Hint 2** 276 277 Solve the problem for a path (bamboo) of length $n$ first. 278 279 **Hint 3** 280 281 Solve Hint 2 first. Now, generalize the solution to an arbitrary tree. 282 283 **Solution** 284 285 Tutorial is loading... 286 287 **Code** 288 289 ``` 290 #include <bits/stdc++.h> 291 using namespace std; 292 293 using ll = long long; 294 using ld = long double; 295 using pii = pair<int, int>; 296 using vi = vector<int>; 297 #define rep(i, a, b) for(int i = a; i < (b); ++i) 298 #define all(x) (x).begin(), (x).end() 299 #define sz(x) (int)(x).size() 300 #define smx(a, b) a = max(a, b) 301 #define smn(a, b) a = min(a, b) 302 #define pb push_back 303 #define endl '\n' 304 305 const ll MOD = 1e9 + 7; 306 const ld EPS = 1e-9; 307 308 // mt19937 rng(time(0)); 309 310 ll euclid(ll a, ll b, ll &x, ll &y) { 311 if (!b) return x = 1, y = 0, a; 312 ll d = euclid(b, a % b, y, x); 313 return y -= a/b * x, d; 314 } 315 316 const ll mod = 998244353; 317 struct mint { 318 ll x; 319 mint(ll xx) : x(xx) {} 320 mint operator+(mint b) { return mint((x + b.x) % mod); } 321 mint operator-(mint b) { return mint((x - b.x + mod) % mod); } 322 mint operator*(mint b) { return mint((x * b.x) % mod); } 323 mint operator/(mint b) { return *this * invert(b); } 324 mint invert(mint a) { 325 ll x, y, g = euclid(a.x, mod, x, y); 326 assert(g == 1); return mint((x + mod) % mod); 327 } 328 mint operator^(ll e) { 329 if (!e) return mint(1); 330 mint r = *this ^ (e / 2); r = r * r; 331 return e&1 ? *this * r : r; 332 } 333 }; 334 335 void solve() { 336 int n; cin >> n; 337 vector<vector<int>> t(n); 338 rep(i,0,n-1) { 339 int x, y; cin >> x >> y; --x, --y; 340 t[x].push_back(y); 341 t[y].push_back(x); 342 } 343 344 vector<int> d(n, n + 1); 345 function<int(int, int)> depths = [&](int curr, int par) { 346 for (auto v : t[curr]) { 347 if (v == par) continue; 348 d[curr] = min(d[curr], 1 + depths(v, curr)); 349 } 350 if (d[curr] > n) d[curr] = 0; 351 return d[curr]; 352 }; 353 354 depths(0, -1); 355 356 vector<mint> ans(n, 0); 357 function<void(int, int, mint)> dfs = [&](int curr, int par, mint val) { 358 ans[curr] = val; 359 for (auto v : t[curr]) { 360 if (v == par) continue; 361 dfs(v, curr, val * d[v] / (d[v] + 1)); 362 } 363 }; 364 365 dfs(0, -1, mint(1)); 366 for (auto x : ans) { 367 cout << x.x << " "; 368 } 369 cout << "\n"; 370 } 371 372 int main() { 373 cin.tie(0)->sync_with_stdio(0); 374 375 int t; cin >> t; 376 while (t--) solve(); 377 } 378 ``` 379 380 ### [2028F - Alice's Adventures in Addition](/contest/2028/problem/F "Codeforces Round 986 (Div. 2)") 381 382 **Hint 1** 383 384 Come up with a DP algorithm running in time $O(n^2 m)$. 385 386 **Hint 2** 387 388 Try optimizing the Hint 1 DP to run in time $O(nm \log m)$ when $a_i \ge 2$ for all $i$. 389 390 **Hint 3** 391 392 Do some casework to extend Hint 2 to $a_i \ge 0$. 393 394 **Hint 4** 395 396 [Bitset](https://codeforces.com/blog/entry/53168) 397 398 **Solution** 399 400 Tutorial is loading... 401 402 **Code** 403 404 ``` 405 #include <bits/stdc++.h> 406 using namespace std; 407 408 using ll = long long; 409 using ld = long double; 410 using pii = pair<int, int>; 411 using vi = vector<int>; 412 #define rep(i, a, b) for(int i = a; i < (b); ++i) 413 #define all(x) (x).begin(), (x).end() 414 #define sz(x) (int)(x).size() 415 #define smx(a, b) a = max(a, b) 416 #define smn(a, b) a = min(a, b) 417 #define pb push_back 418 #define endl '\n' 419 420 const ll MOD = 1e9 + 7; 421 const ld EPS = 1e-9; 422 423 mt19937 rng(time(0)); 424 425 const int LOG = 14; 426 const int MAX = 10000 + 1; 427 428 int main() { 429 cin.tie(0)->sync_with_stdio(0); 430 431 int t; cin >> t; 432 while (t--) { 433 int n, m; cin >> n >> m; 434 bitset<MAX> prev(1), pfx(1), zero(0); 435 list<pair<int, bitset<MAX>>> q; 436 rep(i,0,n) { 437 int x; cin >> x; 438 bitset<MAX> curr = zero; 439 440 if (x == 0) { 441 curr |= pfx; 442 zero = curr; 443 q.push_front({0, prev}); 444 } else if (x == 1) { 445 curr |= prev | (prev << 1); 446 } else { 447 int prod = 1; 448 q.push_front({x, prev}); 449 for (auto const& val : q) { 450 if (prod == 0 || prod * val.first > m) break; 451 prod *= val.first; 452 curr |= val.second << prod; 453 } 454 } 455 pfx |= curr; 456 prev = curr; 457 if (sz(q) > LOG) q.pop_back(); 458 } 459 460 cout << (prev[m] ? "YES" : "NO") << "\n"; 461 } 462 } 463 ```