codeforces-scrape

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

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