1770.md (39749B)
1 Source: https://codeforces.com/blog/entry/110754 2 3 ## [1770A - Koxia and Whiteboards](/contest/1770/problem/A "Good Bye 2022: 2023 is NEAR") 4 5 Idea by [m_99](/profile/m_99 "International Grandmaster m_99") 6 7 **Hint 1** 8 9 Exactly $n$ items out of of $a_1,\ldots,a_n,b_1,\ldots,b_m$ will remain on the whiteboard at the end. 10 11 **Hint 2** 12 13 $b_m$ will always remain on the board at the end. 14 15 **Hint 3** 16 17 Consider the case where $n=2$ and $m=2$. As we mentioned in hint 2, $b_2$ will always be written, but what about $b_1$? 18 19 **Solution** 20 21 This problem can be solved naturally with a greedy algorithm — for $i = 1, 2, \dots, m$, we use $b_i$ to replace the minimal value among the current $a_1, a_2, \dots, a_n$. The time complexity is $O(nm)$ for each test case. 22 23 Alternatively, we can first add $b_m$ to our final sum. For the remaining $(n+m-1)$ integers, we can freely pick $(n - 1)$ out of them and add it to our final sum. This is because if we want a certain $a_i$ to remain on the board at the end, we simply do not touch it in the process. If we want a certain $b_i$ to remain on the board at the end, then on the $i^{th}$ operation we replace some $a_j$ that we do not want at the end by $b_i$. 24 25 Using an efficient sorting algorithm gives us a $O((n + m) \log (n + m))$ solution, which is our intended solution. 26 27 **Code (m_99)** 28 29 ``` 30 #include <stdio.h> 31 #include <bits/stdc++.h> 32 using namespace std; 33 #define rep(i,n) for (int i = 0; i < (n); ++i) 34 #define Inf32 1000000001 35 #define Inf64 4000000000000000001 36 37 int main(){ 38 39 int _t; 40 cin>>_t; 41 42 rep(_,_t){ 43 int n,m; 44 cin>>n>>m; 45 vector<long long> a(n+m); 46 rep(i,n+m)scanf("%lld",&a[i]); 47 48 sort(a.begin(),a.end()-1); 49 reverse(a.begin(),a.end()); 50 51 long long ans = 0; 52 rep(i,n)ans += a[i]; 53 54 cout<<ans<<endl; 55 } 56 57 58 return 0; 59 } 60 ``` 61 62 ## [1770B - Koxia and Permutation](/contest/1770/problem/B "Good Bye 2022: 2023 is NEAR") 63 64 Idea by [m_99](/profile/m_99 "International Grandmaster m_99") 65 66 **Hint 1** 67 68 For $k = 1$, the cost is always $2n$ for any permutation. 69 70 **Hint 2** 71 72 For $k \geq 2$, the minimal cost is always $n + 1$. 73 74 **Solution** 75 76 When $k = 1$ every permutation has the same cost. 77 78 When $k \geq 2$, the minimal cost will be at least $n+1$. This is because there will always be at least one segment containing the element $n$ in the permutation, contributing $n$ to the "max" part of the sum, and the "min" part will add at least $1$ to the sum. 79 80 In fact, the cost $n+1$ is optimal. It can be achieved by ordering the numbers in the pattern $[n, 1, n - 1, 2, n - 2, 3, n - 3, 4, \dots]$. 81 82 The time complexity is $O(n)$ for each test case. Other careful constructions should also get Accepted. 83 84 **Code (Nanako)** 85 86 ``` 87 #include <iostream> 88 #define MULTI int _T; cin >> _T; while(_T--) 89 using namespace std; 90 typedef long long ll; 91 92 int n, k; 93 94 int main () { 95 ios::sync_with_stdio(0); 96 cin.tie(0); 97 98 MULTI { 99 cin >> n >> k; 100 int l = 1, r = n, _ = 1; 101 while (l <= r) cout << ((_ ^= 1) ? l++ : r--) << ' '; 102 cout << endl; 103 } 104 } 105 ``` 106 107 ## [1770C - Koxia and Number Theory](/contest/1770/problem/C "Good Bye 2022: 2023 is NEAR") 108 109 Idea by [triple__a](/profile/triple__a "International Grandmaster triple__a") 110 111 **Hint 1** 112 113 If $a_i$ are not pairwise distinct we get a trivial NO. 114 115 **Hint 2** 116 117 If all $a_i$ are pairwise distinct, can you construct an example with $n = 4$ that gives an answer NO? 118 119 **Hint 3** 120 121 Perhaps you are thinking about properties such as parity? Try to generalize the idea. 122 123 **Hint 3.5** 124 125 Consider every prime. Consider Chinese Remainder Theorem. 126 127 **Hint 4** 128 129 How many primes should we check? Consider Pigeonhole Principle. 130 131 **Solution** 132 133 First, we should check whether the integers in $a$ are pairwise distinct, as $a_i + x \geq 2$ and $\gcd(t,t)=t$, which leads to a trivial NO. 134 135 Given an integer $x$, let's define $b_i := a_i + x$. The condition "$\gcd(b_i,b_j)=1$ for $1\le i \lt j \le n$" is equivalent to "every prime $p$ should divides at most one $b_i$". Given a prime $p$, how should we verify whether for every $x \gt 0$, $p$ divides at least two elements in $b$? 136 137 A small but guided sample is $a = [5, 6, 7, 8]$ with answer NO, because 138 139 * $\gcd(6 + x, 8 + x) \neq 1$ if $x \equiv 0 \pmod 2$, 140 * $\gcd(5 + x, 7 + x) \neq 1$ if $x \equiv 1 \pmod 2$. 141 142 That is, if we consider $[5, 6, 7, 8]$ modulo $2$, we obtain the multiset ${1, 0, 1, 0}$. Both $0$ and $1$ appeared twice, so for any choice of $x$, exactly two integers in $b$ will be divided by $2$. 143 144 This idea can be extended to larger primes. For a given prime $p$, let $cnt_j$ be the multiplicity of $j$ in the multiset $[ a_i \text{ mod } p, a_2 \text{ mod } p, \dots, a_n \text{ mod } p ]$. If $\min(\mathit{cnt}_0, \mathit{cnt}_1, \dots, \mathit{cnt}_{p-1}) \geq 2$, we output NO immediately. 145 146 While there are many primes up to ${10}^{18}$, we only need to check for the primes up to $\lfloor \frac{n}{2} \rfloor$. This is because $\min(\mathit{cnt}_0, \mathit{cnt}_1, \dots, \mathit{cnt}_{p-1}) \geq 2$ is impossible for greater primes according to Pigeonhole Principle. Since the number of primes up to $\lfloor \frac{n}{2} \rfloor$ is at most $O\left(\frac{n}{\log n} \right)$, the problem can be solved in time $O\left(\frac{n^2}{\log n} \right)$. 147 148 The reason that $\min(\mathit{cnt}) \geq 2$ is essential because for a prime $p$, if $a_u \equiv a_v \pmod p$, then it's necessary to have $(x + a_u) \not\equiv 0 \pmod p$, because $\gcd(x + a_u, x + a_v)$ will be divided by $p$ otherwise. So actually, $\mathit{cnt}_i \geq 2$ means $x \not\equiv (p-i) \pmod p$. If $\min(\mathit{cnt}) \lt 2$ holds for all primes, then we can list certain congruence equations and use [Chinese Reminder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to calculate a proper $x$; if there exists a prime that $\min(\mathit{cnt}) \geq 2$, then any choose of $x$ leads to the situation that $p$ appears twice. 149 150 **Code (Nanako)** 151 152 ``` 153 #include <iostream> 154 #include <algorithm> 155 #define MULTI int _T; cin >> _T; while(_T--) 156 using namespace std; 157 typedef long long ll; 158 159 const int N = 105; 160 const int INF = 0x3f3f3f3f; 161 template <typename T> bool chkmin (T &x, T y) {return y < x ? x = y, 1 : 0;} 162 template <typename T> bool chkmax (T &x, T y) {return y > x ? x = y, 1 : 0;} 163 164 int n; 165 ll a[N]; 166 167 int cnt[N]; 168 169 int main () { 170 ios::sync_with_stdio(0); 171 cin.tie(0); 172 173 MULTI { 174 cin >> n; 175 for (int i = 1;i <= n;++i) { 176 cin >> a[i]; 177 } 178 179 int isDistinct = 1; 180 sort(a + 1, a + n + 1); 181 for (int i = 1;i <= n - 1;++i) { 182 if (a[i] == a[i + 1]) isDistinct = 0; 183 } 184 if (isDistinct == 0) { 185 cout << "NO" << endl; 186 continue; 187 } 188 189 int CRT_able = 1; 190 for (int mod = 2;mod <= n / 2;++mod) { 191 fill(cnt, cnt + mod, 0); 192 for (int i = 1;i <= n;++i) { 193 cnt[a[i] % mod]++; 194 } 195 if (*min_element(cnt, cnt + mod) >= 2) CRT_able = 0; 196 } 197 cout << (CRT_able ? "YES" : "NO") << endl; 198 } 199 } 200 ``` 201 202 ## [1770D - Koxia and Game](/contest/1770/problem/D "Good Bye 2022: 2023 is NEAR") 203 204 Idea by [m_99](/profile/m_99 "International Grandmaster m_99") 205 206 **Hint 1** 207 208 If all of $a$, $b$ and $c$ are fixed, how to determine who will win? 209 210 **Hint 2** 211 212 If $a$ and $b$ are fixed, design an algorithm to check if there is an array $c$ that makes Koxia wins. 213 214 **Hint 2.5** 215 216 If you can't solve the problem in Hint 2, try to think about how it's related to graph theory. 217 218 **Hint 3** 219 220 Try to discuss the structure of components in the graph to count up the number of $c$. 221 222 **Solution** 223 224 Firstly, let's consider how an array $c$ could make Koxia wins. 225 226 **Lemma 1.** In each round, Koxia should remove an element in $S$ to make the remaining $2$ elements in $S$ the same (i.e. Mahiru's choice determined nothing actually). 227 228 * In round $n$, if Koxia leaves two choices for Mahiru then Mahiru will be able to prevent $d$ from being a permutation. 229 * This means if Koxia wins, there is only one choice for $d_n$. 230 * Now $(d_1, d_2, \dots, d_{n-1})$ have to be a permutation of a specific $n-1$ numbers. Apply the same argument on $d_{n-1}$ and so on, we can conclude that every $d_i$ only has one choice if Koxia wins. 231 232 **Lemma 2.** Let $p$ be array of length $n$ where we can set $p_i$ to either $a_i$ or $b_i$. Koxia wins iff there exists a way to make $p$ a permutation. 233 234 * According to Lemma 1, if there is a way to make $p$ a permutation, we can just set $c_i = p_i$. Koxia can then force Mahiru to set $d_i = p_i$ every round and Koxia will win. 235 * If it is impossible to make $p$ a permutation, Mahiru can pick either $a_i$ or $b_i$ (at least one of them is available) every round. The resulting array $d$ is guaranteed to not be a permutation. 236 237 First, we need an algorithm to determine if there is a way to make $p$ a permutation. 238 239 We can transform this into a graph problem where $(a_i, b_i)$ are edges in a graph with $n$ vertices. Then there is a way to make $p$ a permutation iff there is a way to assign a direction for every edge such that every vertex has one edge leading into it. It is not hard to see that this is equivalent to the condition that for every connected component, the number of edges equals the number of vertices. We can verify this by a Disjoint-Set Union or a graph traversal in $O(n \alpha(n))$ or $O(n)$ time complexity. 240 241 To solve the counting problem, we consider the structure of the connected components one by one. A component with $|V| = |E|$ can be viewed as a tree with an additional edge. This additional edge can be categorized into two cases: 242 243 * The additional edge forms a cycle together with some of the other edges. There are $2$ choices for the cycle (clockwise and counterclockwise), and the choices of other edges are fixed then (point away from the cycle). 244 * The additional edge forms a self-loop. Then the value of $c_i$ determines nothing in this situation so it can be any integers in $[1, n]$, and the choices of all other edges are fixed. 245 246 Therefore, if exists at least one $c$ to make Koxia wins, then the answer is $2^{\textrm{cycle component cnt}} \cdot n^{\textrm{self-loop component cnt}}$. The time complexity is $O(n \alpha(n))$ or $O(n)$. 247 248 **Code (Nanako, DSU)** 249 250 ``` 251 #include <iostream> 252 #include <numeric> 253 #define MULTI int _T; cin >> _T; while(_T--) 254 using namespace std; 255 typedef long long ll; 256 257 const int N = 1e5 + 5; 258 const int mod = 998244353; 259 260 int n; 261 int a[N], b[N]; 262 263 int fa[N], cnt_v[N], cnt_e[N], selfloop[N]; 264 int vis[N]; 265 void init () { 266 iota(fa + 1, fa + n + 1, 1); 267 fill(cnt_v + 1, cnt_v + n + 1, 1); 268 fill(cnt_e + 1, cnt_e + n + 1, 0); 269 fill(selfloop + 1, selfloop + n + 1, 0); 270 fill(vis + 1, vis + n + 1, 0); 271 } 272 int getfa (int x) { 273 return fa[x] == x ? x : fa[x] = getfa(fa[x]); 274 } 275 void merge (int u, int v) { 276 u = getfa(u); 277 v = getfa(v); 278 cnt_v[u] += cnt_v[v]; 279 cnt_e[u] += cnt_e[v]; 280 selfloop[u] |= selfloop[v]; 281 fa[v] = u; 282 } 283 284 int main () { 285 ios::sync_with_stdio(0); 286 cin.tie(0); 287 288 MULTI { 289 cin >> n; 290 for (int i = 1;i <= n;++i) { 291 cin >> a[i]; 292 } 293 for (int i = 1;i <= n;++i) { 294 cin >> b[i]; 295 } 296 297 init(); 298 for (int i = 1;i <= n;++i) { 299 if (getfa(a[i]) != getfa(b[i])) merge(a[i], b[i]); 300 cnt_e[getfa(a[i])]++; 301 if (a[i] == b[i]) selfloop[getfa(a[i])] = 1; 302 } 303 304 ll ans = 1; 305 for (int i = 1;i <= n;++i) if (vis[getfa(i)] == 0) { 306 if (cnt_v[getfa(i)] != cnt_e[getfa(i)]) ans = 0; 307 else ans = ans * (selfloop[getfa(i)] ? n : 2) % mod; 308 vis[getfa(i)] = 1; 309 } 310 cout << ans << endl; 311 } 312 } 313 ``` 314 315 **Code (zengminghao, DFS)** 316 317 ``` 318 #include <bits/stdc++.h> 319 using namespace std; 320 const int N = 1e5 + 5; 321 const int P = 998244353; 322 323 int n, a[N], b[N]; 324 vector <int> G[N]; 325 bool vis[N]; 326 327 int vertex, edge, self_loop; 328 void dfs(int x) { 329 if (vis[x]) return ; 330 vis[x] = true; 331 vertex++; 332 for (auto y : G[x]) { 333 edge++; 334 dfs(y); 335 if (y == x) { 336 self_loop++; 337 } 338 } 339 } 340 341 void solve() { 342 scanf("%d", &n); 343 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); 344 for (int i = 1; i <= n; i++) scanf("%d", &b[i]); 345 346 for (int i = 1; i <= n; i++) G[i].clear(); 347 348 for (int i = 1; i <= n; i++) { 349 G[a[i]].push_back(b[i]); 350 G[b[i]].push_back(a[i]); 351 } 352 353 int ans = 1; 354 355 for (int i = 1; i <= n; i++) vis[i] = false; 356 for (int i = 1; i <= n; i++) { 357 if (vis[i]) continue ; 358 vertex = 0; 359 edge = 0; 360 self_loop = 0; 361 dfs(i); 362 if (edge != 2 * vertex) { 363 ans = 0; 364 } else if (self_loop) { 365 ans = 1ll * ans * n % P; 366 } else { 367 ans = ans * 2 % P; 368 } 369 } 370 371 printf("%d\n", ans); 372 } 373 374 int main() { 375 int t; 376 scanf("%d", &t); 377 while (t--) { 378 solve(); 379 } 380 return 0; 381 } 382 ``` 383 384 ## [1770E - Koxia and Tree](/contest/1770/problem/E "Good Bye 2022: 2023 is NEAR") 385 386 Idea by [m_99](/profile/m_99 "International Grandmaster m_99") 387 388 **Hint 1** 389 390 Solve a classic problem — find the sum of pairwise distances of $k$ chosen nodes in a tree. 391 392 **Hint 2** 393 394 If we add the move operations while the direction of edges are fixed, find the sum of pairwise distances of $k$ chosen nodes. 395 396 **Hint 2.5** 397 398 If you can't solve the problem in Hint 2, consider why writers make each edge passed by butterflies for at most once. 399 400 **Hint 3** 401 402 When the direction of edges become random, how maintaining $p_i$ as the possibility of "node $i$ contains a butterfly" help you to get the answer? 403 404 **Solution** 405 406 At first sight, we usually think of a classic problem — find the sum of pairwise distances of $k$ chosen nodes in a tree. For any edge, if there are $x$ chosen nodes and $n - x$ chosen nodes respectively on each side of it, then there will be $x (n - x)$ pairs of nodes passing this edge. Without loss of generality, let's assign node $1$ as root, and define both $\mathit{siz}_i$ as the number of chosen nodes in subtree $i$. By summing up $\mathit{siz}_{\mathit{son}} (n - \mathit{siz}_{\mathit{son}})$ for each edge $(\mathit{fa}, \mathit{son})$, we derive the answer, which equals to the expected value of the distance of two nodes (Uniformly randomly chosen from $k$ nodes) after dividing by $\binom{k}{2}$. 407 408 Let's turn to Hint 2 then — add the move operations while the direction of edges are fixed. Let's define $\mathit{siz}^0_i$ and $\mathit{siz}_i$ as the number of butterflies in subtree $i$, but before any move operation / in real time respectively. A very important observation is, although butterflies are moving, we can always claim $|\mathit{siz}_{\mathit{son}} - \mathit{siz}^0_{\mathit{son}}| \leq 1$ because each edge is passed by butterflies for at most once. This property allows us to discuss different values of $\mathit{siz}_{\mathit{son}}$ to sum up the answer in constant time complexity, if you maintain butterflies' positions correctly. 409 410 When we introduce random directions additionally, if we define $p_i$ as the possibility of "node $i$ contains a butterfly", then an equivalent statement of move operation from node $u$ to node $v$ will be, actually, set $p_u = p_v = \frac{p_u+p_v}{2}$, which allows us to maintain $p$ in real time easily. Similarly, by discussing values of $\mathit{siz}_{\mathit{son}}$ (but with possibilities of each case instead of specified moves), we get the final answer. The total time complexity is $O(n)$. 411 412 **Code (Nanako)** 413 414 ``` 415 #include <iostream> 416 #include <vector> 417 using namespace std; 418 typedef long long ll; 419 420 const int N = 3e5 + 5; 421 const int mod = 998244353; 422 const int inv2 = 499122177; 423 424 ll qpow (ll n, ll m) { 425 ll ret = 1; 426 while (m) { 427 if (m & 1) ret = ret * n % mod; 428 n = n * n % mod; 429 m >>= 1; 430 } 431 return ret; 432 } 433 ll getinv (ll a) { 434 return qpow(a, mod - 2); 435 } 436 437 int n, k; 438 int a[N]; 439 int u[N], v[N]; 440 441 vector <int> e[N]; 442 int fa[N]; 443 ll p[N], sum[N]; 444 void dfs (int u, int f) { 445 sum[u] = p[u]; 446 for (int v : e[u]) if (v != f) { 447 dfs(v, u); 448 fa[v] = u; 449 sum[u] += sum[v]; 450 } 451 } 452 453 int main () { 454 ios::sync_with_stdio(0); 455 cin.tie(0); 456 457 cin >> n >> k; 458 for (int i = 1;i <= k;++i) { 459 cin >> a[i]; 460 p[a[i]] = 1; 461 } 462 for (int i = 1;i <= n - 1;++i) { 463 cin >> u[i] >> v[i]; 464 e[u[i]].push_back(v[i]); 465 e[v[i]].push_back(u[i]); 466 } 467 dfs(1, -1); 468 469 ll ans = 0; 470 for (int i = 1;i <= n - 1;++i) { 471 if (fa[u[i]] == v[i]) swap(u[i], v[i]); 472 ll puv = p[u[i]] * (1 - p[v[i]] + mod) % mod; 473 ll pvu = p[v[i]] * (1 - p[u[i]] + mod) % mod; 474 ll delta = 0; 475 delta -= puv * sum[v[i]] % mod * (k - sum[v[i]]) % mod; 476 delta -= pvu * sum[v[i]] % mod * (k - sum[v[i]]) % mod; 477 delta += puv * (sum[v[i]] + 1) % mod * (k - sum[v[i]] - 1) % mod; 478 delta += pvu * (sum[v[i]] - 1) % mod * (k - sum[v[i]] + 1) % mod; 479 ans = (ans + sum[v[i]] * (k - sum[v[i]]) + delta * inv2) % mod; 480 ans = (ans % mod + mod) % mod; 481 p[u[i]] = p[v[i]] = 1ll * (p[u[i]] + p[v[i]]) * inv2 % mod; 482 } 483 cout << ans * getinv(1ll * k * (k - 1) / 2 % mod) % mod << endl; 484 } 485 ``` 486 487 ## [1770F - Koxia and Sequence](/contest/1770/problem/F "Good Bye 2022: 2023 is NEAR") 488 489 Idea by [m_99](/profile/m_99 "International Grandmaster m_99") 490 491 **Hint 1** 492 493 From symmetry, for any non-negative integer $t$, the number of good sequences with $a_1=t$, the number of good sequences with $a_2=t$, ... are equal. 494 495 **Hint 2** 496 497 It is useful to consider the contribution of each bit to the answer independently. 498 499 **Hint 3** 500 501 Since XOR is undone twice, considering the contribution to the answer can be regarded as counting up over mod $2$. 502 503 **Hint 4** 504 505 It is difficult to count those for which total or is $y$, but it is relatively easy to count those for which total or is a subset of $y$. Then, we can consider a way using the inclusion-exclusion principle. 506 507 **Hint 5** 508 509 Lucas's theorem and Kummer's theorem are useful. In particular, you can derive equivalence conditions on or. 510 511 **Hint 6** 512 513 "There are $a+b$ white balls. For every pair $(c,d)$ of nonnegative integers satisfying $c+d=n$, find the sum of the ways to choose $c$ balls from the first $a$ balls and $d$ balls from the remaining $b$ balls." The answer to this problem is $_{a+b} C_{n}$. This is because considering how to choose for every pair $(c,d)$ of non-negative integers satisfying $c+d=n$ merely consider the case of choosing $n$ balls as how many balls to choose from $a$ balls and $b$ balls. This result is called Vandermonde's identity. 514 515 **Solution** 516 517 Let $f(i,t)$ is the number of good sequence such that $a_i=t$. $f(1,t)=f(2,t)=...=f(n,t)$, so if $n$ is even, the answer is $0$. Otherwise, the answer is total xor of $t$ such that number of good sequences such that $a_1=t$ is odd. We can consider each bit independently, so we can rewrite the problem "for each $i$, find the number of good sequences such that $a_1$'s $i$-th bit is $1$, modulo $2$". 518 519 Let $g(y')$ is the answer if $y$ is a subset of $y'$(means $y \mid y'=y'$). We can prove with induction the answer of the original problem is total xor of $g(y')$ such that $y'$ is a subset of given $y$. So, the goal is for each $i$, find the number of $y'$ such that $y'$ is a subset of $y$ and $g(y')$'s $i$-th bit is $1$, modulo $2$. 520 521 We can prove with Lucas's theorem or Kummer's theorem ($p=2$), "$\binom{a}{b} \bmod 2$ is $1$" is equivalent to "$b$ is a subset of $a$". The number of sequences such that the length is $n$ and total sum is $x$ and total or is a subset of $y$, modulo $2$ is equal to $\sum_{t_1+\ldots+t_n=x} \prod{} \binom{y}{t_i}$, because if there is $t_i$ which is not a subset of $y$, $\binom{y}{t_i}$ is $0$ and the product is also $0$, modulo $2$. Consider Vandermonde's identity, the value is equal to $\binom{ny}{x}$. In a similar way, we can rewrite the problem to "for each $i$, find the number of $y'$ such that $y'$ is a subset of $y$ and $y'$'s $i$-th bit is $1$ and $x-2^i$ is a subset of $ny'-2^i$($\binom{ny'-2^i}{x-2^i} \bmod 2 = 1$), modulo $2$". 522 523 From the above, we can solve this problem in $O(y \log y)$ by performing the calculation in $O(1)$ for all $i$ and all $y'$. 524 525 **Code (errorgorn)** 526 527 ``` 528 #include <bits/stdc++.h> 529 using namespace std; 530 531 #define int long long 532 #define ll long long 533 #define ii pair<ll,ll> 534 #define iii pair<ii,ll> 535 #define fi first 536 #define se second 537 #define endl '\n' 538 #define debug(x) cout << #x << ": " << x << endl 539 540 #define pub push_back 541 #define pob pop_back 542 #define puf push_front 543 #define pof pop_front 544 #define lb lower_bound 545 #define ub upper_bound 546 547 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 548 #define all(x) (x).begin(),(x).end() 549 #define sz(x) (int)(x).size() 550 551 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 552 553 int n,a,b; 554 555 bool isSub(int i,int j){ 556 if (i<0 || j<0) return false; 557 return (j&i)==i; 558 } 559 560 signed main(){ 561 ios::sync_with_stdio(0); 562 cin.tie(0); 563 cout.tie(0); 564 cin.exceptions(ios::badbit | ios::failbit); 565 566 cin>>n>>a>>b; 567 568 int ans=0; 569 for (int sub=b;sub;sub=(sub-1)&b) rep(bit,0,20) if (sub&(1<<bit)){ 570 if (isSub(a-(1<<bit),n*sub-(1<<bit))){ 571 ans^=(1<<bit); 572 } 573 } 574 575 cout<<ans*(n%2)<<endl; 576 } 577 ``` 578 579 ## [1770G - Koxia and Bracket](/contest/1770/problem/G "Good Bye 2022: 2023 is NEAR") 580 581 Idea by [huangxiaohua](/profile/huangxiaohua "Grandmaster huangxiaohua") and [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 582 583 **Hint 1** 584 585 What special properties does the deleted bracket sequence have? 586 587 **Hint 2** 588 589 Try to solve this with $O(n^2)$ DP. 590 591 **Hint 3** 592 593 If there is no balance requirement, can multiple brackets be processed quickly with one operation? 594 595 **Hint 4** 596 597 Can you combine the last idea with divide-and-conquer or something? 598 599 **Solution** 600 601 #### $O(n^2)$ Solution 602 603 Let us consider what properties the removed bracket subsequence has. 604 605 First, it must be a bracket subsequence in the form `))...)((....(`. The proof is simple: if there is a deleted `)` on the right-hand side of a `(`, then we can keep them in $s$ without breaking the balancing property of the remaining sequence. 606 607 This property means that we can divide the string into $2$ parts. We only delete `)` from the first part and only delete `(` from the second part. Now let us try to find the dividing point between the two parts: Consider a prefix sum based on a sequence of brackets in which each `(` is replaced by 1 and each `)` is replaced by -1. 608 609 We define a position as a *special position* if and only if the number corresponding to this position is less than the previously occurring minimum value. It is easy to see that whenever a special position occurs, we must remove an additional `)` before this position to make the bracket sequence satisfy the condition again. 610 611 Considering the above idea, we can find that only the `)` before the farthest special position may be deleted, so we can use this position as the dividing point. 612 613 We now solve two separate problems. However, we can turn the problem on deleting only '(' into the one on deleting only `)`. For example, if we are only allowed to delete `(` from `(()((()())`, it is equivalent to the number of ways to delete only `)` from `(()()))())`. 614 615 For the part where only `)` is deleted, the sufficient condition for it to be a balanced bracket sequence is that each number in the prefix sum must be greater than 0 after the operation. 616 617 Also considering the above ideas, let us define the state $dp_{i,j}$, which represents after removing the breakets required by special position, the number of ways to delete additional $j$ $(j \geq 0)$ occurrence of `)` from the string up the $i$-th occurrence of `)` in the string. 618 619 $ \begin{equation} dp_{i,j} = \begin{cases} dp_{i-1,j}+dp_{i-1,j-1}, & \text{if } i \text{ is not special}; \\ dp_{i-1,j}+dp_{i-1,j+1}, & \text{if } i \text{ is special}. \end{cases} \end{equation} $ 620 621 Multiply the $dp_{end,0}$ obtained from both parts of the string to obtain the answer. The time complexity is $O(n^2)$ and optimized implementations can run in about 9 seconds, but it is not enough to pass. 622 623 #### $O(n\sqrt{n \log n})$ Solution 624 625 Let's try to optimize the transitions when there are no special positions. For state $dp_{i,j}$, after processing $k$ individual `)`, the transitions are as follows: 626 627 $dp_{i+k,j}=\sum_{l=0}^k \binom{k}{l} \times dp_{i,j-l}$ 628 629 We find that this transfer equation behaves as a polynomial convolution. Thus we can optimize this convolution by NTT with a time complexity of $O(n \log n)$ for a single operation, while the worst global complexity of this Solution is $O(n^2 \log n)$ due to the presence of the special position. 630 631 Consider how this Solution can be combined with the $O(n^2)$ Solution. For states $dp_{i,j}$ where we want to consider its contribution to $dp_{i+k}$, if $j \geq k$ is satisfied, then the transitions are not affected by the special position anyway. 632 633 Based on the above idea, we can adopt a mixed Solution based on periodic reconstruction: set the reconstruction period $B$, and within one round of the period, we use the $O(n^2)$ DP Solution to handle the part of $j \le B$, while for the part of $j \gt B$, we compute the answer by NTT after one round of the period. 634 635 The time complexity $O(\frac{n^2}{B}+B\cdot n \log n)$ can be optimized to $O(n\sqrt{n \log n})$ by setting the appropriate $B$. Although the time complexity is still high, given the low constant factor of the $O(n^2)$ solution, a decently-optimized implementation is able to get AC. 636 637 #### $O(n\log^2 n)$ Solution 638 639 Consider combining the idea of extracting $j \geq k$ parts for NTT with divide-and-conquer. Suppose now that the interval to be processed is $(l,r)$, where the DP polynomial passed is $s$. We proceed as follows: 640 641 * Count the number of special positions $num$ in the interval $(l,r)$, extract the part of the polynomial $s$ corresponding to the state $j \geq num$, and convolute it with the current interval alone. 642 * Pass the part of the polynomial $s$ corresponding to the state $j \lt num$ into the interval $(l,mid)$, and then pass the result into the interval $(mid+1,r)$ to continue the operation. 643 * Add the polynomials obtained by the above two steps directly, and return the obtained polynomial. 644 645 How to calculate the time complexity of performing the above operations? Let's analyze the operations passed into the left interval and the right interval separately. 646 647 * When passing in the left interval $(l,mid)$, the size of the polynomial for the NTT operation is the number of special positions in the interval $(l,r)$ minus the number of special positions in the left interval $(l,mid)$, i.e., the number of special positions in the right interval $(mid+1,r)$, which does not exceed the length of the right interval $(mid+1,r)$. 648 * When passed into the right interval $(mid+1,r)$, the size of the polynomial does not exceed the length of the left interval $(l,mid)$. 649 * Also, the length of the combinatorial polynomial multiplied with $s$ is the interval length + 1. 650 651 In summary, the size of the two polynomials for the NTT operation in the interval $(l,r)$ does not exceed the interval length + 1. Thus the time complexity of this solution is divide-and-conquer combined with the time complexity of NTT, i.e. $O(n \log^2 n)$. 652 653 **Code (errorgorn)** 654 655 ``` 656 #include <bits/stdc++.h> 657 #include <ext/pb_ds/assoc_container.hpp> 658 #include <ext/pb_ds/tree_policy.hpp> 659 #include <ext/rope> 660 using namespace std; 661 using namespace __gnu_pbds; 662 using namespace __gnu_cxx; 663 664 #define int long long 665 #define ll long long 666 #define ii pair<ll,ll> 667 #define iii pair<ii,ll> 668 #define fi first 669 #define se second 670 #define endl '\n' 671 #define debug(x) cout << #x << ": " << x << endl 672 673 #define pub push_back 674 #define pob pop_back 675 #define puf push_front 676 #define pof pop_front 677 #define lb lower_bound 678 #define ub upper_bound 679 680 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 681 #define all(x) (x).begin(),(x).end() 682 #define sz(x) (int)(x).size() 683 684 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 685 //change less to less_equal for non distinct pbds, but erase will bug 686 687 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 688 689 const int MOD=998244353; 690 691 ll qexp(ll b,ll p,int m){ 692 ll res=1; 693 while (p){ 694 if (p&1) res=(res*b)%m; 695 b=(b*b)%m; 696 p>>=1; 697 } 698 return res; 699 } 700 701 ll inv(ll i){ 702 return qexp(i,MOD-2,MOD); 703 } 704 705 ll fix(ll i){ 706 i%=MOD; 707 if (i<0) i+=MOD; 708 return i; 709 } 710 711 ll fac[1000005]; 712 ll ifac[1000005]; 713 714 ll nCk(int i,int j){ 715 if (i<j) return 0; 716 return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD; 717 } 718 719 //https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/NumberTheoreticTransform.h 720 const ll mod = (119 << 23) + 1, root = 62; // = 998244353 721 // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21 722 // and 483 << 21 (same root). The last two are > 10^9. 723 typedef vector<int> vi; 724 typedef vector<ll> vl; 725 void ntt(vl &a) { 726 int n = sz(a), L = 31 - __builtin_clz(n); 727 static vl rt(2, 1); 728 for (static int k = 2, s = 2; k < n; k *= 2, s++) { 729 rt.resize(n); 730 ll z[] = {1, qexp(root, mod >> s, mod)}; 731 rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod; 732 } 733 vi rev(n); 734 rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2; 735 rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]); 736 for (int k = 1; k < n; k *= 2) 737 for (int i = 0; i < n; i += 2 * k) rep(j,0,k) { 738 ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j]; 739 a[i + j + k] = ai - z + (z > ai ? mod : 0); 740 ai += (ai + z >= mod ? z - mod : z); 741 } 742 } 743 vl conv(const vl &a, const vl &b) { 744 if (a.empty() || b.empty()) return {}; 745 int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B; 746 int inv = qexp(n, mod - 2, mod); 747 vl L(a), R(b), out(n); 748 L.resize(n), R.resize(n); 749 ntt(L), ntt(R); 750 rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod; 751 ntt(out); 752 return {out.begin(), out.begin() + s}; 753 } 754 755 vector<int> v; 756 757 vector<int> solve(int l,int r,vector<int> poly){ 758 if (poly.empty()) return poly; 759 760 if (l==r){ 761 poly=conv(poly,{1,1}); 762 poly.erase(poly.begin(),poly.begin()+v[l]); 763 return poly; 764 } 765 766 int m=l+r>>1; 767 int num=0; 768 rep(x,l,r+1) num+=v[x]; 769 num=min(num,sz(poly)); 770 771 vector<int> small(poly.begin(),poly.begin()+num); 772 poly.erase(poly.begin(),poly.begin()+num); 773 774 vector<int> mul; 775 rep(x,0,r-l+2) mul.pub(nCk(r-l+1,x)); 776 poly=conv(poly,mul); 777 778 small=solve(m+1,r,solve(l,m,small)); 779 poly.resize(max(sz(poly),sz(small))); 780 rep(x,0,sz(small)) poly[x]=(poly[x]+small[x])%MOD; 781 782 return poly; 783 } 784 785 int solve(string s){ 786 if (s=="") return 1; 787 v.clear(); 788 789 int mn=0,curr=0; 790 for (auto it:s){ 791 if (it=='(') curr++; 792 else{ 793 curr--; 794 if (curr<mn){ 795 mn=curr; 796 v.pub(1); 797 } 798 else{ 799 v.pub(0); 800 } 801 } 802 } 803 804 return solve(0,sz(v)-1,{1})[0]; 805 } 806 807 int n; 808 string s; 809 int pref[500005]; 810 811 signed main(){ 812 ios::sync_with_stdio(0); 813 cin.tie(0); 814 cout.tie(0); 815 cin.exceptions(ios::badbit | ios::failbit); 816 817 fac[0]=1; 818 rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD; 819 ifac[1000004]=inv(fac[1000004]); 820 rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD; 821 822 cin>>s; 823 n=sz(s); 824 pref[0]=0; 825 rep(x,0,n) pref[x+1]=pref[x]+(s[x]=='('?1:-1); 826 827 int pos=min_element(pref,pref+n+1)-pref; 828 string a=s.substr(0,pos),b=s.substr(pos,n-pos); 829 reverse(all(b)); for (auto &it:b) it^=1; 830 cout<<solve(a)*solve(b)%MOD<<endl; 831 } 832 ``` 833 834 ## [1770H - Koxia, Mahiru and Winter Festival](/contest/1770/problem/H "Good Bye 2022: 2023 is NEAR") 835 836 Idea by [SteamTurbine](/profile/SteamTurbine "International Master SteamTurbine") 837 838 **Hint 1** 839 840 In what scenario the maximum congestion is $1$? 841 842 **Hint 2** 843 844 Assume you have a blackbox that can solve any problem instance of size $n-2$, use it to solve a problem instance of size $n$. 845 846 **Preface** 847 848 This is a special case for a problem called *congestion minimization*. While in general this problem is NP-hard, for this special structure it can be solved efficiently. 849 850 The only case where the maximum congestion is $1$, is when $p = q = [1,2,\dots,n]$. This can be proved by a pigeonhole argument — if there exists some $p_i \neq i$ or $q_i \neq i$, the total length of the $2n$ paths will be strictly greater than the number of edges which means at least one edge has to be used more than once. 851 852 Our goal now is to try constructing a routing scheme with maximum congestion $2$. We will show that this is always doable for any input. We will first show a pictorial sketch that presents the idea, and fill in the details later. 853 854 We also provide you a python script that visualize the output to help you debug, you can find it at the end of this section. 855 856 **Solution (sketch)** 857 858     859 860 **Solution (details)** 861 862 The solution is based on induction. The base cases $n=0$ and $n=1$ are trivial. Now assume we can solve any problem instance for size up to $k-2$. We will treat it as a blackbox to solve a problem instance of size $k$. 863 864 Given any problem instance of size $k$, first we route the following $4$ demand pairs using only the outer edges: 865 866 * the top-bottom pair that starts at $(1, 1)$, using the left and bottom edges; 867 * the top-bottom pair that starts at $(1, k)$, using the right and bottom edges; 868 * the left-right pair that starts at $(1, 1)$, using the top and right edges; 869 * the left-right pair that ends at $(1,k)$, using the left and top edges. However, if this is the same pair as above, then we route another arbitrary left-right pair using the left, top and right edges. 870 871 As of now, there are $k-2$ top-bottom demands and $k-2$ left-right demands remain to be routed. We simply connect their starting and ending points one step closer to the center, retaining their relative order. In such way, we reduced the problem to a problem instance of size $k-2$ which we already knew how to solve. 872 873 **Code (SteamTurbine)** 874 875 ``` 876 #include <bits/stdc++.h> 877 #define FOR(i,s,e) for (int i=(s); i<(e); i++) 878 #define FOE(i,s,e) for (int i=(s); i<=(e); i++) 879 #define FOD(i,s,e) for (int i=(s)-1; i>=(e); i--) 880 #define PB push_back 881 using namespace std; 882 883 struct Paths{ 884 /* store paths in order */ 885 vector<vector<pair<int, int>>> NS, EW; 886 887 Paths(){ 888 NS.clear(); 889 EW.clear(); 890 } 891 }; 892 893 Paths solve(vector<int> p, vector<int> q){ 894 int n = p.size(); 895 Paths Ret; 896 Ret.NS.resize(n); 897 Ret.EW.resize(n); 898 899 // Base case 900 if (n == 0) return Ret; 901 if (n == 1){ 902 Ret.NS[0].PB({1, 1}); 903 Ret.EW[0].PB({1, 1}); 904 return Ret; 905 } 906 907 // Route NS flow originating from (1, 1) and (1, n) using leftmost and rightmost edges 908 FOE(i,1,n){ 909 Ret.NS[0].PB({i, 1}); 910 Ret.NS[n-1].PB({i, n}); 911 } 912 // Routing to final destination using bottom edges 913 FOE(i,2,p[0]) Ret.NS[0].PB({n, i}); 914 FOD(i,n,p[n-1]) Ret.NS[n-1].PB({n, i}); 915 916 // Create p'[] for n-2 instance 917 vector<int> p_new(0); 918 FOE(i,1,n-2) p_new.PB(p[i] - (p[i]>p[0]) - (p[i]>p[n-1])); 919 920 // Route EW flow originating from (1, 1) using topmost and rightmost edges 921 FOE(i,1,n) Ret.EW[0].PB({1, i}); 922 FOE(i,2,q[0]) Ret.EW[0].PB({i, n}); 923 924 // Route EW flow originating in (m, 1) with q[m] as small as possible 925 int m = 1; 926 // special handle so congestion is 1 if possible 927 if (p[0] == 1 && p[n-1] == n && q[0] == 1 && q[n-1] == n){ 928 m = n - 1; 929 FOE(i,1,n) Ret.EW[n-1].PB({n, i}); 930 } 931 else{ 932 FOR(i,1,n) if (q[i] < q[m]) m = i; 933 // Route(m+1, 1) --> (1, 1) --> (1, n) --> (q[m], n) 934 935 FOD(i,m+2,2) Ret.EW[m].PB({i, 1}); 936 FOR(i,1,n) Ret.EW[m].PB({1, i}); 937 FOE(i,1,q[m]) Ret.EW[m].PB({i, n}); 938 } 939 940 // Create q'[] for n-2 instance 941 vector<int> q_new(0); 942 FOR(i,1,n) if (i != m) q_new.PB(q[i] - (q[i]>q[0]) - (q[i]>q[m])); 943 944 if (n > 1){ 945 Paths S = solve(p_new, q_new); 946 int t; 947 948 // connect NS paths 949 FOR(i,1,n-1){ 950 Ret.NS[i].PB({1, i+1}); 951 for (auto [x, y]: S.NS[i-1]){ 952 Ret.NS[i].PB({x+1, y+1}); 953 t = y + 1; 954 } 955 Ret.NS[i].PB({n, t}); 956 if (p[i] != t) Ret.NS[i].PB({n, p[i]}); 957 } 958 959 // connect EW paths 960 int l = 0; 961 FOR(i,1,n) if (i != m){ 962 Ret.EW[i].PB({i+1, 1}); 963 if (i > m) Ret.EW[i].PB({i, 1}); 964 965 for (auto [x, y]: S.EW[l]){ 966 Ret.EW[i].PB({x+1, y+1}); 967 t = x + 1; 968 } 969 970 Ret.EW[i].PB({t, n}); 971 if (q[i] != t) Ret.EW[i].PB({q[i], n}); 972 ++l; 973 } 974 } 975 976 return Ret; 977 } 978 979 int main(){ 980 int n; 981 vector<int> p, q; 982 983 scanf("%d", &n); 984 p.resize(n), q.resize(n); 985 FOR(i,0,n) scanf("%d", &p[i]); 986 FOR(i,0,n) scanf("%d", &q[i]); 987 988 Paths Solution = solve(p, q); 989 990 for (auto path: Solution.NS){ 991 printf("%d", path.size()); 992 for (auto [x, y]: path) printf(" %d %d", x, y); 993 puts(""); 994 } 995 996 for (auto path: Solution.EW){ 997 printf("%d", path.size()); 998 for (auto [x, y]: path) printf(" %d %d", x, y); 999 puts(""); 1000 } 1001 return 0; 1002 } 1003 ``` 1004 1005 **Visualizer (Python script)** 1006 1007 ``` 1008 # --------------------------------------------------- 1009 # Visualize the ouput 1010 # Pass the output as stdin to the script 1011 # Only works for output with congestion at most 2 1012 # Code by SteamTurbine Dec 2022 1013 # --------------------------------------------------- 1014 1015 from PIL import Image, ImageDraw, ImageColor 1016 from sys import stdin 1017 import random 1018 1019 # Visual the ouput 1020 # Pass the output as stdin to the script 1021 1022 Lines = [line for line in stdin if len(line.strip()) > 0] 1023 n = int(len(Lines)/2) 1024 1025 im = Image.new('RGB', (n*150+200, n*150+200), (255, 255, 255)) 1026 draw = ImageDraw.Draw(im) 1027 1028 S = {(0,0,0,0)} 1029 Dict = {} 1030 Colors = ['orange', 'blue', 'green', 'red', 'skyblue', 'olive', 'brown', 'yellow', 'gray', 'tomato', 'tan' , 'purple', 'cyan', 'skyblue'] 1031 1032 # use color map if n is large 1033 if (n+n > len(Colors)): 1034 Colors = [] 1035 for name, code in ImageColor.colormap.items(): 1036 if (name != "black" and name != "white"): Colors.append(name) 1037 random.shuffle(Colors) 1038 1039 # draw blank lines 1040 # lines to down 1041 for i in range(1, n+1, 1): 1042 for j in range(1, n, 1): 1043 draw.line((i*150+20, j*150+20, i*150+20, j*150+170), fill = 'black', width = 5) 1044 1045 # lines to right 1046 for i in range(1, n, 1): 1047 for j in range(1, n+1, 1): 1048 draw.line((i*150+20, j*150+20, i*150+170, j*150+20), fill = 'black', width = 5) 1049 1050 for i in range(len(Lines)): 1051 line = Lines[i] 1052 arr = [int(x) for x in line.split()] 1053 pathlen = arr[0] 1054 color = Colors[i % len(Colors)] 1055 1056 # draw source and sink 1057 if (i >= n): 1058 # x from 0 to n 1059 y = arr[1] 1060 x = arr[2] 1061 draw.line((x*150-40, y*150+20, x*150+20, y*150+20), fill=color, width=12) 1062 y = arr[len(arr)-2] 1063 x = arr[len(arr)-1] 1064 draw.line((x*150+20, y*150+20, x*150+80, y*150+20), fill=color, width=12) 1065 else: 1066 # y from 0 to n 1067 y = arr[1] 1068 x = arr[2] 1069 draw.line((x*150+20, y*150-40, x*150+20, y*150+20), fill=color, width=12) 1070 y = arr[len(arr)-2] 1071 x = arr[len(arr)-1] 1072 draw.line((x*150+20, y*150+20, x*150+20, y*150+80), fill=color, width=12) 1073 1074 for k in range(3, len(arr), 2): 1075 (y1, x1, y2, x2) = arr[k-2:k+2] 1076 1077 if (x1 > x2): (x1, y1, x2, y2) = (x2, y2, x1, y1) 1078 elif (x1 == x2) and (y1 > y2): (x1, y1, x2, y2) = (x2, y2, x1, y1) 1079 1080 # check if set used 1081 if ((x1, y1, x2, y2) in S): 1082 old_color = Dict[(x1, y1, x2, y2)] 1083 used = 1 1084 else: 1085 used = 0 1086 S.add((x1, y1, x2, y2)) 1087 Dict[(x1, y1, x2, y2)] = color 1088 1089 # drawline 1090 if (x1 == x2): 1091 if (used): 1092 draw.line((x1*150+26, y1*150+20, x2*150+26, y2*150+20), fill=old_color, width=12) 1093 draw.line((x1*150+14, y1*150+20, x2*150+14, y2*150+20), fill=color, width=12) 1094 else: draw.line((x1*150+20, y1*150+20, x2*150+20, y2*150+20), fill=color, width=12) 1095 else: 1096 if (used): 1097 draw.line((x1*150+20, y1*150+26, x2*150+20, y2*150+26), fill=old_color, width=12) 1098 draw.line((x1*150+20, y1*150+14, x2*150+20, y2*150+14), fill=color, width=12) 1099 else: draw.line((x1*150+20, y1*150+20, x2*150+20, y2*150+20), fill=color, width=12) 1100 1101 # draw nodes 1102 for i in range(1, n+1, 1): 1103 for j in range(1, n+1, 1): 1104 draw.ellipse((i*150, j*150, i*150+40, j*150+40), fill = 'white', outline = 'black', width = 5) 1105 1106 im.show() 1107 im.save("problemF.png") 1108 ```