codeforces-scrape

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

1293.md (41984B)


      1 Source: https://codeforces.com/blog/entry/73051
      2 
      3 All themes written by [AkiLotus](/profile/AkiLotus "Master AkiLotus") (I am the only one in the team playing Cytus II anyway :D).
      4 
      5 ## [1293A - ConneR and the A.R.C. Markland-N](/contest/1293/problem/A "Codeforces Round 614 (Div. 2)")
      6 
      7 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
      8 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
      9 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus")
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 **Solution (Akikaze, C++)**
     16 
     17 Submission link: [69149995](/contest/1293/submission/69149995 "Submission 69149995 by AkiLotus")
     18 
     19 **Source code in plain text**
     20 
     21 ```
     22 #pragma GCC optimize("Ofast")
     23  
     24 #include <bits/stdc++.h>
     25 using namespace std;
     26  
     27 #define endl '\n'
     28  
     29 int n, s, k;
     30 vector<int> a;
     31  
     32 void Input() {
     33 	cin >> n >> s >> k; a.clear(); a.resize(k);
     34 	for (auto &z: a) cin >> z;
     35 }
     36  
     37 void Solve() {
     38 	for (int i=0; i<=k; i++) {
     39 		if (s-i >= 1 && find(a.begin(), a.end(), s-i) == a.end()) {cout << i << endl; return;}
     40 		if (s+i <= n && find(a.begin(), a.end(), s+i) == a.end()) {cout << i << endl; return;}
     41 	}
     42 	assert(false); // if reached this line, the solution failed to find a free floor
     43 }
     44  
     45 int main(int argc, char* argv[]) {
     46 	ios_base::sync_with_stdio(0); cin.tie(NULL);
     47 	int T; cin >> T; while (T--) {Input(); Solve();} return 0;
     48 }
     49 ```
     50 
     51 **Solution (Akikaze, Java 8)**
     52 
     53 Submission link: [69150848](/contest/1293/submission/69150848 "Submission 69150848 by AkiLotus")
     54 
     55 **Source code in plain text**
     56 
     57 ```
     58 import java.io.*;
     59 import java.util.*;
     60 
     61 public class Akisolution {
     62 	public static Scanner sc = new Scanner(System.in);
     63 	public static PrintWriter out = new PrintWriter(System.out, true);
     64 	public static int n, s, k;
     65 	public static int[] a;
     66 
     67 	public static boolean exist(int[] arr, int x) {
     68 		for (int i=0; i<arr.length; i++) {
     69 			if (arr[i] == x) return true;
     70 		}
     71 		return false;
     72 	}
     73 
     74 	public static void Input() {
     75 		n = sc.nextInt(); s = sc.nextInt(); k = sc.nextInt();
     76 		a = new int[k];
     77 		for (int i=0; i<k; i++) a[i] = sc.nextInt();
     78 	}
     79 
     80 	public static void Solve() {
     81 		for (int i=0; i<=k; i++) {
     82 			if (s-i >= 1 && !exist(a, s-i)) {out.println(i); return;}
     83 			if (s+i <= n && !exist(a, s+i)) {out.println(i); return;}
     84 		}
     85 		assert false; // if reached this line, the solution failed to find a free floor
     86 	}
     87 
     88 	public static void main(String[] args) {
     89 		int t = sc.nextInt();
     90 		while (t-- > 0) {Input(); Solve();}
     91 	}
     92 }
     93 ```
     94 
     95 **Solution (Akikaze, Python 3)**
     96 
     97 Submission link: [69150816](/contest/1293/submission/69150816 "Submission 69150816 by AkiLotus")
     98 
     99 **Source code in plain text**
    100 
    101 ```
    102 T = int(input())
    103 for test_no in range(T):
    104 	n, s, k = map(int, input().split())
    105 	a = list(map(int, input().split()))
    106 
    107 	for i in range(0, k+1):
    108 		if s-i >= 1 and not s-i in a: 
    109 			print(i); break
    110 		if s+i <= n and not s+i in a:
    111 			print(i); break
    112 	else: assert(False) # if reached this line, the solution failed to find a free floor
    113 ```
    114 
    115 ## [1293B - JOE is on TV!](/contest/1293/problem/B "Codeforces Round 614 (Div. 2)")
    116 
    117 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    118 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    119 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution (Akikaze, C++)**
    126 
    127 Submission link: [69151243](/contest/1293/submission/69151243 "Submission 69151243 by AkiLotus")
    128 
    129 **Source code in plain text**
    130 
    131 ```
    132 #pragma GCC optimize("Ofast")
    133 
    134 #include <bits/stdc++.h>
    135 using namespace std;
    136 
    137 #define endl '\n'
    138 
    139 int n;
    140 
    141 void Input() {
    142 	cin >> n;
    143 }
    144 
    145 void Solve() {
    146 	double ans = 0;
    147 	for (int i=1; i<=n; i++) ans += 1.0 / i;
    148 	
    149 	cout << fixed << setprecision(12) << ans << endl;
    150 }
    151 
    152 int main(int argc, char* argv[]) {
    153 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    154 	Input(); Solve(); return 0;
    155 }
    156 ```
    157 
    158 **Solution (Akikaze, Java 8)**
    159 
    160 Submission link: [69151737](/contest/1293/submission/69151737 "Submission 69151737 by AkiLotus")
    161 
    162 **Source code in plain text**
    163 
    164 ```
    165 import java.io.*;
    166 import java.util.*;
    167 
    168 public class Akisolution {
    169 	public static Scanner sc = new Scanner(System.in);
    170 	public static PrintWriter out = new PrintWriter(System.out, true);
    171 	public static int n;
    172 
    173 	public static void Input() {
    174 		n = sc.nextInt();
    175 	}
    176 
    177 	public static void Solve() {
    178 		double ans = 0;
    179 		for (int i=1; i<=n; i++) ans += 1.0 / i;
    180 
    181 		out.printf("%.12f\n", ans);
    182 	}
    183 
    184 	public static void main(String[] args) {
    185 		Input(); Solve();
    186 	}
    187 }
    188 ```
    189 
    190 **Solution (Akikaze, Python 3)**
    191 
    192 Submission link: [69151256](/contest/1293/submission/69151256 "Submission 69151256 by AkiLotus")
    193 
    194 **Source code in plain text**
    195 
    196 ```
    197 T = 1
    198 for test_no in range(T):
    199 	n = int(input())
    200 	ans = sum([1.0 / i for i in range(1, n+1)])
    201 
    202 	print(ans)
    203 ```
    204 
    205 ## [1292A - NEKO's Maze Game](/contest/1292/problem/A "Codeforces Round 614 (Div. 1)")
    206 
    207 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    208 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    209 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Video editorial**
    216 
    217 Video by [Errichto](/profile/Errichto "International Grandmaster Errichto"): <https://www.youtube.com/watch?v=mhrvlor1qH0>
    218 
    219 **Solution (Akikaze, C++)**
    220 
    221 Submission link: [69151594](/contest/1292/submission/69151594 "Submission 69151594 by AkiLotus")
    222 
    223 **Source code in plain text**
    224 
    225 ```
    226 #pragma GCC optimize("Ofast")
    227 
    228 #include <bits/stdc++.h>
    229 using namespace std;
    230 
    231 #define endl '\n'
    232 
    233 int n, q;
    234 vector<vector<int>> lava;
    235 
    236 void Input() {
    237 	cin >> n >> q;
    238 	lava.resize(2, vector<int>(n, 0));
    239 }
    240 
    241 void Solve() {
    242 	int blockedPair = 0;
    243 	while (q--) {
    244 		int x, y; cin >> x >> y; x--; y--;
    245 		int delta = (lava[x][y] == 0) ? +1 : -1;
    246 
    247 		lava[x][y] = 1 - lava[x][y];
    248 		for (int dy=-1; dy<=1; dy++) {
    249 			if (y+dy < 0 || y+dy >= n) continue;
    250 
    251 			if (lava[1-x][y+dy] == 1) blockedPair += delta;
    252 		}
    253 
    254 		cout << ((blockedPair == 0) ? "Yes\n" : "No\n");
    255 	}
    256 }
    257 
    258 int main(int argc, char* argv[]) {
    259 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    260 	Input(); Solve(); return 0;
    261 }
    262 ```
    263 
    264 **Solution (Akikaze, Java 8)**
    265 
    266 Submission link: [69151628](/contest/1292/submission/69151628 "Submission 69151628 by AkiLotus")
    267 
    268 **Source code in plain text**
    269 
    270 ```
    271 import java.io.*;
    272 import java.util.*;
    273 
    274 public class Akisolution {
    275 	public static Scanner sc = new Scanner(System.in);
    276 	public static PrintWriter out = new PrintWriter(System.out, true);
    277 	public static int n, q;
    278 	public static int[][] lava;
    279 
    280 	public static void Input() {
    281 		n = sc.nextInt(); q = sc.nextInt();
    282 		lava = new int[2][n];
    283 	}
    284 
    285 	public static void Solve() {
    286 		int blockedPair = 0;
    287 		while (q-- > 0) {
    288 			int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
    289 			int delta = (lava[x][y] == 0) ? +1 : -1;
    290 
    291 			lava[x][y] = 1 - lava[x][y];
    292 			for (int dy=-1; dy<=1; dy++) {
    293 				if (y+dy < 0 || y+dy >= n) continue;
    294 
    295 				if (lava[1-x][y+dy] == 1) blockedPair += delta;
    296 			}
    297 
    298 			if (blockedPair == 0) out.println("Yes");
    299 			else out.println("No");
    300 		}
    301 	}
    302 
    303 	public static void main(String[] args) {
    304 		Input(); Solve();
    305 	}
    306 }
    307 ```
    308 
    309 **Solution (Akikaze, Python 3)**
    310 
    311 Submission link: [69151636](/contest/1292/submission/69151636 "Submission 69151636 by AkiLotus")
    312 
    313 **Source code in plain text**
    314 
    315 ```
    316 T = 1
    317 for test_no in range(T):
    318 	n, q = map(int, input().split())
    319 	lava = [[0 for j in range(n)] for i in range(2)]
    320 
    321 	blockedPair = 0
    322 	while q > 0:
    323 		q -= 1
    324 		x, y = map(lambda s: int(s)-1, input().split())
    325 		delta = +1 if lava[x][y] == 0 else -1
    326 
    327 		lava[x][y] = 1 - lava[x][y]
    328 		for dy in range(-1, 2):
    329 			if y + dy >= 0 and y + dy < n and lava[1-x][y+dy] == 1:
    330 				blockedPair += delta
    331 		
    332 		if blockedPair == 0: print('Yes')
    333 		else: print('No')
    334 ```
    335 
    336 ## [1292B - Aroma's Search](/contest/1292/problem/B "Codeforces Round 614 (Div. 1)")
    337 
    338 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") feat. [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    339 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    340 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
    341 
    342 **Tutorial**
    343 
    344 Tutorial is loading...
    345 
    346 **Solution (Akikaze, C++)**
    347 
    348 Submission link: [69152149](/contest/1292/submission/69152149 "Submission 69152149 by AkiLotus")
    349 
    350 **Source code in plain text**
    351 
    352 ```
    353 #pragma GCC optimize("Ofast")
    354 
    355 #include <bits/stdc++.h>
    356 using namespace std;
    357 
    358 #define endl '\n'
    359 
    360 long long x0, y0, ax, ay, bx, by, xs, ys, t;
    361 
    362 void Input() {
    363 	cin >> x0 >> y0 >> ax >> ay >> bx >> by;
    364 	cin >> xs >> ys >> t;
    365 }
    366 
    367 void Solve() {
    368 	vector<long long> x(1, x0), y(1, y0);
    369 	long long LIMIT = (1LL << 62) - 1;
    370 	while ((LIMIT - bx) / ax >= x.back() && (LIMIT - by) / ay >= y.back()) {
    371 		x.push_back(ax * x.back() + bx); y.push_back(ay * y.back() + by);
    372 	}
    373 
    374 	int n = x.size();
    375 	int ans = 0;
    376 	for (int i=0; i<n; i++) {
    377 		for (int j=i; j<n; j++) {
    378 			long long length = x[j] - x[i] + y[j] - y[i];
    379 			long long dist2Left = abs(xs - x[i]) + abs(ys - y[i]);
    380 			long long dist2Right = abs(xs - x[j]) + abs(ys - y[j]);
    381 			if (length <= t - dist2Left || length <= t - dist2Right) ans = max(ans, j-i+1);
    382 		}
    383 	}
    384 
    385 	cout << ans << endl;
    386 }
    387 
    388 int main(int argc, char* argv[]) {
    389 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    390 	Input(); Solve(); return 0;
    391 }
    392 ```
    393 
    394 **Solution (Akikaze, Java 8)**
    395 
    396 Submission link: [69152154](/contest/1292/submission/69152154 "Submission 69152154 by AkiLotus")
    397 
    398 **Source code in plain text**
    399 
    400 ```
    401 import java.io.*;
    402 import java.util.*;
    403 
    404 public class Akisolution {
    405 	public static Scanner sc = new Scanner(System.in);
    406 	public static PrintWriter out = new PrintWriter(System.out, true);
    407 	public static long x0, y0, ax, ay, bx, by, xs, ys, t;
    408 
    409 	public static long abs(long x) {return ((x > 0) ? x : -x);}
    410 
    411 	public static void Input() {
    412 		x0 = sc.nextLong(); y0 = sc.nextLong();
    413 		ax = sc.nextLong(); ay = sc.nextLong(); bx = sc.nextLong(); by = sc.nextLong();
    414 		xs = sc.nextLong(); ys = sc.nextLong(); t = sc.nextLong();
    415 	}
    416 
    417 	public static void Solve() {
    418 		ArrayList<Long> x = new ArrayList<>(), y = new ArrayList<>();
    419 		x.add(x0); y.add(y0);
    420 		long LIMIT = ((long)1 << 62) - 1;
    421 		int n = x.size();
    422 		while ((LIMIT - bx) / ax >= x.get(n - 1) && (LIMIT - by) / ay >= y.get(n - 1)) {
    423 			x.add(ax * x.get(n - 1) + bx); y.add(ay * y.get(n - 1) + by); n++;
    424 		}
    425 
    426 		int ans = 0;
    427 		for (int i=0; i<n; i++) {
    428 			for (int j=i; j<n; j++) {
    429 				long length = x.get(j) - x.get(i) + y.get(j) - y.get(i);
    430 				long dist2Left = abs(xs - x.get(i)) + abs(ys - y.get(i));
    431 				long dist2Right = abs(xs - x.get(j)) + abs(ys - y.get(j));
    432 				if (length <= t - dist2Left || length <= t - dist2Right) {
    433 					ans = (ans > j-i+1) ? ans : (j - i + 1);
    434 				}
    435 			}
    436 		}
    437 		
    438 		out.println(ans);
    439 	}
    440 
    441 	public static void main(String[] args) {
    442 		Input(); Solve();
    443 	}
    444 }
    445 ```
    446 
    447 **Solution (Akikaze, Python 3)**
    448 
    449 Submission link: [69152156](/contest/1292/submission/69152156 "Submission 69152156 by AkiLotus")
    450 
    451 **Source code in plain text**
    452 
    453 ```
    454 T = 1
    455 for test_no in range(T):
    456 	x0, y0, ax, ay, bx, by = map(int, input().split())
    457 	xs, ys, t = map(int, input().split())
    458 
    459 	LIMIT = 2 ** 62 - 1
    460 	x, y = [x0], [y0]
    461 	while ((LIMIT - bx) / ax >= x[-1] and (LIMIT - by) / ay >= y[-1]):
    462 		x.append(ax * x[-1] + bx)
    463 		y.append(ay * y[-1] + by)
    464 	
    465 	n = len(x)
    466 	ans = 0
    467 	for i in range(n):
    468 		for j in range(i, n):
    469 			length = x[j] - x[i] + y[j] - y[i]
    470 			dist2Left = abs(xs - x[i]) + abs(ys - y[i])
    471 			dist2Right = abs(xs - x[j]) + abs(ys - y[j])
    472 			if (length <= t - dist2Left or length <= t - dist2Right): ans = max(ans, j-i+1)
    473 	
    474 	print(ans)
    475 ```
    476 
    477 ## [1292C - Xenon's Attack on the Gangs](/contest/1292/problem/C "Codeforces Round 614 (Div. 1)")
    478 
    479 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    480 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    481 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")
    482 
    483 **Tutorial**
    484 
    485 Tutorial is loading...
    486 
    487 **Solution (xuanquang1999, C++)**
    488 
    489 Submission link: [69152556](/contest/1292/submission/69152556 "Submission 69152556 by AkiLotus")
    490 
    491 **Source code in plain text**
    492 
    493 ```
    494 #include <bits/stdc++.h>
    495 
    496 using namespace std;
    497 
    498 int n, root;
    499 vector<vector<int>> tree, par, sub;
    500 vector<vector<long long>> dp;
    501 
    502 void dfs(int u) {
    503 	sub[root][u] = 1;
    504 	for(int v: tree[u]) {
    505 		if (v == par[root][u])
    506 			continue;
    507 		par[root][v] = u;
    508 		dfs(v);
    509 		sub[root][u] += sub[root][v];
    510 	}
    511 }
    512 
    513 long long getDP(int u, int v) {
    514 	if (u == v) return 0;
    515 	if (dp[u][v] != -1) return dp[u][v];
    516 
    517 	long long res = sub[u][v] * sub[v][u] + max(getDP(par[v][u], v), getDP(u, par[u][v]));
    518 	return dp[u][v] = res;
    519 }
    520 
    521 void input() {
    522 	scanf("%d", &n);
    523 
    524 	tree.assign(n, vector<int>());
    525 	for(int i = 0; i < n-1; ++i) {
    526 		int u, v;
    527 		scanf("%d%d", &u, &v);
    528 		--u; --v;
    529 		tree[u].push_back(v); tree[v].push_back(u);
    530 	}
    531 }
    532 
    533 void solve() {
    534 	// Preprocessing
    535 	par.assign(n, vector<int>(n, -1));
    536 	sub.assign(n, vector<int>(n, -1));
    537 	for(int u = 0; u < n; ++u) {
    538 		root = u;
    539 		dfs(u);
    540 	}
    541 
    542 	// Calculating DP
    543 	dp.assign(n, vector<long long>(n, -1LL));
    544 	long long ans = 0;
    545 	for(int u = 0; u < n; ++u)
    546 		for(int v = 0; v < n; ++v)
    547 			ans = max(ans, getDP(u, v));
    548 
    549 	cout << ans << endl;	
    550 }
    551 
    552 int main() {
    553 	input();
    554 	solve();
    555 
    556 	return 0;
    557 }
    558 ```
    559 
    560 **Solution (xuanquang1999, Java 8)**
    561 
    562 Submission link: [69152568](/contest/1292/submission/69152568 "Submission 69152568 by AkiLotus")
    563 
    564 **Source code in plain text**
    565 
    566 ```
    567 import java.io.PrintWriter;
    568 import java.util.ArrayList;
    569 import java.util.Scanner;
    570 
    571 public class Main {
    572 	private static Scanner in;
    573 	private static PrintWriter out;
    574 	
    575 	private static int n, root;
    576 	private static ArrayList<Integer>[] tree;
    577 	private static int[][] par, sub;
    578 	private static long[][] dp;
    579 	
    580 	private static long getDP(int u, int v) {
    581 		if (u == v) return 0;
    582 		if (dp[u][v] != -1) return dp[u][v];
    583 
    584 		long res = sub[u][v] * sub[v][u] + Math.max(getDP(par[v][u], v), getDP(u, par[u][v]));
    585 		return dp[u][v] = res;
    586 	}
    587 
    588 	private static void dfs(int u) {
    589 		sub[root][u] = 1;
    590 		for(int v: tree[u]) {
    591 			if (v == par[root][u])
    592 				continue;
    593 			par[root][v] = u;
    594 			dfs(v);
    595 			sub[root][u] += sub[root][v];
    596 		}
    597 	}
    598 
    599 	private static void input() {
    600 		n = in.nextInt();
    601 
    602 		tree = new ArrayList[n];
    603 		for(int u = 0; u < n; ++u)
    604 			tree[u] = new ArrayList<>();
    605 		for(int i = 0; i < n-1; ++i) {
    606 			int u = in.nextInt(), v = in.nextInt();
    607 			u -= 1; v -= 1;
    608 			tree[u].add(v); tree[v].add(u);
    609 		}
    610 	}
    611 
    612 	private static void solve() {
    613 		// Preprocessing
    614 		par = new int[n][n];
    615 		sub = new int[n][n];
    616 		for(int u = 0; u < n; ++u) {
    617 			par[u][u] = -1;
    618 			root = u;
    619 			dfs(u);
    620 		}
    621 
    622 		// Calculating DP
    623 		dp = new long[n][n];
    624 		for(int u = 0; u < n; ++u)
    625 			for(int v = 0; v < n; ++v)
    626 				dp[u][v] = -1;
    627 
    628 		long ans = 0;
    629 		for(int u = 0; u < n; ++u)
    630 			for(int v = 0; v < n; ++v)
    631 				ans = Math.max(ans, getDP(u, v));
    632 
    633 		out.println(ans);
    634 	}
    635 
    636 	public static void main(String[] args) {
    637 		in = new Scanner(System.in);
    638 		out = new PrintWriter(System.out);
    639 
    640 		input();
    641 		solve();
    642 
    643 		out.close();
    644 	}
    645 }
    646 ```
    647 
    648 **Solution (pajenegod, PyPy3)**
    649 
    650 Submission link: [72000655](/contest/1292/submission/72000655 "Submission 72000655 by pajenegod")
    651 
    652 **Source code in plain text**
    653 
    654 ```
    655 import sys
    656  
    657 # Read input and build the graph
    658 inp = [int(x) for x in sys.stdin.buffer.read().split()]; ii = 0
    659 n = inp[ii]; ii += 1
    660 coupl = [[] for _ in range(n)]
    661 for _ in range(n - 1):
    662     u = inp[ii] - 1; ii += 1
    663     v = inp[ii] - 1; ii += 1
    664     coupl[u].append(v)
    665     coupl[v].append(u)
    666  
    667 # Relabel to speed up n^2 operations later on
    668 bfs = [0]
    669 found = [0]*n
    670 found[0] = 1
    671 for node in bfs:
    672     for nei in coupl[node]:
    673         if not found[nei]:
    674             found[nei] = 1
    675             bfs.append(nei)
    676  
    677 new_label = [0]*n
    678 for i in range(n):
    679     new_label[bfs[i]] = i
    680  
    681 coupl = [coupl[i] for i in bfs]
    682 for c in coupl:
    683     c[:] = [new_label[x] for x in c]
    684  
    685 ##### DP using multisource bfs
    686  
    687 DP = [0] * (n * n)
    688 size = [1] * (n * n)
    689 P = [-1] * (n * n)
    690  
    691 # Create the bfs ordering
    692 bfs = [root * n + root for root in range(n)]
    693 for ind in bfs:
    694     P[ind] = ind
    695  
    696 for ind in bfs:
    697     node, root = divmod(ind, n)
    698     for nei in coupl[node]:
    699         ind2 = nei * n + root
    700         if P[ind2] == -1:
    701             bfs.append(ind2)
    702             P[ind2] = ind
    703  
    704 del bfs[:n]
    705  
    706 # Do the DP
    707 for ind in reversed(bfs):
    708     node, root = divmod(ind, n)
    709     ind2 = root * n + node
    710     pind = P[ind]
    711     parent = pind//n
    712     
    713     # Update size of (root, parent)
    714     size[pind] += size[ind]
    715  
    716     # Update DP value of (root, parent)
    717     DP[pind] = max(DP[pind], max(DP[ind], DP[ind2]) + size[ind] * size[ind2])
    718 print(max(DP[root * n + root] for root in range(n)))
    719 ```
    720 
    721 **Additional notes**
    722 
    723 [pajenegod](/profile/pajenegod "Grandmaster pajenegod") uses a variant of BFS dedicated for speed efficiency on Python 3 / PyPy3. More details [here](https://codeforces.com/blog/entry/124286?#comment-1103326).
    724 
    725 ## [1292D - Chaotic V.](/contest/1292/problem/D "Codeforces Round 614 (Div. 1)")
    726 
    727 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    728 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    729 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
    730 
    731 **Tutorial**
    732 
    733 Tutorial is loading...
    734 
    735 **Solution (Akikaze, C++)**
    736 
    737 Submission link: [69153064](/contest/1292/submission/69153064 "Submission 69153064 by AkiLotus")
    738 
    739 **Source code in plain text**
    740 
    741 ```
    742 #pragma GCC optimize("Ofast")
    743 
    744 #include <bits/stdc++.h>
    745 using namespace std;
    746 
    747 #define endl '\n'
    748 
    749 const int MAXK = 5000;
    750 int n; vector<int> cnt(MAXK + 1, 0);
    751 vector<vector<int>> primeExponential(MAXK + 1, vector<int>(MAXK + 1, 0));
    752 
    753 void Preprocess() {
    754 	for (int i=2; i<MAXK + 1; i++) {
    755 		for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
    756 		int tmp = i;
    757 		for (int x=2; x<=sqrt(tmp); x++) {
    758 			while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
    759 		}
    760 		if (tmp > 1) primeExponential[i][tmp]++;
    761 	}
    762 }
    763 
    764 void Input() {
    765 	cin >> n;
    766 	for (int i=0; i<n; i++) {
    767 		int k; cin >> k; cnt[k]++;
    768 	}
    769 }
    770 
    771 void Solve() {
    772 	Preprocess();
    773 
    774 	vector<int> bestPD(MAXK + 1, 1);
    775 	long long ans = 0, cur = 0;
    776 	for (int i=1; i<MAXK + 1; i++) {
    777 		if (!cnt[i]) {bestPD[i] = 1; continue;}
    778 		for (int j=1; j<MAXK + 1; j++) {
    779 			ans += 1LL * primeExponential[i][j] * cnt[i];
    780 			cur += 1LL * primeExponential[i][j] * cnt[i];
    781 			if (primeExponential[i][j]) bestPD[i] = j;
    782 		}
    783 	}
    784 
    785 	while (*max_element(bestPD.begin(), bestPD.end()) > 1) {
    786 		vector<int> frequency(MAXK + 1, 0);
    787 
    788 		for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];
    789 
    790 		int bestPrime = max_element(frequency.begin(), frequency.end()) - frequency.begin();
    791 		int bestGroup = frequency[bestPrime];
    792 		if (bestGroup * 2 <= n) break;
    793 		if (bestPrime == 1) break;
    794 		cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);
    795 
    796 		for (int i=0; i<MAXK + 1; i++) {
    797 			if (bestPD[i] != bestPrime) bestPD[i] = 1;
    798 			if (bestPD[i] == 1) continue;
    799 			primeExponential[i][bestPD[i]] -= 1;
    800 			while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
    801 		}
    802 	}
    803 
    804 	cout << ans << endl;
    805 }
    806 
    807 int main(int argc, char* argv[]) {
    808 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    809 	Input(); Solve(); return 0;
    810 }
    811 ```
    812 
    813 **Solution (Akikaze, Java 8)**
    814 
    815 Submission link: [69153077](/contest/1292/submission/69153077 "Submission 69153077 by AkiLotus")
    816 
    817 **Source code in plain text**
    818 
    819 ```
    820 import java.io.*;
    821 import java.util.*;
    822 
    823 public class Akisolution {
    824 	public static Scanner sc = new Scanner(System.in);
    825 	public static PrintWriter out = new PrintWriter(System.out, true);
    826 	public static final int MAXK = 5000;
    827 	public static int n;
    828 	public static int[] cnt = new int[MAXK + 1];
    829 	public static int[][] primeExponential = new int[MAXK + 1][MAXK + 1];
    830 
    831 	public static long min(long a, long b) {return ((a < b) ? a : b);}
    832 
    833 	public static int max_element(int[] arr) {
    834 		int res = -1000000000;
    835 		for (int i=0; i<arr.length; i++) {
    836 			if (arr[i] > res) res = arr[i];
    837 		}
    838 		return res;
    839 	}
    840 
    841 	public static int max_id(int[] arr) {
    842 		int res = -1000000000, id = -1;
    843 		for (int i=0; i<arr.length; i++) {
    844 			if (arr[i] > res) {
    845 				res = arr[i];
    846 				id = i;
    847 			}
    848 		}
    849 		return id;
    850 	}
    851 
    852 	public static void Preprocess() {
    853 		for (int i=2; i<MAXK + 1; i++) {
    854 			for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
    855 			int tmp = i;
    856 			for (int x=2; x<=Math.sqrt(tmp); x++) {
    857 				while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
    858 			}
    859 			if (tmp > 1) primeExponential[i][tmp]++;
    860 		}
    861 	}
    862 
    863 	public static void Input() {
    864 		n = sc.nextInt();
    865 		for (int i=0; i<n; i++) {
    866 			int k = sc.nextInt();
    867 			cnt[k] += 1;
    868 		}
    869 	}
    870 
    871 	public static void Solve() {
    872 		Preprocess();
    873 
    874 		int[] bestPD = new int[MAXK + 1];
    875 		for (int i=0; i<MAXK + 1; i++) bestPD[i] = 1;
    876 		long ans = 0, cur = 0;
    877 		for (int i=1; i<MAXK + 1; i++) {
    878 			if (cnt[i] == 0) {bestPD[i] = 1; continue;}
    879 			for (int j=1; j<MAXK + 1; j++) {
    880 				ans += (long)primeExponential[i][j] * cnt[i];
    881 				cur += (long)primeExponential[i][j] * cnt[i];
    882 				if (primeExponential[i][j] != 0) bestPD[i] = j;
    883 			}
    884 		}
    885 
    886 		while (max_element(bestPD) > 1) {
    887 			int[] frequency = new int[MAXK + 1];
    888 
    889 			for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];
    890 
    891 			int bestPrime = max_id(frequency);
    892 			int bestGroup = frequency[bestPrime];
    893 			if (bestGroup * 2 <= n) break;
    894 			if (bestPrime == 1) break;
    895 			cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);
    896 
    897 			for (int i=0; i<MAXK + 1; i++) {
    898 				if (bestPD[i] != bestPrime) bestPD[i] = 1;
    899 				if (bestPD[i] == 1) continue;
    900 				primeExponential[i][bestPD[i]] -= 1;
    901 				while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
    902 			}
    903 		}
    904 
    905 		out.println(ans);
    906 	}
    907 
    908 	public static void main(String[] args) {
    909 		Input(); Solve();
    910 	}
    911 }
    912 ```
    913 
    914 **Solution (Akikaze, PyPy 3)**
    915 
    916 Submission link: [69153090](/contest/1292/submission/69153090 "Submission 69153090 by AkiLotus")
    917 
    918 **Source code in plain text**
    919 
    920 ```
    921 T = 1
    922 for test_no in range(T):
    923 	MAXK = 5000
    924 	n = int(input())
    925 	cnt = [0] * (MAXK + 1)
    926 	primeExponential = [[0 for j in range(MAXK + 1)] for i in range(MAXK + 1)]
    927 
    928 	line, num = (input() + ' '), 0
    929 	for c in line:
    930 		if c != ' ': num = num * 10 + (ord(c) - 48)
    931 		else:
    932 			cnt[num] += 1
    933 			num = 0
    934 
    935 	for i in range(2, MAXK + 1):
    936 		for j in range(0, MAXK + 1): primeExponential[i][j] += primeExponential[i-1][j]
    937 		tmp, x = i, 2
    938 		while x * x <= tmp:
    939 			while tmp % x == 0:
    940 				primeExponential[i][x] += 1
    941 				tmp //= x
    942 			x += 1
    943 		if tmp > 1: primeExponential[i][tmp] += 1
    944 
    945 	bestPD = [1] * (MAXK + 1)
    946 	ans, cur = 0, 0
    947 
    948 	for i in range(1, MAXK + 1):
    949 		if cnt[i] == 0: continue
    950 		for j in range(1, MAXK + 1):
    951 			ans += primeExponential[i][j] * cnt[i]
    952 			cur += primeExponential[i][j] * cnt[i]
    953 			if primeExponential[i][j]: bestPD[i] = j
    954 
    955 	frequency = [0] * (MAXK + 1)
    956 	while max(bestPD) > 1:
    957 		for i in range(MAXK + 1): frequency[i] = 0
    958 		for i in range(MAXK + 1): frequency[bestPD[i]] += cnt[i]
    959 
    960 		bestGroup = max(frequency)
    961 		bestPrime = frequency.index(bestGroup)
    962 		if bestGroup * 2 <= n: break
    963 		if bestPrime == 1: break
    964 		cur -= bestGroup
    965 		cur += (n - bestGroup); ans = min(ans, cur)
    966 
    967 		for i in range(MAXK + 1):
    968 			if bestPD[i] != bestPrime: bestPD[i] = 1
    969 			if bestPD[i] == 1: continue
    970 			primeExponential[i][bestPD[i]] -= 1
    971 			while bestPD[i] > 1 and primeExponential[i][bestPD[i]] == 0: bestPD[i] -= 1
    972 
    973 	print(ans)
    974 ```
    975 
    976 ## [1292E - Rin and The Unknown Flower](/contest/1292/problem/E "Codeforces Round 614 (Div. 1)")
    977 
    978 Author: [low_](/profile/low_ "Master low_") ([Sulfox](/profile/Sulfox "Grandmaster Sulfox") Remix)  
    979 Development: [low_](/profile/low_ "Master low_"), [Sulfox](/profile/Sulfox "Grandmaster Sulfox"), [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    980 Editorialist: [low_](/profile/low_ "Master low_")
    981 
    982 **Tutorial**
    983 
    984 Tutorial is loading...
    985 
    986 **Solution (Akikaze, C++)**
    987 
    988 Submission link: [69153383](/contest/1292/submission/69153383 "Submission 69153383 by AkiLotus")
    989 
    990 **Source code in plain text**
    991 
    992 ```
    993 #pragma GCC optimize("Ofast")
    994 
    995 #include <bits/stdc++.h>
    996 using namespace std;
    997 
    998 #define endl '\n'
    999 
   1000 int n, L, minID;
   1001 string s;
   1002 
   1003 void fill(int id, char c) {
   1004 	L -= (s[id] == 'L'); s[id] = c;
   1005 	minID = min(minID, id);
   1006 }
   1007 
   1008 void query(char cmd, string str) {
   1009 	cout << cmd << " " << str << endl; cout.flush();
   1010 	if (cmd == '?') {
   1011 		int k; cin >> k;
   1012 		assert(k != -1);
   1013 		vector<int> a(k);
   1014 		for (auto &z: a) {
   1015 			cin >> z; z--;
   1016 			for (int i=0; i<str.size(); i++) {
   1017 				assert(s[z+i] == 'L' || s[z+i] == str[i]);
   1018 				fill(z+i, str[i]);
   1019 			}
   1020 		}
   1021 	}
   1022 	else if (cmd == '!') {
   1023 		int correct; cin >> correct;
   1024 		assert(correct);
   1025 	}
   1026 }
   1027 
   1028 void Input() {
   1029 	cin >> n; s.clear();
   1030 	L = n; minID = n; s.resize(n, 'L');
   1031 }
   1032 
   1033 void Solve() {
   1034 	query('?', "CH"); query('?', "CO");
   1035 	query('?', "HC"); query('?', "HO");
   1036 	if (L == n) {
   1037 		// the string exists in form O...OX...X, with X=C or X=H
   1038 		// or it's completely mono-character
   1039 		query('?', "CCC");
   1040 		if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
   1041 		else {
   1042 			query('?', "HHH");
   1043 			if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
   1044 			else {
   1045 				query('?', "OOO");
   1046 				if (minID == n) {
   1047 					// obviously n=4
   1048 					query('?', "OOCC");
   1049 					if (minID == n) {fill(0, 'O'); fill(1, 'O'); fill(2, 'H'); fill(3, 'H');}
   1050 				}
   1051 				if (s[n-1] == 'L') {
   1052 					string t = s; t[n-1] = 'C';
   1053 					if (t[n-2] == 'L') t[n-2] = 'C';
   1054 					query('?', t);
   1055 					if (s[n-1] == 'L') {
   1056 						fill(n-1, 'H');
   1057 						if (s[n-2] == 'L') fill(n-2, 'H');
   1058 					}
   1059 				}
   1060 			}
   1061 		}
   1062 	}
   1063 	else {
   1064 		int maxID = minID; while (maxID < n-1 && s[maxID+1] != 'L') maxID++;
   1065 		for (int i=minID-1; i>=0; i--) {
   1066 			query('?', s.substr(i+1, 1) + s.substr(minID, maxID-minID+1));
   1067 			if (minID != i) {
   1068 				for (int x=0; x<=i; x++) fill(x, 'O');
   1069 				break;
   1070 			}
   1071 		}
   1072 		int nextFilled;
   1073 		for (int i=maxID+1; i<n; i++) {
   1074 			if (s[i] != 'L') continue;
   1075 			nextFilled = i;
   1076 			while (nextFilled < n && s[nextFilled] == 'L') nextFilled++;
   1077 			query('?', s.substr(0, i) + s[i-1]);
   1078 			if (s[i] == 'L') {
   1079 				if (s[i-1] != 'O') fill(i, 'O');
   1080 				else {
   1081 					if (nextFilled == n) {
   1082 						query('?', s.substr(0, i) + 'C');
   1083 						if (s[i] == 'L') fill(i, 'H');
   1084 						for (int x=i+1; x<nextFilled; x++) fill(x, s[i]);
   1085 					}
   1086 					else for (int x=i; x<nextFilled; x++) fill(x, s[nextFilled]);
   1087 					i = nextFilled - 1;
   1088 				}
   1089 			}
   1090 		}
   1091 	}
   1092 	query('!', s);
   1093 }
   1094 
   1095 int main(int argc, char* argv[]) {
   1096 	ios_base::sync_with_stdio(0); cin.tie(NULL);
   1097 	int T; cin >> T; while (T--) {Input(); Solve();} return 0;
   1098 }
   1099 ```
   1100 
   1101 **Solution (Akikaze, Java 8)**
   1102 
   1103 Submission link: [69153556](/contest/1292/submission/69153556 "Submission 69153556 by AkiLotus")
   1104 
   1105 **Source code in plain text**
   1106 
   1107 ```
   1108 import java.io.*;
   1109 import java.util.*;
   1110 
   1111 public class Akisolution {
   1112 	public static Scanner sc = new Scanner(System.in);
   1113 
   1114 	public static class CPPString {
   1115 		// as the Java String is insanely cryptic to modify
   1116 		public char[] arr;
   1117 
   1118 		public CPPString() {}
   1119 		public CPPString(String str) {this.arr = str.toCharArray();}
   1120 		public CPPString(char[] ca) {this.arr = ca;}
   1121 		public CPPString(CPPString other) {
   1122 			this.arr = new char[other.arr.length];
   1123 			for (int i=0; i<other.arr.length; i++) this.arr[i] = other.arr[i];
   1124 		}
   1125 		public void resize(int length, char defaultChar) {
   1126 			this.arr = new char[length];
   1127 			for (int i=0; i<length; i++) this.arr[i] = defaultChar;
   1128 		}
   1129 		public int size() {return this.arr.length;}
   1130 		public CPPString substr(int L, int len) {
   1131 			// get substring [L, L+len)
   1132 			char[] res = new char[len];
   1133 			for (int i=0; i<len; i++) res[i] = this.arr[L+i];
   1134 			return new CPPString(res);
   1135 		}
   1136 		public CPPString add(char ch) {
   1137 			char[] new_ca = new char[this.arr.length + 1]; new_ca[this.arr.length] = ch;
   1138 			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
   1139 			return new CPPString(new_ca);
   1140 		}
   1141 		public CPPString add(CPPString other) {
   1142 			char[] new_ca = new char[this.arr.length + other.arr.length];
   1143 			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
   1144 			for (int i=0; i<other.arr.length; i++) new_ca[this.arr.length + i] = other.arr[i];
   1145 			return new CPPString(new_ca);
   1146 		}
   1147 
   1148 		@Override
   1149 		public String toString() {return new String(arr);}
   1150 	}
   1151 
   1152 	public static int n, L, minID;
   1153 	public static CPPString s;
   1154 
   1155 	public static void fill(int id, char c) {
   1156 		if (s.arr[id] == 'L') L--;
   1157 		s.arr[id] = c;
   1158 		minID = (minID < id) ? minID : id;
   1159 	}
   1160 
   1161 	public static void query(char cmd, CPPString str) {
   1162 		System.out.println(cmd + " " + str); System.out.flush();
   1163 		System.err.println(cmd + " " + str);
   1164 		if (cmd == '?') {
   1165 			int k = sc.nextInt();
   1166 			assert (k != -1);
   1167 			int[] a = new int[k];
   1168 			for (int index = 0; index < k; index++) {
   1169 				a[index] = sc.nextInt() - 1;
   1170 				for (int i=0; i<str.size(); i++) {
   1171 					assert (s.arr[a[index]+i] == 'L' || s.arr[a[index]+i] == str.arr[i]);
   1172 					fill(a[index]+i, str.arr[i]);
   1173 				}
   1174 			}
   1175 		}
   1176 		else if (cmd == '!') {
   1177 			int correct = sc.nextInt();
   1178 			assert (correct == 1);
   1179 		}
   1180 	}
   1181 
   1182 	public static void query(char cmd, String str) {
   1183 		query(cmd, new CPPString(str));
   1184 	}
   1185 
   1186 	public static void Input() {
   1187 		n = sc.nextInt(); s = new CPPString();
   1188 		L = n; minID = n; s.resize(n, 'L');
   1189 	}
   1190 
   1191 	public static void Solve() {
   1192 		query('?', "CH"); query('?', "CO");
   1193 		query('?', "HC"); query('?', "HO");
   1194 		if (L == n) {
   1195 			// the string exists in form O...OX...X, with X=C or X=H
   1196 			// or it's completely mono-character
   1197 			query('?', "CCC");
   1198 			if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
   1199 			else {
   1200 				query('?', "HHH");
   1201 				if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
   1202 				else {
   1203 					query('?', "OOO");
   1204 					if (minID == n) {
   1205 						// obviously n=4
   1206 						query('?', "OOCC");
   1207 						if (minID == n) {
   1208 							fill(0, 'O'); fill(1, 'O');
   1209 							fill(2, 'H'); fill(3, 'H');
   1210 						}
   1211 					}
   1212 					if (s.arr[n-1] == 'L') {
   1213 						CPPString t = new CPPString(s); t.arr[n-1] = 'C';
   1214 						if (t.arr[n-2] == 'L') t.arr[n-2] = 'C';
   1215 						query('?', t);
   1216 						if (s.arr[n-1] == 'L') {
   1217 							fill(n-1, 'H');
   1218 							if (s.arr[n-2] == 'L') fill(n-2, 'H');
   1219 						}
   1220 					}
   1221 				}
   1222 			}
   1223 		}
   1224 		else {
   1225 			int maxID = minID; while (maxID < n-1 && s.arr[maxID+1] != 'L') maxID++;
   1226 			for (int i=minID-1; i>=0; i--) {
   1227 				query('?', s.substr(i+1, 1).add(s.substr(minID, maxID-minID+1)));
   1228 				if (minID != i) {
   1229 					for (int x=0; x<=i; x++) fill(x, 'O');
   1230 					break;
   1231 				}
   1232 			}
   1233 			int nextFilled;
   1234 			for (int i=maxID+1; i<n; i++) {
   1235 				if (s.arr[i] != 'L') continue;
   1236 				nextFilled = i;
   1237 				while (nextFilled < n && s.arr[nextFilled] == 'L') nextFilled++;
   1238 				query('?', s.substr(0, i).add(s.arr[i-1]));
   1239 				if (s.arr[i] == 'L') {
   1240 					if (s.arr[i-1] != 'O') fill(i, 'O');
   1241 					else {
   1242 						if (nextFilled == n) {
   1243 							query('?', s.substr(0, i).add('C'));
   1244 							if (s.arr[i] == 'L') fill(i, 'H');
   1245 							for (int x=i+1; x<nextFilled; x++) fill(x, s.arr[i]);
   1246 						}
   1247 						else for (int x=i; x<nextFilled; x++) fill(x, s.arr[nextFilled]);
   1248 						i = nextFilled - 1;
   1249 					}
   1250 				}
   1251 			}
   1252 		}
   1253 		query('!', s);
   1254 	}
   1255 
   1256 	public static void main(String[] args) {
   1257 		int T = sc.nextInt();
   1258 		while (T-- > 0) {Input(); Solve();}
   1259 	}
   1260 }
   1261 ```
   1262 
   1263 **Solution (Akikaze, Python 3)**
   1264 
   1265 Submission link: [69153398](/contest/1292/submission/69153398 "Submission 69153398 by AkiLotus")
   1266 
   1267 **Source code in plain text**
   1268 
   1269 ```
   1270 import sys
   1271 n, L, minID = None, None, None
   1272 s = []
   1273 
   1274 def fill(id, c):
   1275 	global n, L, s, minID
   1276 	L -= (s[id] == 'L')
   1277 	s = s[0:id] + c + s[id+1:]
   1278 	minID = min(minID, id)
   1279 
   1280 def query(cmd, str):
   1281 	global n, L, s, minID
   1282 	print(cmd, ''.join(str))
   1283 	print(cmd, ''.join(str), file=sys.stderr)
   1284 	sys.stdout.flush()
   1285 	if (cmd == '?'):
   1286 		result = list(map(int, input().split()))
   1287 		assert(result[0] != -1)
   1288 		for z in result[1:]:
   1289 			z -= 1
   1290 			for i in range(len(str)):
   1291 				assert(s[z+i] == 'L' or s[z+i] == str[i])
   1292 				fill(z+i, str[i])
   1293 	elif (cmd == '!'):
   1294 		correct = int(input())
   1295 		assert(correct == 1)
   1296 
   1297 T = int(input())
   1298 for test_no in range(T):
   1299 	n = int(input())
   1300 	L, minID = n, n
   1301 	s = 'L' * n
   1302 
   1303 	query('?', "CH")
   1304 	query('?', "CO")
   1305 	query('?', "HC")
   1306 	query('?', "HO")
   1307 	if (L == n):
   1308 		# the string exists in form O...OX...X, with X=C or X=H
   1309 		# or it's completely mono-character
   1310 		query('?', "CCC")
   1311 		if (minID < n): 
   1312 			for x in range(minID-1, -1, -1): fill(x, 'O')
   1313 		else:
   1314 			query('?', "HHH")
   1315 			if (minID < n):
   1316 				for x in range(minID-1, -1, -1): fill(x, 'O')
   1317 			else:
   1318 				query('?', "OOO")
   1319 				if (minID == n):
   1320 					# obviously n=4
   1321 					query('?', "OOCC")
   1322 					if (minID == n):
   1323 						fill(0, 'O')
   1324 						fill(1, 'O')
   1325 						fill(2, 'H')
   1326 						fill(3, 'H')
   1327 				
   1328 				if (s[n-1] == 'L'):
   1329 					t = s[0:n-1] + 'C'
   1330 					if (t[n-2] == 'L'): t = t[0:n-2] + 'C' + t[n-1:]
   1331 					query('?', t)
   1332 					if (s[n-1] == 'L'):
   1333 						fill(n-1, 'H')
   1334 						if (s[n-2] == 'L'): fill(n-2, 'H')
   1335 	else:
   1336 		maxID = minID
   1337 		while (maxID < n-1 and s[maxID+1] != 'L'): maxID += 1
   1338 		for i in range(minID-1, -1, -1):
   1339 			query('?', s[i+1:i+2] + s[minID:maxID+1])
   1340 			if (minID != i):
   1341 				for x in range(i+1): fill(x, 'O')
   1342 				break
   1343 		
   1344 		nextFilled = None
   1345 		i = maxID + 1
   1346 		while i < n:
   1347 			if (s[i] != 'L'):
   1348 				i += 1
   1349 				continue
   1350 			nextFilled = i
   1351 			while (nextFilled < n and s[nextFilled] == 'L'): nextFilled += 1
   1352 			query('?', s[0:i] + s[i-1])
   1353 			if (s[i] == 'L'):
   1354 				if (s[i-1] != 'O'): fill(i, 'O')
   1355 				else:
   1356 					if (nextFilled == n):
   1357 						query('?', s[0:i] + 'C')
   1358 						if (s[i] == 'L'): fill(i, 'H')
   1359 						for x in range(i+1, nextFilled): fill(x, s[i])
   1360 					else:
   1361 						for x in range(i, nextFilled): fill(x, s[nextFilled])
   1362 					i = nextFilled - 1
   1363 			i += 1
   1364 	query('!', s)
   1365 ```
   1366 
   1367 ## [1292F - Nora's Toy Boxes](/contest/1292/problem/F "Codeforces Round 614 (Div. 1)")
   1368 
   1369 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") × [MofK](/profile/MofK "Grandmaster MofK")  
   1370 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
   1371 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")
   1372 
   1373 **Tutorial**
   1374 
   1375 Tutorial is loading...
   1376 
   1377 **Solution (xuanquang1999, C++)**
   1378 
   1379 Submission link: [69153931](/contest/1292/submission/69153931 "Submission 69153931 by AkiLotus")
   1380 
   1381 **Source code in plain text**
   1382 
   1383 ```
   1384 #include <bits/stdc++.h>
   1385 
   1386 using namespace std;
   1387 
   1388 const int MOD = 1000000007;
   1389 
   1390 bool isSubset(int a, int b) {
   1391 	return (a & b) == a;
   1392 }
   1393 
   1394 bool isIntersect(int a, int b) {
   1395 	return (a & b) != 0;
   1396 }
   1397 
   1398 void add(int &a, long long b) {
   1399 	a = (a + b) % MOD;
   1400 }
   1401 
   1402 // Solve for each weakly connected component (WCC)
   1403 int cntOrder(vector<int> s, vector<int> t) {
   1404 	int p = s.size(), m = t.size();
   1405 
   1406 	vector<int> inMask(m, 0);
   1407 	for(int x = 0; x < p; ++x)
   1408 		for(int i = 0; i < m; ++i)
   1409 			if (t[i] % s[x] == 0)
   1410 				inMask[i] |= 1 << x;
   1411 
   1412 	vector<int> cnt(1<<p, 0);
   1413 	for(int mask = 0; mask < (1<<p); ++mask)
   1414 		for(int i = 0; i < m; ++i)
   1415 			if (isSubset(inMask[i], mask))
   1416 				++cnt[mask];
   1417 
   1418 	vector<vector<int>> dp(m+1, vector<int>(1<<p, 0));
   1419 	for(int i = 0; i < m; ++i)
   1420 		dp[1][inMask[i]] += 1;
   1421 	for(int k = 1; k < m; ++k) {
   1422 		for(int mask = 0; mask < (1<<p); ++mask) {
   1423 			for(int i = 0; i < m; ++i)
   1424 				if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
   1425 					add(dp[k+1][mask | inMask[i]], dp[k][mask]);
   1426 			add(dp[k+1][mask], 1LL * dp[k][mask] * (cnt[mask] - k));
   1427 		}
   1428 	}
   1429 
   1430 	return dp[m][(1<<p)-1];
   1431 }
   1432 
   1433 int n;
   1434 vector<int> a, degIn, s, t;
   1435 vector<vector<int>> graph;
   1436 vector<bool> visited;
   1437 
   1438 void dfs(int u) {
   1439 	visited[u] = true;
   1440 	if (degIn[u] == 0)
   1441 		s.push_back(a[u]);
   1442 	else
   1443 		t.push_back(a[u]);
   1444 
   1445 	for(int v: graph[u])
   1446 		if (!visited[v])
   1447 			dfs(v);
   1448 }
   1449 
   1450 void input() {
   1451 	scanf("%d", &n);
   1452 	a.resize(n);
   1453 	for(int u = 0; u < n; ++u)
   1454 		scanf("%d", &a[u]);
   1455 }
   1456 
   1457 void solve() {
   1458 	// Pre-calculate C(n, k)
   1459 	vector<vector<int>> c(n, vector<int>(n, 0));
   1460 	for(int i = 0; i < n; ++i) {
   1461 		c[i][0] = 1;
   1462 		for(int j = 1; j <= i; ++j)
   1463 			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
   1464 	}
   1465 
   1466 	// Building divisibility graph
   1467 	degIn.assign(n, 0);
   1468 	graph.assign(n, vector<int>());
   1469 	for(int u = 0; u < n; ++u) {
   1470 		for(int v = 0; v < n; ++v) {
   1471 			if (u != v && a[v] % a[u] == 0) {
   1472 				graph[u].push_back(v);
   1473 				graph[v].push_back(u);
   1474 				++degIn[v];
   1475 			}
   1476 		}
   1477 	}
   1478 
   1479 	// Solve for each WCC of divisibility graph and combine result
   1480 	int ans = 1;
   1481 	int curLen = 0;
   1482 	visited.assign(n, false);
   1483 	for(int u = 0; u < n; ++u) {
   1484 		if (!visited[u]) {
   1485 			s.clear();
   1486 			t.clear();
   1487 			dfs(u);
   1488 
   1489 			if (!t.empty()) {
   1490 				int sz = t.size() - 1;
   1491 				int cnt = cntOrder(s, t);
   1492 
   1493 				// Number of orders for current WCC
   1494 				ans = (1LL * ans * cnt) % MOD;
   1495 				// Number of ways to insert <sz> number to array of <curLen> elements
   1496 				ans = (1LL * ans * c[curLen + sz][sz]) % MOD;
   1497 				curLen += sz;
   1498 			}
   1499 		}
   1500 	}
   1501 
   1502 	printf("%d\n", ans);  
   1503 }
   1504 
   1505 int main() {
   1506 	input();
   1507 	solve();
   1508 
   1509 	return 0;
   1510 }
   1511 ```
   1512 
   1513 **Solution (xuanquang1999, Java 8)**
   1514 
   1515 Submission link: [69153932](/contest/1292/submission/69153932 "Submission 69153932 by AkiLotus")
   1516 
   1517 **Source code in plain text**
   1518 
   1519 ```
   1520 import java.io.PrintWriter;
   1521 import java.util.ArrayList;
   1522 import java.util.Scanner;
   1523 
   1524 public class Main {
   1525 	private static Scanner in;
   1526 	private static PrintWriter out;
   1527 	private static final int MOD = (int)1e9 + 7;
   1528 	
   1529 	private static int n;
   1530 	private static int[] a, degIn;
   1531 	private static ArrayList<Integer> s, t;
   1532 	private static boolean[] visited;
   1533 	private static ArrayList<Integer>[] graph;
   1534 	
   1535 	private static boolean isSubset(int a, int b) {
   1536 		return (a & b) == a;
   1537 	}
   1538 
   1539 	private static boolean isIntersect(int a, int b) {
   1540 		return (a & b) != 0;
   1541 	}
   1542 
   1543 	// Solve for each weakly connected component (WCC)
   1544 	private static int cntOrder(ArrayList<Integer> s, ArrayList<Integer> t) {
   1545 		int p = s.size(), m = t.size();
   1546 
   1547 		int[] inMask = new int[m];
   1548 		for(int x = 0; x < p; ++x)
   1549 			for(int i = 0; i < m; ++i)
   1550 				if (t.get(i) % s.get(x) == 0)
   1551 					inMask[i] |= 1 << x;
   1552 
   1553 		int[] cnt = new int[1<<p];
   1554 		for(int mask = 0; mask < (1<<p); ++mask)
   1555 			for(int i = 0; i < m; ++i)
   1556 				if (isSubset(inMask[i], mask))
   1557 					++cnt[mask];
   1558 
   1559 		int[][] dp = new int[m+1][1<<p];
   1560 		for(int i = 0; i < m; ++i)
   1561 			dp[1][inMask[i]] += 1;
   1562 		for(int k = 1; k < m; ++k) {
   1563 			for(int mask = 0; mask < (1<<p); ++mask) {
   1564 				for(int i = 0; i < m; ++i)
   1565 					if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
   1566 						dp[k+1][mask | inMask[i]] = (int)((dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD);
   1567 				dp[k+1][mask] = (int)((dp[k+1][mask] + (long)dp[k][mask] * (cnt[mask] - k)) % MOD);
   1568 			}
   1569 		}
   1570 
   1571 		return dp[m][(1<<p)-1];
   1572 	}
   1573 
   1574 	private static void dfs(int u) {
   1575 		visited[u] = true;
   1576 		if (degIn[u] == 0)
   1577 			s.add(a[u]);
   1578 		else
   1579 			t.add(a[u]);
   1580 	
   1581 		for(int v: graph[u])
   1582 			if (!visited[v])
   1583 				dfs(v);
   1584 	}
   1585 	
   1586 	private static void input() {
   1587 		n = in.nextInt();
   1588 		a = new int[n];
   1589 		for(int u = 0; u < n; ++u)
   1590 			a[u] = in.nextInt();
   1591 	}
   1592 	
   1593 	private static void solve() {
   1594 		// Pre-calculate C(n, k)
   1595 		int[][] c = new int[n][n];
   1596 		for(int i = 0; i < n; ++i) {
   1597 			c[i][0] = 1;
   1598 			for(int j = 1; j <= i; ++j)
   1599 				c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
   1600 		}
   1601 	
   1602 		// Building divisibility graph
   1603 		degIn = new int[n];
   1604 		graph = new ArrayList[n];
   1605 		for(int u = 0; u < n; ++u)
   1606 			graph[u] = new ArrayList<>();
   1607 		for(int u = 0; u < n; ++u) {
   1608 			for(int v = 0; v < n; ++v) {
   1609 				if (u != v && a[v] % a[u] == 0) {
   1610 					graph[u].add(v);
   1611 					graph[v].add(u);
   1612 					++degIn[v];
   1613 				}
   1614 			}
   1615 		}
   1616 	
   1617 		// Solve for each WCC of divisibility graph and combine result
   1618 		int ans = 1;
   1619 		int curLen = 0;
   1620 		visited = new boolean[n];
   1621 		for(int u = 0; u < n; ++u) {
   1622 			if (!visited[u]) {
   1623 				s = new ArrayList<>();
   1624 				t = new ArrayList<>();
   1625 				dfs(u);
   1626 	
   1627 				if (!t.isEmpty()) {
   1628 					int sz = t.size() - 1;
   1629 					int cnt = cntOrder(s, t);
   1630 	
   1631 					// Number of orders for current WCC
   1632 					ans = (int)(((long)ans * cnt) % MOD);
   1633 					// Number of ways to insert <sz> number to array of <curLen> elements
   1634 					ans = (int)(((long)ans * c[curLen + sz][sz]) % MOD);
   1635 					curLen += sz;
   1636 				}
   1637 			}
   1638 		}
   1639 	
   1640 		out.println(ans);
   1641 	}
   1642 	
   1643 	public static void main(String[] args) {
   1644 		in = new Scanner(System.in);
   1645 		out = new PrintWriter(System.out);
   1646 
   1647 		input();
   1648 		solve();
   1649 
   1650 		out.close();
   1651 	}
   1652 }
   1653 ```
   1654 
   1655 **Solution (xuanquang1999, PyPy 3)**
   1656 
   1657 Submission link: [69153968](/contest/1292/submission/69153968 "Submission 69153968 by AkiLotus")
   1658 
   1659 **Source code in plain text**
   1660 
   1661 ```
   1662 MOD = 1000000007
   1663 
   1664 def isSubset(a, b):
   1665 	return (a & b) == a
   1666 
   1667 def isIntersect(a, b):
   1668 	return (a & b) != 0
   1669 
   1670 # Solve for each weakly connected component (WCC)
   1671 def cntOrder(s, t):
   1672 	p = len(s)
   1673 	m = len(t)
   1674 
   1675 	inMask = [0 for i in range(m)]
   1676 
   1677 	for x in range(p):
   1678 		for i in range(m):
   1679 			if t[i] % s[x] == 0:
   1680 				inMask[i] |= 1 << x
   1681 
   1682 	cnt = [0 for mask in range(1<<p)]
   1683 	for mask in range(1<<p):
   1684 		for i in range(m):
   1685 			if isSubset(inMask[i], mask):
   1686 				cnt[mask] += 1
   1687 
   1688 	dp = [[0 for mask in range(1<<p)] for k in range(m+1)]
   1689 	for i in range(m):
   1690 		dp[1][inMask[i]] += 1
   1691 	for k in range(m):
   1692 		for mask in range(1<<p):
   1693 			for i in range(m):
   1694 				if not isSubset(inMask[i], mask) and isIntersect(inMask[i], mask):
   1695 					dp[k+1][mask | inMask[i]] = (dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD
   1696 			dp[k+1][mask] = (dp[k+1][mask] + dp[k][mask] * (cnt[mask] - k)) % MOD
   1697 
   1698 	return dp[m][(1<<p)-1]
   1699 
   1700 def dfs(u):
   1701 	global a, graph, degIn, visited, s, t
   1702 
   1703 	visited[u] = True
   1704 	if degIn[u] == 0:
   1705 		s.append(a[u])
   1706 	else:
   1707 		t.append(a[u])
   1708 
   1709 	for v in graph[u]:
   1710 		if not visited[v]:
   1711 			dfs(v)
   1712 
   1713 def main():
   1714 	global a, graph, degIn, visited, s, t
   1715 
   1716 	# Reading input
   1717 	n = int(input())
   1718 	a = list(map(int, input().split()))
   1719 
   1720 	# Pre-calculate C(n, k)
   1721 	c = [[0 for j in range(n)] for i in range(n)]
   1722 	for i in range(n):
   1723 		c[i][0] = 1
   1724 		for j in range(1, i+1):
   1725 			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD	
   1726 
   1727 	# Building divisibility graph
   1728 	degIn = [0 for u in range(n)]
   1729 	graph = [[] for u in range(n)]
   1730 	for u in range(n):
   1731 		for v in range(n):
   1732 			if u != v and a[v] % a[u] == 0:
   1733 				graph[u].append(v)
   1734 				graph[v].append(u)
   1735 				degIn[v] += 1
   1736 
   1737 	# Solve for each WCC of divisibility graph and combine result
   1738 	ans = 1
   1739 	curLen = 0
   1740 	visited = [False for u in range(n)]
   1741 	for u in range(n):
   1742 		if not visited[u]:
   1743 			s = []
   1744 			t = []
   1745 			dfs(u)
   1746 
   1747 			if len(t) > 0:
   1748 				sz = len(t) - 1
   1749 				cnt = cntOrder(s, t)
   1750 
   1751 				# Number of orders for current WCC
   1752 				ans = (ans * cnt) % MOD
   1753 				# Number of ways to insert <sz> number to array of <curLen> elements
   1754 				ans = (ans * c[curLen + sz][sz]) % MOD
   1755 				curLen += sz		
   1756 
   1757 	print(ans)
   1758 
   1759 if __name__ == "__main__":
   1760 	main()
   1761 ```