1875.md (35813B)
1 Source: https://codeforces.com/blog/entry/120943 2 3 ## [1875A - Jellyfish and Undertale](/contest/1875/problem/A "Codeforces Round 901 (Div. 2)") 4 5 **Tutorial** 6 7 We can use one tool each time the timer reaches to $1$, then the answer will be $\sum_{i=1}^n \min(a - 1, x_i) + b$. This can prove to be optimal. Because for each tool, if we use it when the timer is $c$, its contribution to the answer is $\min(x_i, a - c)$. We can't use the tool when the timer is less than or equal to $0$ because the bomb will explode before that, so $c=1$ is the optimal. 8 9 Time complexity: $O(n)$ per test case. 10 11 Memory complexity: $O(1)$ per test case. 12 13 **Code** 14 15 ``` 16 #include<bits/stdc++.h> 17 18 using namespace std; 19 20 int n = 0, a = 0, b = 0; 21 long long ans = 0; 22 23 inline void solve(){ 24 scanf("%d %d %d", &a, &b, &n); 25 ans = b; 26 for(int i = 0, x = 0 ; i < n ; i ++){ 27 scanf("%d", &x); 28 ans += min(a - 1, x); 29 } 30 printf("%lld\n", ans); 31 } 32 33 int T = 0; 34 35 int main(){ 36 scanf("%d", &T); 37 for(int i = 0 ; i < T ; i ++) solve(); 38 return 0; 39 } 40 ``` 41 42 ## [1874A - Jellyfish and Game](/contest/1874/problem/A "Codeforces Round 901 (Div. 1)") 43 44 **Tutorial** 45 46 Let us define $\min(a)$ to be the minimum value of $a$ in the current round, $\max(a)$ to be the maximum value of $a$ in the current round, $\min(b)$ to be the minimum value of $b$ in the current round, $\max(b)$ to be the maximum value of $b$ in the current round, $\text{MIN}$ to be the minimum value of all the apples, $\text{MAX}$ to be the maximum value of all the apples. 47 48 By greedy and induction, we would come to the following conclusion: 49 50 * If Jellyfish is the one operating this round: If $\min(a) \lt \max(b)$, she will swap this two apples, otherwise she will do nothing. 51 * If Gellyfish is the one operating this round: If $\max(a) \gt \min(b)$, he will swap this two apples, otherwise she will do nothing. 52 53 We consider who $\text{MAX}$ and $\text{MIN}$ will belong to after the first round. 54 55 In the first round: 56 57 * If $\max(a) \lt \max(b)$, $\text{MAX} = \max(b)$. And because $\min(a) \lt \max(b)$, Jellyfish will swap this two apples. So $\text{MAX}$ belongs to Jellyfish. 58 * If $\max(a) \gt \max(b)$, $\text{MAX} = \max(a)$. If $\min(a)=\max(a)$, then $\min(a) \gt \max(b)$, Jellyfish will do nothing. Otherwise Jellyfish won't swap the apple with value $\text{MAX}$. In conclusion $\text{MAX}$ belongs to Jellyfish 59 60 We can also show that $\text{MIN}$ belongs to Gellyfish, and the proof is symmetric with the above. 61 62 So in the second round, $\min(b) = \text{MIN}, \max(a) = \text{MAX}$, We have $\text{MIN} \lt \text{MAX}$. So Gellyfish will swap this two apples, in the third round, $\min(a)=\text{MIN}, \max(b) = \text{MAX}$, Jellyfish will swap this two apples. 63 64 So after the first round, the game will go two rounds at a time, with two people swapping two apples with the minimum value and the maximum value back and forth. 65 66 So we only need to know the answer for $k = 1$ and $k = 2$. 67 68 Time complexity: $O(n + m)$ per test case. 69 70 Memory complexity: $O(n + m)$ per test case. 71 72 **Code** 73 74 ``` 75 #include<bits/stdc++.h> 76 77 using namespace std; 78 79 const int N = 1000 + 5; 80 int n = 0, m = 0, k = 0, x = 0, y = 0, a[N] = {}, b[N] = {}; 81 82 inline void solve(){ 83 scanf("%d %d %d", &n, &m, &k); k --; 84 for(int i = 0 ; i < n ; i ++) scanf("%d", &a[i]); 85 for(int i = 0 ; i < m ; i ++) scanf("%d", &b[i]); 86 x = y = 0; 87 for(int i = 1 ; i < n ; i ++) if(a[i] < a[x]) x = i; 88 for(int i = 1 ; i < m ; i ++) if(b[i] > b[y]) y = i; 89 if(b[y] > a[x]) swap(a[x], b[y]); 90 if(k & 1){ 91 x = 0, y = 0; 92 for(int i = 1 ; i < n ; i ++) if(a[i] > a[x]) x = i; 93 for(int i = 1 ; i < m ; i ++) if(b[i] < b[y]) y = i; 94 swap(a[x], b[y]); 95 } 96 long long ans = 0; 97 for(int i = 0 ; i < n ; i ++) ans += a[i]; 98 printf("%lld\n", ans); 99 100 } 101 102 int T = 0; 103 104 int main(){ 105 scanf("%d", &T); 106 for(int i = 0 ; i < T ; i ++) solve(); 107 return 0; 108 } 109 ``` 110 111 ## [1875C - Jellyfish and Green Apple](/contest/1875/problem/C "Codeforces Round 901 (Div. 2)") 112 113 **Tutorial** 114 115 Firstly, if $n \geq m$, we can make the problem transform $n \lt m$ by giving each person an apple at a time until there are not enough apples. 116 117 We can calculate the mass of apples that each person ends up with as $\frac n m$. 118 119 Since it's cut in half every time, if $\frac m {\gcd(n, m)}$ is not an integral power of $2$, there's no solution. 120 121 Since the number of apple pieces is added to exactly $1$ for each cut, So we just need to minimize the final number of apple pieces. 122 123 As the problem is transformed, $\frac n m$ is less than $1$, and $\frac m {\gcd(n, m)}$ is an integral power of $2$. So we can uniquely find a set of positive integers $S$ satisfying $\frac n m = \sum_{i \in S} \frac 1 {2^i}$. And this method can be proven to be optimal, if we find another multiset $T$ satisfying $S \neq T$, for every element $x$ that appears twice or more, We can make the answer better by removing two $x$ at a time from $T$ and adding one $x - 1$ to $T$. By repeating this process, eventually $T$ will become $S$. 124 125 We can use $\text{std::__builtin_popcount()}$ to get $|S|$, the answer is $m \times |S|-n$. 126 127 Time complexity: $O(\log m)$ per test case. 128 129 Memory complexity: $O(1)$ per test case. 130 131 **Code** 132 133 ``` 134 #include<bits/stdc++.h> 135 136 using namespace std; 137 138 int n = 0, m = 0; 139 140 inline void solve(){ 141 scanf("%d %d", &n, &m); n %= m; 142 int a = n / __gcd(n, m), b = m / __gcd(n, m); 143 if(__builtin_popcount(b) > 1) printf("-1\n"); 144 else printf("%lld\n", 1ll * __builtin_popcount(a) * m - n); 145 } 146 147 int T = 0; 148 149 int main(){ 150 scanf("%d", &T); 151 for(int i = 0 ; i < T ; i ++) solve(); 152 return 0; 153 } 154 ``` 155 156 ## [1875D - Jellyfish and Mex](/contest/1875/problem/D "Codeforces Round 901 (Div. 2)") 157 158 **Tutorial** 159 160 We only care about the operation before $\text{MEX}(a)$ reaches $0$, because after that, $m$ will never change. 161 162 **Lemma.** Before $\text{MEX}(a)$ reaches $0$, we will choose a positive integer $x$ at a time that satisfies $x \lt \text{MEX}(a)$, and delete all $x$ from $a$, the $\text{MEX}(a)$ will become $x$. 163 164 **Proof.** Because if $x \gt \text{MEX}(a)$, we can place this operation after the $\text{MEX}(a)$ becomes $0$, if we don't delete all of $x$, $\text{MEX}(a)$ won't change, we can also put this operation later. 165 166 So before $\text{MEX}(a)$ reaches $0$, the $x$ we delete is non-increasing. 167 168 It means we can solve this problem by dynamic programming. Let $dp_i$ represents when $\text{MEX}(a)=i$, and we haven't delete any $x$ satisfying $x \lt i$,the minimum value of $m$. 169 170 Let $c_i$ represents the number of times $i$ appears in $a$, the transition is: $\forall j \lt i, dp_j \leftarrow dp_i + i \times (c_j - 1) + j$. 171 172 Time complexity: $O(n^2)$ per test case. 173 174 Memory complexity: $O(n)$ per test case. 175 176 **Code** 177 178 ``` 179 #include<bits/stdc++.h> 180 181 using namespace std; 182 typedef long long ll; 183 184 const ll N = 5000 + 5, Inf = 0x3f3f3f3f3f3f3f3f; 185 ll n = 0, m = 0, a[N] = {}, dp[N] = {}; 186 187 inline void init(){ 188 for(ll i = 0 ; i <= n ; i ++) a[i] = 0, dp[i] = Inf; 189 n = m = 0; 190 } 191 192 inline void solve(){ 193 scanf("%lld", &n); 194 for(ll i = 1, x = 0 ; i <= n ; i ++){ 195 scanf("%lld", &x); 196 if(x < n) a[x] ++; 197 } 198 while(a[m]) m ++; 199 dp[m] = 0; 200 for(ll i = m ; i >= 1 ; i --) for(ll j = 0 ; j < i ; j ++) dp[j] = min(dp[j], dp[i] + i * a[j]); 201 printf("%lld\n", dp[0] - m); 202 } 203 204 ll T = 0; 205 206 int main(){ 207 memset(dp, 0x3f, sizeof(dp)); 208 scanf("%lld", &T); 209 for(ll i = 0 ; i < T ; i ++) init(), solve(); 210 return 0; 211 } 212 ``` 213 214 ## [1874B - Jellyfish and Math](/contest/1874/problem/B "Codeforces Round 901 (Div. 1)") 215 216 **Tutorial** 217 218 First of all, since $\text{and}, \text{or}, \text{xor}$ are all bitwise operations, each bit is independent of the other. 219 220 We define $a_i$ as the $i$-th bit of $a$, $b_i$ as the $i$-th bit of $b$, $c_i$ as the $i$-th bit of $c$, $d_i$ as the $i$-th bit of $d$, $m_i$ as the $i$-th bit of $m$, $x_i$ as the $i$-th bit of $x$, $y_i$ as the $i$-th bit of $y$. (in binary) 221 222 **Lemma.** For all $i \neq j$, if $(a_i, b_i, m_i) = (a_j, b_j, m_j)$ and $(c_i, d_i) \neq (c_j, d_j)$, the goal cannot be achieved. 223 224 **Proof.** Because after every operation we will have $(x_i, y_i) = (x_j, y_j)$, so we can't achieve he goal. 225 226 Since $(a_i, b_i, m_i)$ has only $2^3=8$ cases, and $(c_i, d_i)$ has only $2^2=4$ cases, and there are some $(0/1, 0/1, 0/1)$ that do not appear in $\{(a_i, b_i, m_i)\ |\ 0 \leq i \leq \log \max(a, b, c, d, m)\}$, so there are only $(4+1)^8 \lt 4\times 10^5$ cases in this problem. We can use BFS(breadth-first search) for preprocessing. 227 228 Time complexity: $O(5^8)$ for preprocessing and $O(\log \max(a, b, c, d, m))$ per test case. 229 230 Memory complexity: $O(5^8)$ for preprocessing and $O(1)$ per test case. 231 232 **Code** 233 234 ``` 235 #include<bits/stdc++.h> 236 237 using namespace std; 238 239 const int S = 4e5 + 5, Inf = 0x3f3f3f3f; 240 int pw5[10] = {}, dp[S] = {}; 241 queue<int> Q; 242 243 inline void checkmin(int &x, int y){ 244 if(y < x) x = y; 245 } 246 247 inline int w(int mask, int i){ 248 return (mask / pw5[i]) % 5; 249 } 250 251 inline int f(int a, int b, int m){ 252 return (a << 2) | (b << 1) | m; 253 } 254 255 inline int g(int c, int d){ 256 return (c << 1) | d; 257 } 258 259 inline int work(int mask, int opt){ 260 int ret = 0; 261 for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++){ 262 int x = w(mask, f(a, b, m)), c = x >> 1, d = x & 1; 263 if(opt == 1) c = c & d; 264 else if(opt == 2) c = c | d; 265 else if(opt == 3) d = c ^ d; 266 else d = m ^ d; 267 ret += pw5[f(a, b, m)] * g(c, d); 268 } 269 return ret; 270 } 271 272 inline void init(){ 273 pw5[0] = 1; 274 for(int i = 1 ; i <= 8 ; i ++) pw5[i] = pw5[i - 1] * 5; 275 memset(dp, 0x3f, sizeof(dp)); 276 int mask = 0; 277 for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++) mask += pw5[f(a, b, m)] * g(a, b); 278 dp[mask] = 0, Q.push(mask); 279 while(Q.size()){ 280 int s = Q.front(); Q.pop(); 281 for(int opt = 0 ; opt < 4 ; opt ++){ 282 int t = work(s, opt); 283 if(dp[t] == Inf) dp[t] = dp[s] + 1, Q.push(t); 284 } 285 } 286 for(int mask = 0 ; mask < pw5[8] ; mask ++) for(int i = 0 ; i < 8 ; i ++) if(w(mask, i) == 4){ 287 for(int x = 1 ; x <= 4 ; x ++) checkmin(dp[mask], dp[mask - x * pw5[i]]); 288 break; 289 } 290 } 291 292 inline void solve(){ 293 int A = 0, B = 0, C = 0, D = 0, M = 0, mask = pw5[8] - 1; 294 scanf("%d %d %d %d %d", &A, &B, &C, &D, &M); 295 for(int i = 0 ; i < 30 ; i ++){ 296 int a = (A >> i) & 1, b = (B >> i) & 1, c = (C >> i) & 1, d = (D >> i) & 1, m = (M >> i) & 1; 297 if(w(mask, f(a, b, m)) == 4) mask -= (4 - g(c, d)) * pw5[f(a, b, m)]; 298 else if(w(mask, f(a, b, m)) != g(c, d)){ 299 printf("-1\n"); 300 return; 301 } 302 } 303 printf("%d\n", (dp[mask] < Inf) ? dp[mask] : -1); 304 } 305 306 int T = 0; 307 308 int main(){ 309 init(); 310 scanf("%d", &T); 311 for(int i = 0 ; i < T ; i ++) solve(); 312 return 0; 313 } 314 ``` 315 316 ## [1874C - Jellyfish and EVA](/contest/1874/problem/C "Codeforces Round 901 (Div. 1)") 317 318 **Tutorial** 319 320 Let's solve this problem by dynamic programming, Let $f_u$ represents the max probability of reaching city $n$ starting from city $u$. 321 322 The problem is how to transition. for city $u$, we assume that there are $d$ roads from city $u$, the $i$-th road from city $u$ is to city $v_i$. 323 324 Let's sort $v$ by using $f_v$ as the keyword, with $v$ with the larger $f_v$ coming first. 325 326 Let's define an array $a$ of $d$ elements equals to $[f_{v_1}, f_{v_2}, \dots, f_{v_d}]$, according to the definition, $a$ is non-increasing. 327 328 That is, next we want to find an optimal solution such that the probability of going to city $v_i$ is $p_i$, maximizing the value of $\sum_{i=1}^d{a_i \times p_i}$. 329 330 **Tips:** the sum of $p_i$ may not be $1$, because it is possible to stay at city $u$ when $d$ is even. 331 332 For two choices of $p$, $p_1$ and $p_2$, Sometimes we can't which is better, for example: 333 334 $p_1 = [0.6, 0.2, 0.2], p_2 = [0.5, 0.5, 0]$ 335 336 when $a=[1.0, 0.2, 0.2]$, $p_1$ is better than $p_2$. But when $a = [1.0, 0.8, 0]$, $p_2$ is better than $p_1$. 337 338 **Tips.** In fact, when $d=3$, $p$ has only one choice $[\frac 1 3, \frac 1 3, \frac 1 3]$, the above is just a hypothetical to illustrate the problem. 339 340 So when can we say, $p_1$ is always not worse than $p_2$? 341 342 **Lemma.** If there are two arrays $p_1$ and $p_2$, satisfying $\forall i \leq d, \sum_{j=1}^i{p_1}_j \geq \sum_{j=1}^i{p_2}_j$, $p_1$ is always not worse than $p_2$. 343 344 **Proof.** Let's consider $a_{d+1}$ as $0$ and define $a'_i = a_i - a_{i+1}$, ${p_1'}_i = \sum_{j=1}^i{p_1}_j$ and ${p_2'}_i = \sum_{j=1}^i{p_2}_j$, then $\sum_{i=1}^d a_i \times {p_1}_i = \sum_{i=1}^d a'_i \times {p_1'}_i, \sum_{i=1}^d a_i \times {p_2}_i = \sum_{i=1}^d a'_i \times {p_2'}_i$, Because $a$ is non-increasing, so $a'_i \geq 0$, and we have $\forall i \leq d, {p_1}_i \geq {p_2}_i$, so $\sum_{i=1}^d a_i \times {p_1}_i \geq \sum_{i=1}^d a_i \times {p_2}_i$. 345 346 Now the problem is, there is whether an array $p$ not worse than any other arrays for for all $d$. 347 348 For $d = 1$, $p = [1.0]$ satisfies the condition. 349 350 For $d = 2$, $p = [0.5, 0]$ satisfies the condition. 351 352 What about $d \gt 2$ ? After they choose the roads for the first time, The size of the problem will become $d - 2$. 353 354 For example, when $d = 4$, Let's assume Jellyfish choose $v_1$ for the first time, then there will be $4$ situations: 355 356 1. When Asuka chooses $v_1$ they will go to $v_1$. 357 2. When Asuka chooses $v_2$, the problem changes into the subproblem with $[v_3, v_4]$. 358 3. When Asuka chooses $v_3$, the problem changes into the subproblem with $[v_2, v_4]$. 359 4. When Asuka chooses $v_4$, the problem changes into the subproblem with $[v_2, v_3]$. 360 361 By calculating, $p = [0.25, 0.25, 0.125, 0]$, it also satisfies the condition. 362 363 Let's define $g_k$ as the best array $p$ when $d=k$, $g'_k$ as the the probabilities of going to cities except the city Jellyfish choose for the first time. By recursion, we can get $g'_k$ from $g_{k-2}$. After that, we insert $\frac 1 k$ into $g'_k$, keeping it non-increasing, we will get $g_k$. 364 365 By calculating, we will find $\frac 1 k$ is always the first element in $g_k$. So when $k \gt 2$, we have the following transition: 366 367 * $g_{k, 1} = \frac 1 k$ 368 * $\forall 1 \lt i \leq k, g_{k, i} = g_{k-2, i - 2} \times \frac {i - 2} k + g_{k-2, i - 1} \times \frac {k - i} k$ 369 370 In the above we consider $g_{k, x}$ as $0$ for all $x = 0$ or $x \gt k$. 371 372 Because $g_{k-2}$ satisfies the condition, by greedy and induction we can show that $g_k$ satisfies the condition. 373 374 Time complexity: $O(\max(n)^2)$ for preprocessing and $O(m \log n)$ per test case. 375 376 Memory complexity: $O(\max(n)^2)$ for preprocessing and $O(m)$ per test case. 377 378 **Code** 379 380 ``` 381 #include<bits/stdc++.h> 382 383 using namespace std; 384 385 const int N = 5000 + 5; 386 int n = 5000, m = 0; 387 vector<vector<int> > G(N), Gx(N); 388 long double f[N] = {}, g[N][N] = {}; 389 390 inline bool cmp(int u, int v){ 391 return f[u] > f[v]; 392 } 393 394 inline void work(int u){ 395 if(u == n){ 396 f[u] = 1.00; 397 return; 398 } 399 sort(G[u].begin(), G[u].end(), cmp); 400 int k = G[u].size(); 401 for(int i = 0 ; i < k ; i ++){ 402 int v = G[u][i]; 403 f[u] += f[v] * g[k][i + 1]; 404 } 405 } 406 407 inline void init(){ 408 for(int u = 1 ; u <= n ; u ++){ 409 f[u] = 0.00; 410 G[u].clear(), Gx[u].clear(); 411 } 412 n = m = 0; 413 } 414 415 inline void solve(){ 416 scanf("%d %d", &n, &m); 417 for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){ 418 scanf("%d %d", &u, &v); 419 if(u != n){ 420 G[u].push_back(v); 421 Gx[v].push_back(u); 422 } 423 } 424 for(int u = n ; u >= 1 ; u --) work(u); 425 printf("%.12Lf\n", f[1]); 426 } 427 428 int T = 0; 429 430 int main(){ 431 for(int i = 1 ; i <= n ; i += 2) for(int j = 1 ; j <= i ; j ++) g[i][j] = 1.00 / i; 432 for(int i = 2 ; i <= n ; i += 2){ 433 g[i][1] = 1.00; 434 for(int j = 1 ; j <= i ; j ++) g[i][j] /= i; 435 if(i + 2 <= n) for(int j = 1 ; j <= i ; j ++) g[i + 2][j + 1] += g[i][j] * (i - j + 1), g[i + 2][j + 2] += g[i][j] * j; 436 } 437 scanf("%d", &T); 438 for(int i = 1 ; i <= T ; i ++) init(), solve(); 439 return 0; 440 } 441 ``` 442 443 ## [1874D - Jellyfish and Miku](/contest/1874/problem/D "Codeforces Round 901 (Div. 1)") 444 445 **Tutorial** 446 447 Let's assume that $a$ is given. We can use dynamic programming to solve the problem. 448 449 Let's define $f_i$ as the expected number of days Jellyfish needs to reach city $i$ from city $0$. 450 451 We will have: 452 453 * $f_0=0, f_1=1$ 454 * $\forall i \gt 1, f_i=f_{i-1}+1+\frac {a_{i-1}} {a_{i-1}+a_i} \times (f_i - f_{i-2})$ 455 456 Let's make it better: 457 458 * $f_i = f_{i-1} + 1 + \frac {a_{i-1}} {a_i} \times (f_{i-1}-f_{i-2}+1)$ 459 460 What does this inspire us to do? Let's define $g_i=f_i-f_{i-1}$, then we will get: 461 462 * $g_1=1$ 463 * $\forall i \gt 1, g_i = 1 + \frac {a_{i-1}} {a_i} \times (g_{i-1}+1)$ 464 465 By induction, we will find $g_i = 1 + 2 \times \sum_{j=1}^{i-1} \frac {a_j} {a_i}$. According to the definition, $f_n = \sum_{i=1}^n g_n = n + 2 \times \sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$. 466 467 Then we can use dynamic programming to solve the problem itself. 468 469 Let's define $s_i = \sum_{j=1}^i a_j$, then $f_n = n + 2 \times \sum_{i=1}^n \frac{s_{i-1}}{a_i}$. 470 471 Let's define $dp_{i, x}$ as the minimum value of $\sum_{i=1}^n \frac{s_{i-1}}{a_i}$ when $s_i = x$. 472 473 We transit by enumerating the values of $a_{i+1}$, The transition is: $dp_{i+1, x+y} \leftarrow dp_{i, x} + \frac x y$. 474 475 But the time complexity is $O(n m^2)$, how can it becomes faster? 476 477 Let's take a closer look at $\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$. If there exists $i \lt n$ satisfying $a_i \gt a_{i+1}$. We can swap $a_i$ and $a_{i+1}$, the answer will be better! so $a$ is a non-decreasing array, which means $a_i \leq \frac m {n - i + 1}$. 478 479 Because $\sum_{i=1}^n \frac n i$ is $O(n \log n)$, so if we only enumerate the possible values of $a_i$ the time complexity will be $O(m^2 \log m)$. 480 481 Time complexity: $O(m^2 \log m)$ 482 483 Memory complexity: $O(nm)$ 484 485 **Code** 486 487 ``` 488 #include<bits/stdc++.h> 489 490 using namespace std; 491 492 const int N = 3000 + 5; 493 const long double Inf = 1e18; 494 int n = 0, m = 0; 495 long double dp[N][N] = {}; 496 497 int main(){ 498 scanf("%d %d", &n, &m); 499 for(int i = 0 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) dp[i][x] = Inf; 500 dp[0][0] = 0.00; 501 for(int i = 1 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) for(int y = 1 ; x + y * (n - i + 1) <= m ; y ++) dp[i][x + y] = min(dp[i][x + y], dp[i - 1][x] + 1.00 * x / y); 502 printf("%.12Lf", 2 * dp[n][m] + n); 503 return 0; 504 } 505 ``` 506 507 ## [1874E - Jellyfish and Hack](/contest/1874/problem/E "Codeforces Round 901 (Div. 1)") 508 509 **Tutorial** 510 511 Firstly, if $lim \gt \frac {n(n+1)} 2$, the answer will be $0$. So we only need to solve the problem which satisfies $lim \leq \frac{n(n+1)} 2$. 512 513 We can use dynamic programming to solve the problem: 514 515 Let's define $dp_{i, a}$ means the number of the permutations $P$ of $[1, 2, \dots, i]$, satisfying $\mathrm{fun(P)} = a$. 516 517 Since only relative rankings are useful, we have the following transition: 518 519 * $dp_{0, 0} = 1$ 520 * $\forall i \gt 0, dp_{i, a} = \sum_{j=1}^i \binom {i-1} {j-1} \sum_{b=0}^{a - i} dp_{j - 1, b} \times dp_{i - j, a - b - i}$ 521 522 The time complexity is $O(n^6)$, because $a \leq \frac {i(i+1)} 2$, how can it becomes faster? 523 524 FFT (Fast Fourier Transform) might come to mind first. If we use FFT instead of enumerating $t$, The time complexity will become $O(n^4 \log n)$. This is not enough because $n$ is large and $10^9+7$ is not a modulus suitable for NTT (Number-theoretic Transform). 525 526 **Tips.** Also, if you use divide and conquer and FFT, The time complexity will be $O(n^3 \text{poly}(\log n))$, but because FFT have a big constant factor, this still can't pass the problem. 527 528 But we can do something similar to what the FFT does. We define $F_i = \sum_{a=1}^{\frac {n(n + 1)} 2} dp_{i, a} \times x^a$, then we will have the following transition: 529 530 * $F_0=1$ 531 * $F_i = x^i \times \sum_{j=1}^i \binom{i - 1}{j - 1} F_{j-1} \times F_{i-j}$ 532 533 For all $1 \leq i \leq n$, The degree of $F_i$ won't exceed $\frac {n(n+1)} 2$. So if we have $\frac{n(n+1)} 2 + 1$ points on $F_n$, We can get $F_n$ by in time complexity $O(n^4)$ using Lagrange Interpolation. The only thing we need to do is the dot product of the functions, so the time complexity of the transition is also $O(n^4)$. 534 535 Time complexity: $O(n^4)$ 536 537 Memory complexity: $O(n^3)$ 538 539 **Code** 540 541 ``` 542 #include<bits/stdc++.h> 543 544 using namespace std; 545 typedef long long ll; 546 547 const ll N = 200 + 5, Mod = 1e9 + 7; 548 549 inline ll power(ll x, ll y){ 550 ll ret = 1; 551 while(y){ 552 if(y & 1) ret = ret * x % Mod; 553 x = x * x % Mod, y >>= 1; 554 } 555 return ret; 556 } 557 558 ll n = 0, k = 0, lim = 0; 559 ll C[N][N] = {}, pw[N * N][N] = {}, iv[N * N] = {}, ifac[N * N] = {}, dp[N][N * N] = {}; 560 ll a[N * N] = {}, b[N * N] = {}, ans = 0; 561 562 int main(){ 563 scanf("%lld %lld", &n, &k); lim = n * (n + 1) / 2; 564 for(ll i = 0 ; i <= n ; i ++){ 565 C[i][0] = 1; 566 for(ll j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod; 567 } 568 ifac[0] = 1; 569 for(ll x = 0 ; x <= lim ; x ++){ 570 pw[x][0] = 1; 571 if(x) iv[x] = power(x, Mod - 2), ifac[x] = ifac[x - 1] * iv[x] % Mod; 572 for(ll i = 1 ; i <= n ; i ++) pw[x][i] = pw[x][i - 1] * x % Mod; 573 } 574 for(ll x = 0 ; x <= lim ; x ++) dp[0][x] = 1; 575 for(ll i = 1 ; i <= n ; i ++){ 576 for(ll j = 0 ; j < i ; j ++) for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = (dp[i][x] + dp[j][x] * dp[i - 1 - j][x] % Mod * C[i - 1][j]) % Mod; 577 for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = dp[i][x] * pw[x][i] % Mod; 578 } 579 a[0] = 1; 580 for(ll i = 0 ; i <= lim ; i ++){ 581 for(ll x = lim ; x >= 1 ; x --) a[x] = (a[x - 1] + a[x] * (Mod - i)) % Mod; 582 a[0] = a[0] * (Mod - i) % Mod; 583 } 584 for(ll i = 1 ; i <= lim ; i ++) if(dp[n][i]){ 585 ll w = dp[n][i] * ifac[i] % Mod * ifac[lim - i] % Mod; 586 if((lim - i) & 1) w = Mod - w; 587 b[0] = a[0] * (Mod - iv[i]) % Mod; 588 for(ll x = 1 ; x <= lim ; x ++) b[x] = (a[x] - b[x - 1] + Mod) * (Mod - iv[i]) % Mod; 589 for(ll x = k ; x <= lim ; x ++) ans = (ans + b[x] * w) % Mod; 590 } 591 printf("%lld\n", ans); 592 return 0; 593 } 594 ``` 595 596 ## [1874F - Jellyfish and OEIS](/contest/1874/problem/F "Codeforces Round 901 (Div. 1)") 597 598 **Tutorial** 599 600 Let's call a section $[l, r]$ bad if $[p_l, p_{l+1}, \dots, p_{r-1}, p_r]$ is a permutation of $[l, l + 1, \dots, r - 1, r]$ and $l \leq r \leq m_l$. 601 602 Let's call a section $[l, r]$ primitive if it's a bad section and there are no section $[l', r']$ satisfying $[l', r']$ is also a bad section and $[l, r]$ covers $[l', r']$. 603 604 **Lemma.** For all primitive sections, none two of them intersect. 605 606 **Proof.** If $[l_1, r_1]$ is a bad section, $[l_2, r_2]$ is a bad section and $l_1 \lt l_2 \lt r_1 \lt r_2$, the section $[l_2, r_1]$ will also be a bad section, but both $[l_1, r_1]$ and $[l_2, r_2]$ covers $[l_2, r_1]$, so $[l_1, r_1]$ and $[l_2, r_2]$ can't be primitive at the same time. 607 608 Let's use the principle of inclusion-exclusion and dynamic programming to solve the problem. 609 610 Let's define $f(l, r)$ as the number of $p_l, p_{l+1}, \dots, p_{r-1}, p_r$ which is a primitive section. By the principle of inclusion-exclusion, we count the ways to fix $k$ primitive sections in range $[l, r]$, and arrange the rest arbitrarily. 611 612 Then we can define $g_{1/2}(l, r, x)$ as the number of ways to fix $k$ ($k$ is odd/even) primitive sections in range $[l, r]$, and the number of the positions which doesn't cover by any primitive section is $x$. 613 614 Finally we define $g(l, r, x) = g_2(l, r, x) - g_1(l, r, x)$, We will have the following transition: 615 616 * $\forall l \leq r \leq m_l, f(l, r) = \sum_{x=0}^{r-l+1} g(l, r, x) \times x! + f(l, r)$ 617 * $g(l, r, x) = g(l, r - 1, x - 1) - \sum_{mid=l}^r g(l, mid - 1, x )\times f(mid, r)$ 618 619 **Tips.** In the transition of $f(l, r)$, We add $f(l, r)$ because $f(l, r)$ contributes to $g(l, r, 0)$, but it should not contribute to $f(l, r)$, This problem can be solved by ordering the transitions. 620 621 According to the definition, $\sum_{x=0}^{n} g(1, n, x) \times x!$ is the answer. 622 623 Time complexity: $O(n^4)$ 624 625 Memory complexity: $O(n^3)$ 626 627 **Code** 628 629 ``` 630 #include<bits/stdc++.h> 631 632 using namespace std; 633 typedef long long ll; 634 635 const ll N = 200 + 5, Mod = 1e9 + 7; 636 ll n = 0, m[N] = {}, fac[N] = {}, f[N][N] = {}, g[N][N][N] = {}; 637 638 int main(){ 639 scanf("%lld", &n); 640 for(ll i = 1 ; i <= n ; i ++) scanf("%lld", &m[i]); 641 if(m[1] == n){ 642 printf("0"); 643 return 0; 644 } 645 fac[0] = 1; 646 for(ll i = 1 ; i <= n ; i ++) fac[i] = fac[i - 1] * i % Mod; 647 for(ll i = 1 ; i <= n ; i ++) g[i][i - 1][0] = 1; 648 for(ll l = n ; l >= 1 ; l --) for(ll r = l ; r <= n ; r ++){ 649 for(ll x = 1 ; x <= r - l + 1 ; x ++) g[l][r][x] = g[l][r - 1][x - 1]; 650 for(ll mid = l ; mid < r ; mid ++) if(r <= m[mid + 1]) for(ll x = 0 ; x <= mid - l + 1 ; x ++) g[l][r][x] = (g[l][r][x] + g[l][mid][x] * (Mod - f[mid + 1][r])) % Mod; 651 for(ll x = 0 ; x <= r - l + 1 ; x ++) f[l][r] = (f[l][r] + g[l][r][x] * fac[x]) % Mod; 652 if(r <= m[l]) g[l][r][0] = (g[l][r][0] + (Mod - f[l][r])) % Mod; 653 } 654 printf("%lld", f[1][n]); 655 return 0; 656 } 657 ``` 658 659 ## [1874G - Jellyfish and Inscryption](/contest/1874/problem/G "Codeforces Round 901 (Div. 1)") 660 661 **Tutorial** 662 663 For convenience, let's define $k = \max(a, b, x, y)$, use operation 1 for "You will get a card with $a$ HP, and $b$ damage", operation 2 for "If you have at least one card, choose one of your cards and increase its HP by $x$" and operation 3 for "If you have at least one card, choose one of your cards and increase its damage by $y$", operation 4 for "You will get a prop with $w$ power", operation 5 for "You can choose at most one of your cards and multiply its damage by $10^9$", "the $i$-th card" for the card we get from vertex $i$ (It must be operation 1 on vertex $i$), "do operation 2/3/5 onto card $i$" for "When we do this operation 2/3/5, we will choose the card $i$ and increase his HP or damage". 664 665 Let us consider the problem without the operation 5, what's the maximum possible answer. If you want to maximize the the sum of the power of your cards, the answer will not exceeding $(100 \times 200)^2 = 4 \times 10^8$; If you you want to maximize the the sum of the power of your props, the answer will not exceeding $200 \times 10^6 = 2 \times 10^8$. Because $4 \times 10^8 + 2 \times 10^8 = 6 \times 10^8 \lt 10^9$, so the operation $n$ is the most important. Let's called the card we wil do the operation 5 onto it the "flash card". Let's use meet-in-the-middle, the problem is divided into two subproblems — the game before we get the flash card and the game after we get the flash card. 666 667 ### 1. The game after we get the flash card 668 669 It's a easy problem, we can use dynamic programming to solve this problem. 670 671 Since the most important thing is the HP and damage of the flash card, so we define the following dynamic programming state: 672 673 * $dp_b(u, a)$ means we are current at vertex $u$, the current HP of the flash card is $a$, the maximum damage of the flash card. 674 * $dp_c(u, a)$ means we are current at vertex $u$, the current HP of the flash card is $a$, the damage of the flash card is $dp_b(u, a)$, the maximum sum of the power of all the other cards and props. 675 676 Since $a \leq nk$, the time complexity of the transition is $O(m \times n \times k)$. 677 678 ### 2. The game before we get the flash card 679 680 This is the key of the problem, and since it's much more difficult, we first consider the subproblems of this problem. 681 682 #### I. If the graph is a chain, and all the operation 2 and operation 3 is after the operation 1 683 684 **Lemma.** We will do all the operation 2 onto one of the cards, symmetrically we will also do all the operation 3 onto one of the cards. 685 686 **Proof.** We consider a sequence of operations, let's consider if we do all the operation 1 on the card with the max damage after doing all the operation 2, the answer won't be worse, we can do all the operation 1 onto this card instead, then we make a symmetrical adjustment, the answer won't be worse, and all the operation 2 is done onto one of the cards, all the operation 3 is done onto one of the cards. 687 688 #### II. If the graph is a chain 689 690 It's similar to the **subproblem I**. If we say **subproblem I** is like a "global max value", then **subproblem II** is like a "prefix max value". 691 692 Let's define $p_i$ means we will do the operation 2/3 on vertex $i$ onto the $p_i$-th card. 693 694 **Lemma1.** If there is a operation 2 on vertex $i$ and a operation 2 on vertex $j$, if $p_i \lt j \lt i$, we will have $p_j = p_i$. 695 696 **Proof.** Let's consider the final HP and damage of the cards after all the operations. Because we do the operation 2 on vertex $i$ onto the $p_i$-th card, for all $i' \lt i$, the damage of the $i'$-th card is not larger than the $p_i$-th card. So for $j$, if we don't do the operation 2 on vertex j onto the $p_i$-th card, we can do it onto the $p_i$-th card instead, the answer won't be worse. 697 698 Symmetrically, **Lemma1** is also correct for operation 3. 699 700 Now we can use dynamic programming to solve the problem, we define the following dynamic programming state: 701 702 * $f(u, a, b)$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations and we will do the next several operation 2 onto a card with $b$ damage after all the operations, and this two cards are not the same. 703 * $g(u, a, b)$ means we are current at vertex $u$, We will do the next several operation 2 and operation 3 onto a card currently having $a$ HP and $b$ damage. 704 705 The time complexity is $O(m \times n^2 \times k^2)$, but it's not enough. 706 707 **Lemma2.** If a card has $a$ HP and $b$ damage after all the operations and it's not the flash card, $\min(a, b) \leq k$. 708 709 **Proof.** If we use this card as the flash card instead of the last one, and do all the operations done onto the last flash card onto this card, the power of the flash card will be larger. So it won't exist in this half problem. 710 711 Now the time complexity becomes $O(m \times n \times k^2)$, it's still not enough. 712 713 **Lemma3.** Let's define $A$ as the maximum HP of all the cards except the flash card after all the operations, $B$ as the maximum damage of all the cards except the flash card after all the operations, $\min(A, B) \leq k$. 714 715 **Proof.** Let's assume that the $i$-th card has $A$ HP after all the operations, the $j$-th card has $B$ damage after all the operations and $A \gt k, B \gt k$. If $i = j$, it conflicts with **Lemma 2**; If $i \lt j$, because of the **Lemma 2**, the HP of the $j$-th card after all the operations won't exceed $k$, let's use $A'$ as the HP of the $j$-th card after all the operations, and $B \gt k$, so we have done some operation 3 onto the $j$-th card. But because $A \gt k \geq A'$, if we do these operations onto the $i$-th card, the answer will be better; If $i \gt j$, it's symmetric with $i \lt j$. 716 717 But we can make the dynamic programming state better: 718 719 * $f(u, a, b)$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations and we will do the next several operation 2 onto a card with $b$ damage after all the operations, and this two cards are not the same. 720 * $g_a(u, a, a')$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations, we will do the next several operation 2 onto a card and totally increase $a'$ HP in the next several operations to reach it's HP after all the operations. 721 * $g_b(u, b, b')$ it's symmetric with $g_a$, just swap "HP" and "damage". 722 723 Let's define $A$ as the maximum HP of all the cards except the flash card after all the operations, $B$ as the maximum damage of all the cards except the flash card after all the operations. We will find the $a, a', b, b'$ in $f, g_a, g_b$ is $O(k)$ because if $A \leq k$, using $g_a$ we can get the right answer, if $B \leq k$, using $g_b$ we can get the right answer. 724 725 the time complexity of the transition is $O(m \times k^2)$. 726 727 The transition is very complex, you can see more details in my code : ) 728 729 In my code, I use $g(u)$ to make the transition better. When $a'$ or $b'$ reaches $0$, we reaches the vertex $u$ and there is a operation 1 on vertex $u$, I don't enumerate the value of the next $a$ and $b$ while transiting. I transit it to $g(u)$ first, and enumerate the value of the next $a$ and $b$ together. 730 731 #### III. the problem itself 732 733 Since the path is a chain, and we use dynamic programming to solve the problem. There's no difference whether the graph is a chain. 734 735 Time complexity: $O(m(nk+k^2))$ 736 737 Memory complexity: $O(n^2k+nk^2)$ 738 739 **Code** 740 741 ``` 742 #include<bits/stdc++.h> 743 744 using namespace std; 745 typedef long long ll; 746 747 const int N = 200 + 5; 748 const ll lim = 1e9; 749 750 inline void checkmax(int &x, int y){ 751 if(y > x) x = y; 752 } 753 754 inline void checkmax(ll &x, ll y){ 755 if(y > x) x = y; 756 } 757 758 inline void checkmax(pair<int, int> &x, pair<int, int> y){ 759 if(y > x) x = y; 760 } 761 762 int n = 0, m = 0, k = 0, opt[N] = {}, a[N] = {}, b[N] = {}, w[N] = {}; 763 int f[N][N][N] = {}, g[N] = {}, g_a[N][N][N] = {}, g_b[N][N][N] = {}; 764 pair<int, int> dp[N][N * N] = {}; 765 vector<vector<int> > G(N); 766 767 int main(){ 768 scanf("%d %d", &n, &m); 769 for(int u = 1 ; u <= n ; u ++){ 770 scanf("%d", &opt[u]); 771 if(opt[u] == 1) scanf("%d %d", &a[u], &b[u]); 772 else if(opt[u] == 2) scanf("%d", &a[u]); 773 else if(opt[u] == 3) scanf("%d", &b[u]); 774 else if(opt[u] == 4) scanf("%d", &w[u]); 775 k = max(k, max(a[u], b[u])); 776 } 777 for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){ 778 scanf("%d %d", &u, &v); 779 G[u].push_back(v); 780 } 781 memset(f, -1, sizeof(f)); 782 memset(g, -1, sizeof(g)), memset(g_a, -1, sizeof(g_a)), memset(g_b, -1, sizeof(g_b)); 783 memset(dp, -1, sizeof(dp)); 784 f[1][0][0] = 0; 785 for(int u = 1 ; u <= n ; u ++){ 786 if(opt[u] == 1 && g[u] != -1){ 787 for(int x = a[u] ; x <= k ; x ++) checkmax(g_a[u][x][x - a[u]], g[u] + x * b[u]); 788 for(int x = b[u] ; x <= k ; x ++) checkmax(g_b[u][x][x - b[u]], g[u] + x * a[u]); 789 checkmax(dp[u][a[u]], make_pair(b[u], g[u])); 790 } 791 for(int v : G[u]){ 792 if(opt[v] == 1){ 793 for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){ 794 if(f[u][x][y] != -1){ 795 checkmax(f[v][max(x, a[v])][max(y, b[v])], f[u][x][y] + a[v] * b[v]); 796 checkmax(g[v], f[u][x][y]); 797 } 798 if(g_a[u][x][y] != -1){ 799 checkmax(g_a[v][max(x, a[v])][y], g_a[u][x][y] + a[v] * b[v]); 800 if(!y){ 801 checkmax(g[v], g_a[u][x][y]); 802 checkmax(f[v][x][b[v]], g_a[u][x][y] + a[v] * b[v]); 803 } 804 } 805 if(g_b[u][x][y] != -1){ 806 checkmax(g_b[v][max(x, b[v])][y], g_b[u][x][y] + a[v] * b[v]); 807 if(!y){ 808 checkmax(g[v], g_b[u][x][y]); 809 checkmax(f[v][a[v]][x], g_b[u][x][y] + a[v] * b[v]); 810 } 811 } 812 } 813 for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){ 814 int y = dp[u][x].first, z = dp[u][x].second; 815 checkmax(dp[v][x], make_pair(y, z + a[v] * b[v])); 816 } 817 } 818 else if(opt[v] == 2){ 819 for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){ 820 if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + a[v] * y); 821 if(g_a[u][x][y] != -1 && y >= a[v]) checkmax(g_a[v][x][y - a[v]], g_a[u][x][y]); 822 if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y], g_b[u][x][y] + a[v] * x); 823 } 824 for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){ 825 int y = dp[u][x].first, z = dp[u][x].second; 826 checkmax(dp[v][x + a[v]], make_pair(y, z)); 827 } 828 } 829 else if(opt[v] == 3){ 830 for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){ 831 if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + x * b[v]); 832 if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + x * b[v]); 833 if(g_b[u][x][y] != -1 && y >= b[v]) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y]); 834 } 835 for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){ 836 int y = dp[u][x].first, z = dp[u][x].second; 837 checkmax(dp[v][x], make_pair(y + b[v], z)); 838 } 839 } 840 else{ 841 for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){ 842 if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + w[v]); 843 if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + w[v]); 844 if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y] + w[v]); 845 } 846 for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){ 847 int y = dp[u][x].first, z = dp[u][x].second; 848 checkmax(dp[v][x], make_pair(y, z + w[v])); 849 } 850 } 851 } 852 } 853 ll ans = f[n][0][0]; 854 for(int x = 0 ; x <= n * k ; x ++) if(dp[n][x] != make_pair(-1, -1)){ 855 int y = dp[n][x].first, z = dp[n][x].second; 856 checkmax(ans, lim * x * y + z); 857 } 858 printf("%lld", ans); 859 return 0; 860 } 861 ```