1606.md (8953B)
1 Source: https://codeforces.com/blog/entry/96454 2 3 [1606A - AB Balance](/contest/1606/problem/A "Educational Codeforces Round 116 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main() { 15 repeat(readLine()!!.toInt()) { 16 val s = readLine()!! 17 println(s.last() + s.substring(1)) 18 } 19 } 20 ``` 21 22 [1606B - Update Files](/contest/1606/problem/B "Educational Codeforces Round 116 (Rated for Div. 2)") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (Neon)** 29 30 ``` 31 #include <bits/stdc++.h> 32 33 using namespace std; 34 35 using li = long long; 36 37 int main() { 38 ios_base::sync_with_stdio(false); 39 cin.tie(NULL); 40 int t; 41 cin >> t; 42 while (t--) { 43 li n, k; 44 cin >> n >> k; 45 li ans = 0, cur = 1; 46 while (cur < k) { 47 cur *= 2; 48 ++ans; 49 } 50 if (cur < n) ans += (n - cur + k - 1) / k; 51 cout << ans << '\n'; 52 } 53 } 54 ``` 55 56 [1606C - Banknotes](/contest/1606/problem/C "Educational Codeforces Round 116 (Rated for Div. 2)") 57 58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 59 60 **Tutorial** 61 62 Tutorial is loading... 63 64 **Solution (Neon)** 65 66 ``` 67 #include <bits/stdc++.h> 68 69 using namespace std; 70 71 int main() { 72 int t; 73 cin >> t; 74 while (t--) { 75 int n, k; 76 cin >> n >> k; 77 k += 1; 78 vector<int> a(n); 79 for (int& x : a) { 80 cin >> x; 81 int cur = 1; 82 while (x--) cur *= 10; 83 x = cur; 84 } 85 long long res = 0; 86 for (int i = 0; i < n; i++) { 87 int cnt = k; 88 if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1); 89 res += a[i] * 1LL * cnt; 90 k -= cnt; 91 } 92 cout << res << '\n'; 93 } 94 } 95 ``` 96 97 [1606D - Red-Blue Matrix](/contest/1606/problem/D "Educational Codeforces Round 116 (Rated for Div. 2)") 98 99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (awoo)** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 #define forn(i, n) for (int i = 0; i < int(n); i++) 111 112 using namespace std; 113 114 const int INF = 1e9; 115 116 int main() { 117 int tc; 118 scanf("%d", &tc); 119 while (tc--){ 120 int n, m; 121 scanf("%d%d", &n, &m); 122 vector<vector<int>> a(n, vector<int>(m)); 123 forn(i, n) forn(j, m) scanf("%d", &a[i][j]); 124 vector<int> ord(n); 125 iota(ord.begin(), ord.end(), 0); 126 sort(ord.begin(), ord.end(), [&a](int x, int y){ return a[x][0] > a[y][0]; }); 127 vector<vector<int>> mxl(n, vector<int>(m, -INF)); 128 vector<vector<int>> mnr(n, vector<int>(m, INF)); 129 for (int i = n - 1; i >= 0; --i) forn(j, m){ 130 mxl[i][j] = a[ord[i]][j]; 131 if (i < n - 1) mxl[i][j] = max(mxl[i][j], mxl[i + 1][j]); 132 if (j > 0) mxl[i][j] = max(mxl[i][j], mxl[i][j - 1]); 133 } 134 for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j){ 135 mnr[i][j] = a[ord[i]][j]; 136 if (i < n - 1) mnr[i][j] = min(mnr[i][j], mnr[i + 1][j]); 137 if (j < m - 1) mnr[i][j] = min(mnr[i][j], mnr[i][j + 1]); 138 } 139 vector<int> mnl(m, INF), mxr(m, -INF); 140 pair<int, int> ans(-1, -1); 141 forn(i, n - 1){ 142 forn(j, m){ 143 mnl[j] = min(mnl[j], a[ord[i]][j]); 144 if (j > 0) mnl[j] = min(mnl[j], mnl[j - 1]); 145 } 146 for (int j = m - 1; j >= 0; --j){ 147 mxr[j] = max(mxr[j], a[ord[i]][j]); 148 if (j < m - 1) mxr[j] = max(mxr[j], mxr[j + 1]); 149 } 150 forn(j, m - 1) if (mnl[j] > mxl[i + 1][j] && mxr[j + 1] < mnr[i + 1][j + 1]){ 151 ans = {i, j}; 152 } 153 } 154 if (ans.first == -1){ 155 puts("NO"); 156 continue; 157 } 158 puts("YES"); 159 string res(n, '.'); 160 forn(i, n) res[ord[i]] = i <= ans.first ? 'R' : 'B'; 161 printf("%s %d\n", res.c_str(), ans.second + 1); 162 } 163 return 0; 164 } 165 ``` 166 167 [1606E - Arena](/contest/1606/problem/E "Educational Codeforces Round 116 (Rated for Div. 2)") 168 169 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 170 171 **Tutorial** 172 173 Tutorial is loading... 174 175 **Solution (Neon)** 176 177 ``` 178 #include <bits/stdc++.h> 179 180 using namespace std; 181 182 const int N = 505; 183 const int MOD = 998244353; 184 185 int n, x; 186 int c[N][N], dp[N][N]; 187 188 int add(int x, int y) { 189 x += y; 190 if (x >= MOD) x -= MOD; 191 return x; 192 } 193 194 int mul(int x, int y) { 195 return x * 1ll * y % MOD; 196 } 197 198 int main() { 199 cin >> n >> x; 200 for (int i = 0; i <= n; ++i) { 201 c[i][0] = c[i][i] = 1; 202 for (int j = 1; j < i; ++j) 203 c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]); 204 } 205 dp[n][0] = 1; 206 for (int i = n; i > 1; i--) { 207 for (int j = 0; j < x; ++j) { 208 if (!dp[i][j]) continue; 209 int pw = 1, nj = min(x, j + i - 1); 210 for (int k = i; k >= 0; k--) { 211 dp[k][nj] = add(dp[k][nj], mul(dp[i][j], mul(c[i][k], pw))); 212 pw = mul(pw, nj - j); 213 } 214 } 215 } 216 int ans = 0; 217 for (int i = 0; i <= x; ++i) 218 ans = add(ans, dp[0][i]); 219 cout << ans << endl; 220 } 221 ``` 222 223 [1606F - Tree Queries](/contest/1606/problem/F "Educational Codeforces Round 116 (Rated for Div. 2)") 224 225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution (BledDest)** 232 233 ``` 234 #include <bits/stdc++.h> 235 236 using namespace std; 237 238 struct Vertex 239 { 240 int cost; 241 int depth; 242 int idx; 243 Vertex() {}; 244 Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {}; 245 }; 246 247 bool operator <(const Vertex& a, const Vertex& b) 248 { 249 if(a.cost != b.cost) 250 return a.cost > b.cost; 251 if(a.depth != b.depth) 252 return a.depth > b.depth; 253 return a.idx < b.idx; 254 } 255 256 struct DSU 257 { 258 int n; 259 vector<int> p; 260 vector<int> top; 261 262 int get(int x) 263 { 264 if(p[x] == x) 265 return x; 266 return p[x] = get(p[x]); 267 } 268 269 int get_top(int x) 270 { 271 return top[get(x)]; 272 } 273 274 void merge(int x, int par) 275 { 276 p[x] = par; 277 } 278 279 DSU(int k = 0) 280 { 281 n = k; 282 p.resize(n); 283 iota(p.begin(), p.end(), 0); 284 top = p; 285 }; 286 }; 287 288 const int N = 200043; 289 290 int n; 291 vector<int> g[N]; 292 int p[N], d[N], tin[N], tout[N]; 293 int qv[N]; 294 int qk[N]; 295 int T = 0; 296 297 void dfs(int v = 0, int par = -1) 298 { 299 tin[v] = T++; 300 p[v] = par; 301 if(par == -1) 302 d[v] = 0; 303 else 304 d[v] = d[par] + 1; 305 for(auto x : g[v]) 306 if(x != par) 307 dfs(x, v); 308 tout[v] = T; 309 } 310 311 pair<long long, long long> tree[4 * N]; 312 313 pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b) 314 { 315 return make_pair(a.first + b.first, a.second + b.second); 316 } 317 318 pair<long long, long long> get(int v, int l, int r, int L, int R) 319 { 320 if(L >= R) return {0, 0}; 321 if(l == L && r == R) return tree[v]; 322 int m = (l + r) / 2; 323 return get(v * 2 + 1, l, m, L, min(R, m)) + get(v * 2 + 2, m, r, max(m, L), R); 324 } 325 326 void add(int v, int l, int r, int pos, pair<long long, long long> val) 327 { 328 if(l == r - 1) 329 tree[v] = tree[v] + val; 330 else 331 { 332 int m = (l + r) / 2; 333 if(pos < m) add(v * 2 + 1, l, m, pos, val); 334 else add(v * 2 + 2, m, r, pos, val); 335 tree[v] = tree[v] + val; 336 } 337 } 338 339 pair<long long, long long> get_vertex_value(int v) 340 { 341 return get(0, 0, n, tin[v], tout[v]); 342 } 343 344 void add_on_path(int x, int y, pair<long long, long long> val) 345 { 346 // x is a descendant of y 347 add(0, 0, n, tin[x], val); 348 if(p[y] != -1) 349 add(0, 0, n, tin[p[y]], make_pair(-val.first, -val.second)); 350 } 351 352 int calculate_cost(int v, int correction) 353 { 354 //cerr << v << " " << correction << endl; 355 pair<long long, long long> res = get_vertex_value(v); 356 // first - (second + 1) * k <= 0 357 long long k = (res.first + res.second) / (res.second + 1) - 1; 358 if(correction < k) return correction; 359 return k; 360 } 361 362 int main() 363 { 364 scanf("%d", &n); 365 for(int i = 1; i < n; i++) 366 { 367 int x, y; 368 scanf("%d %d", &x, &y); 369 --x; 370 --y; 371 g[x].push_back(y); 372 g[y].push_back(x); 373 } 374 int q; 375 scanf("%d", &q); 376 for(int i = 0; i < q; i++) 377 { 378 scanf("%d %d", &qv[i], &qk[i]); 379 --qv[i]; 380 } 381 382 dfs(); 383 DSU dsu(n); 384 385 vector<long long> ans(q); 386 set<Vertex> pq; 387 vector<Vertex> curv(n); 388 for(int i = 0; i < n; i++) 389 { 390 int count_children = g[i].size(); 391 if(i != 0) count_children--; 392 add_on_path(i, i, make_pair((long long)(count_children), 0ll)); 393 if(i != 0) 394 { 395 curv[i] = Vertex(calculate_cost(i, 200000), d[i], i); 396 pq.insert(curv[i]); 397 } 398 399 } 400 401 for(int i = 0; i < q; i++) 402 pq.insert(Vertex(qk[i], -1, i)); 403 404 while(!pq.empty()) 405 { 406 Vertex z = *pq.begin(); 407 pq.erase(pq.begin()); 408 if(z.depth == -1) 409 { 410 auto res = get_vertex_value(qv[z.idx]); 411 ans[z.idx] = res.first - res.second * z.cost; 412 } 413 else 414 { 415 int v = z.idx; 416 int pv = p[v]; 417 int newtop = dsu.get_top(pv); 418 pair<long long, long long> val = get_vertex_value(v); 419 val.second++; 420 val.first--; 421 if(newtop != 0) 422 pq.erase(curv[newtop]); 423 add_on_path(pv, newtop, val); 424 if(newtop != 0) 425 curv[newtop].cost = calculate_cost(newtop, z.cost); 426 if(newtop != 0) 427 pq.insert(curv[newtop]); 428 dsu.merge(v, pv); 429 } 430 } 431 432 for(int i = 0; i < q; i++) 433 printf("%lld\n", ans[i]); 434 } 435 ```