codeforces-scrape

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

1569.md (10261B)


      1 Source: https://codeforces.com/blog/entry/94721
      2 
      3 [1569A - Balanced Substring](/contest/1569/problem/A "Educational Codeforces Round 113 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n = int(input())
     16 	s = input()
     17 	for i in range(n - 1):
     18 		if s[i] != s[i + 1]:
     19 			print(i + 1, i + 2)
     20 			break
     21 	else:
     22 		print(-1, -1)
     23 ```
     24 
     25 [1569B - Chess Tournament](/contest/1569/problem/B "Educational Codeforces Round 113 (Rated for Div. 2)")
     26 
     27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution (Neon)**
     34 
     35 ```
     36 #include <bits/stdc++.h>
     37 
     38 using namespace std;
     39 
     40 int main() {
     41   ios_base::sync_with_stdio(false);
     42   cin.tie(NULL); 
     43   int t;
     44   cin >> t;
     45   while (t--) {
     46     int n;
     47     string s;
     48     cin >> n >> s;
     49     vector<int> id;
     50     for (int i = 0; i < n; ++i) if (s[i] == '2')
     51       id.push_back(i);
     52     int k = id.size();
     53     if (k == 1 || k == 2) {
     54       cout << "NO\n";
     55       continue;
     56     }
     57     vector<string> t(n, string(n, '='));
     58     for (int i = 0; i < n; ++i) t[i][i] = 'X';
     59     for (int i = 0; i < k; ++i) {
     60       int x = id[i], y = id[(i + 1) % k];
     61       t[x][y] = '+';
     62       t[y][x] = '-';
     63     }
     64     cout << "YES\n";
     65     for (int i = 0; i < n; ++i) cout << t[i] << '\n';
     66   }
     67 }
     68 ```
     69 
     70 [1569C - Jury Meeting](/contest/1569/problem/C "Educational Codeforces Round 113 (Rated for Div. 2)")
     71 
     72 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     73 
     74 **Tutorial**
     75 
     76 Tutorial is loading...
     77 
     78 **Solution (Neon)**
     79 
     80 ```
     81 #include <bits/stdc++.h>
     82 
     83 using namespace std;
     84 
     85 const int MOD = 998244353;
     86 
     87 int main() {
     88   ios_base::sync_with_stdio(false);
     89   cin.tie(NULL); 
     90   int t;
     91   cin >> t;
     92   while (t--) {
     93     int n;
     94     cin >> n;
     95     vector<int> a(n);
     96     for (int &x : a) cin >> x;
     97     int mx = *max_element(a.begin(), a.end());
     98     int cmx = count(a.begin(), a.end(), mx);
     99     int k = count(a.begin(), a.end(), mx - 1);
    100     int ans = 1, sub = 1;
    101     for (long long i = 1; i <= n; ++i) {
    102       ans = ans * i % MOD;
    103       if (i != k + 1) sub = sub * i % MOD;
    104     }
    105     if (cmx == 1) ans = (ans - sub + MOD) % MOD;
    106     cout << ans << '\n';
    107   }
    108 }
    109 ```
    110 
    111 [1569D - Inconvenient Pairs](/contest/1569/problem/D "Educational Codeforces Round 113 (Rated for Div. 2)")
    112 
    113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (adedalic)**
    120 
    121 ```
    122 #include<bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    127 #define sz(a) int((a).size())
    128 #define all(a) (a).begin(), (a).end()
    129 
    130 #define x first
    131 #define y second
    132 
    133 typedef long long li;
    134 typedef pair<int, int> pt;
    135 
    136 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    137 	return out << "(" << p.x << ", " << p.y << ")";
    138 }
    139 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    140 	fore(i, 0, sz(v)) {
    141 		if(i) out << " ";
    142 		out << v[i];
    143 	}
    144 	return out;
    145 }
    146 
    147 const int INF = int(1e9);
    148 const li INF64 = li(1e18);
    149 
    150 int n, m, k;
    151 vector<int> x, y;
    152 vector<pt> ps;
    153 
    154 inline bool read() {
    155 	if(!(cin >> n >> m >> k))
    156 		return false;
    157 	x.resize(n);
    158 	fore (i, 0, n)
    159 		cin >> x[i];
    160 	y.resize(m);
    161 	fore (i, 0, m)
    162 		cin >> y[i];
    163 	ps.resize(k);
    164 	fore (i, 0, k)
    165 		cin >> ps[i].x >> ps[i].y;
    166 	
    167 	return true;
    168 }
    169 
    170 inline void solve() {
    171 	li ans = 0;
    172 	
    173 	fore (_i, 0, 2) {
    174 		vector<int> cntY(m, 0);
    175 		sort(all(ps));
    176 		
    177 		vector<pt> bord(k);
    178 		
    179 		int u = 0;
    180 		while (u < k) {
    181 			int v = u;
    182 			while (v < k && ps[v].x == ps[u].x)
    183 				v++;
    184 			
    185 			fore (i, u, v) {
    186 				int r = int(lower_bound(all(y), ps[i].y) - y.begin());
    187 				int l = r;
    188 				if (y[l] > ps[i].y)
    189 					l--;
    190 				assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
    191 				
    192 				bord[i] = {l, r};
    193 			}
    194 			
    195 			fore (i, u, v) if (bord[i].x < bord[i].y)
    196 				ans += cntY[bord[i].x];
    197 			
    198 			fore (i, u, v) if (bord[i].x < bord[i].y)
    199 				cntY[bord[i].x]++;
    200 			
    201 			u = v;
    202 		}
    203 		
    204 		
    205 		fore (i, 0, k)
    206 			swap(ps[i].x, ps[i].y);
    207 		swap(x, y);
    208 		swap(n, m);
    209 	}
    210 	
    211 	cout << ans << endl;
    212 }
    213 
    214 int main() {
    215 #ifdef _DEBUG
    216 	freopen("input.txt", "r", stdin);
    217 	int tt = clock();
    218 #endif
    219 	ios_base::sync_with_stdio(false);
    220 	cin.tie(0), cout.tie(0);
    221 	cout << fixed << setprecision(15);
    222 	
    223 	int t; cin >> t;
    224 	while (t--) {
    225 		read();
    226 		solve();
    227 		
    228 #ifdef _DEBUG
    229 		cerr << "TIME = " << clock() - tt << endl;
    230 		tt = clock();
    231 #endif
    232 	}
    233 	return 0;
    234 }
    235 ```
    236 
    237 [1569E - Playoff Restoration](/contest/1569/problem/E "Educational Codeforces Round 113 (Rated for Div. 2)")
    238 
    239 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution (BledDest)**
    246 
    247 ```
    248 #include <bits/stdc++.h>     
    249 
    250 using namespace std;
    251 
    252 const int MOD = 998244353;
    253 
    254 int add(int x, int y)
    255 {
    256  	x += y;
    257  	while(x >= MOD) x -= MOD;
    258  	while(x < 0) x += MOD;
    259  	return x;
    260 }
    261 
    262 int mul(int x, int y)
    263 {
    264  	return (x * 1ll * y) % MOD;
    265 }
    266 
    267 int binpow(int x, int y)
    268 {
    269  	int z = 1;
    270  	while(y)
    271  	{
    272  	 	if(y & 1) z = mul(z, x);
    273  	 	x = mul(x, x);
    274  	 	y >>= 1;
    275  	}
    276  	return z;
    277 }
    278 
    279 vector<int> evaluate(int n, int choice_mask)
    280 {
    281  	int cur_place = n / 2 + 1;
    282  	int cur_bit = n - 2;
    283  	vector<int> p(n);
    284  	vector<int> c(n);
    285  	for(int i = 0; i < n; i++)
    286  		c[i] = i;
    287  	while(c.size() != 1)
    288  	{
    289  		vector<int> nc;
    290  	 	for(int i = 0; i < c.size(); i += 2)
    291  	 	{
    292  	 	 	if(choice_mask & (1 << cur_bit))
    293  	 	 	{
    294  	 	 		p[c[i]] = cur_place;
    295  	 	 		nc.push_back(c[i + 1]);
    296  	 	 	}
    297  	 	 	else
    298  	 	 	{
    299  	 	 		p[c[i + 1]] = cur_place;
    300  	 	 		nc.push_back(c[i]);
    301  	 	 	}
    302  	 	 	cur_bit--;
    303  	 	}
    304  	 	c = nc;
    305  	 	cur_place /= 2;
    306   		cur_place++;
    307 	}
    308 	p[c[0]] = 1;
    309 	return p;
    310 }
    311 
    312 vector<int> adjust(int n, vector<int> p, bool winning)
    313 {
    314 	for(int i = 0; i < n; i++)
    315 	{
    316 		if(p[i] == 1)
    317 		{
    318 		 	if(!winning) p[i]++;	
    319 		}
    320 		else
    321 		 	p[i] = p[i] * 2 - 1;
    322 	}
    323 	return p;
    324 }	
    325 
    326 int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
    327 {
    328 	if(partial)
    329 		p = adjust(n, p, winning);
    330  	int res = 0;
    331  	for(int i = 0; i < n; i++)
    332  		res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
    333  	return res;
    334 }
    335 
    336 int main()
    337 {
    338  	int k, A, h;
    339  	cin >> k >> A >> h;
    340  	if(k <= 4)
    341  	{
    342  		for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
    343  		{             
    344  			vector<int> p = evaluate(1 << k, i);
    345  			if(get_hash(1 << k, p, A) == h)
    346  			{
    347  		 		for(auto x : p) cout << x << " ";
    348  		 		cout << endl;
    349  		 		return 0;
    350  			}
    351  		}
    352  	}
    353  	else
    354  	{
    355  		int mask_left = -1;
    356  		int mask_right = -1;
    357  		bool left_win = false;
    358  		for(int c = 0; c < 2; c++)
    359  		{
    360  		 	map<int, int> left_map;
    361  		 	for(int i = 0; i < (1 << 16); i++)
    362  		 	{
    363  		 	 	vector<int> p = evaluate(16, i);
    364  		 	 	int left_hash = get_hash(16, p, A, true, c == 0, 0);
    365  		 	 	left_map[left_hash] = i;	
    366  		 	}
    367  		 	for(int i = 0; i < (1 << 16); i++)
    368  		 	{
    369  		 	 	vector<int> p = evaluate(16, i);
    370  		 	 	int right_hash = get_hash(16, p, A, true, c == 1, 16);
    371  		 	 	int left_hash = add(h, MOD - right_hash);
    372  		 	 	if(left_map.count(left_hash))
    373  		 	 	{
    374  		 	 	 	mask_left = left_map[left_hash];
    375  		 	 	 	mask_right = i;
    376  		 	 	 	left_win = (c == 0);
    377  		 	 	}
    378  		 	}
    379  	 	}
    380  	 	if(mask_left != -1)
    381  		{
    382  	 		vector<int> ans_left = evaluate(16, mask_left);
    383  	 		vector<int> ans_right = evaluate(16, mask_right);
    384  	 		ans_left = adjust(16, ans_left, left_win);
    385  	 		ans_right = adjust(16, ans_right, !left_win);
    386  	 		for(auto x : ans_left)
    387  	 			cout << x << " ";
    388  	   		for(auto x : ans_right)
    389  	   			cout << x << " ";
    390  	   		return 0;
    391  		}        
    392  	}
    393  	cout << -1 << endl;
    394  	return 0;
    395 }
    396 ```
    397 
    398 [1569F - Palindromic Hamiltonian Path](/contest/1569/problem/F "Educational Codeforces Round 113 (Rated for Div. 2)")
    399 
    400 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    401 
    402 **Tutorial**
    403 
    404 Tutorial is loading...
    405 
    406 **Solution (awoo)**
    407 
    408 ```
    409 #include <bits/stdc++.h>
    410 
    411 #define forn(i, n) for (int i = 0; i < int(n); i++)
    412 
    413 using namespace std;
    414 
    415 vector<vector<char>> g;
    416 map<long long, bool> dp;
    417 
    418 void brute(int n, vector<int> &p){
    419 	int x = find(p.begin(), p.end(), -1) - p.begin();
    420 	if (x == int(p.size())){
    421 		vector<vector<char>> dp2(1 << n, vector<char>(n));
    422 		vector<int> pos1(n), pos2(n);
    423 		forn(i, p.size()){
    424 			pos1[p[i]] = pos2[p[i]];
    425 			pos2[p[i]] = i;
    426 		}
    427 		forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
    428 		forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
    429 			forn(j, n) if (!((mask >> j) & 1)){
    430 				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
    431 				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
    432 			}
    433 		}
    434 		forn(i, n) if (dp2[(1 << n) - 1][i]){
    435 			long long num = 0;
    436 			for (int x : p) num = num * 6 + x;
    437 			dp[num] = true;
    438 			break;
    439 		}
    440 		return;
    441 	}
    442 	for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
    443 		p[x] = p[y] = n;
    444 		brute(n + 1, p);
    445 		p[x] = p[y] = -1;
    446 	}
    447 }
    448 
    449 bool dfs(vector<int> p){
    450 	vector<int> used(int(p.size()), -1);
    451 	int cnt = 0;
    452 	forn(i, p.size()) if (used[p[i]] == -1)
    453 		used[p[i]] = cnt++;
    454 	long long num = 0;
    455 	for (int& x : p){
    456 		x = used[x];
    457 		num = num * 6 + x;
    458 	}
    459 	if (dp.count(num)) return dp[num];
    460 	bool res = false;
    461 	vector<int> cur(cnt);
    462 	forn(i, p.size()) ++cur[p[i]];
    463 	forn(i, p.size()) if (cur[p[i]] > 2){
    464 		int x = p[i];
    465 		for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
    466 			p[i] = p[j] = cnt;
    467 			if (dfs(p)){
    468 				res = true;
    469 				break;
    470 			}
    471 			p[i] = p[j] = x;
    472 		}
    473 		break;
    474 	}
    475 	return dp[num] = res;
    476 }
    477 
    478 void brute2(int n, vector<int> &p){
    479 	int x = find(p.begin(), p.end(), -1) - p.begin();
    480 	if (x == int(p.size())){
    481 		dfs(p);
    482 		return;
    483 	}
    484 	forn(i, n + 1){
    485 		for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
    486 			p[x] = p[y] = i;
    487 			brute2(max(n, i + 1), p);
    488 			p[x] = p[y] = -1;
    489 		}
    490 	}
    491 }
    492 
    493 int main() {
    494 	int n, m, k;
    495 	scanf("%d%d%d", &n, &m, &k);
    496 	g.resize(n, vector<char>(n));
    497 	forn(_, m){
    498 		int v, u;
    499 		scanf("%d%d", &v, &u);
    500 		--v, --u;
    501 		g[v][u] = g[u][v] = 1;
    502 	}
    503 	vector<int> cur(n, -1);
    504 	brute(0, cur);
    505 	brute2(0, cur);
    506 	vector<long long> fact(k + 1);
    507 	fact[0] = 1;
    508 	for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
    509 	long long ans = 0;
    510 	for (auto it : dp) if (it.second){
    511 		long long num = it.first;
    512 		long long mx = 1;
    513 		while (num){
    514 			mx = max(mx, num % 6 + 1);
    515 			num /= 6;
    516 		}
    517 		if (mx <= k){
    518 			ans += fact[k] / fact[k - mx];
    519 		}
    520 	}
    521 	printf("%lld\n", ans);
    522 	return 0;
    523 }
    524 ```