codeforces-scrape

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

711.md (11687B)


      1 Source: https://codeforces.com/blog/entry/46830
      2 
      3 Here are the editorials for all the problems. Hope you enjoyed them and found them interesting!
      4 
      5 Tutorial is loading...
      6 
      7 **Code**
      8 
      9 ```
     10 #include <bits/stdc++.h>
     11 #include <ext/pb_ds/assoc_container.hpp>
     12 #include <ext/pb_ds/tree_policy.hpp>
     13 
     14 using namespace std;
     15 using namespace __gnu_pbds;
     16 
     17 #define fi first
     18 #define se second
     19 #define mp make_pair
     20 #define pb push_back
     21 #define fbo find_by_order
     22 #define ook order_of_key
     23 
     24 typedef long long ll;
     25 typedef pair<int,int> ii;
     26 typedef vector<int> vi;
     27 typedef long double ld; 
     28 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
     29 typedef set<int>::iterator sit;
     30 typedef map<int,int>::iterator mit;
     31 typedef vector<int>::iterator vit;
     32 
     33 const int INF = 1e9 + 7;
     34 const int MOD = 1e9 + 7;
     35 const int N = 1000;
     36 char bus[N][5];
     37 
     38 void printbus(int n)
     39 {
     40 	for(int i = 0; i < n; i++)
     41 	{
     42 		for(int j = 0; j < 5; j++)
     43 		{
     44 			cout << bus[i][j];
     45 		}
     46 		cout << '\n';
     47 	}
     48 }
     49 
     50 void yes()
     51 {
     52 	cout << "YES" << '\n';
     53 }
     54 
     55 void no()
     56 {
     57 	cout << "NO" << '\n';
     58 }
     59 
     60 int main()
     61 {
     62 	ios_base::sync_with_stdio(0); cin.tie(0);
     63 	int n; cin >> n;
     64 	for(int i = 0; i < n; i++)
     65 	{
     66 		for(int j = 0; j < 5; j++)
     67 		{
     68 			cin >> bus[i][j];
     69 		}
     70 	}
     71 	bool possible = false;
     72 	for(int i = 0; i < n; i++)
     73 	{
     74 		for(int j = 0; j < 2; j++)
     75 		{
     76 			if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O')
     77 			{
     78 				bus[i][j*3] = '+';
     79 				bus[i][j*3+1] = '+';
     80 				possible = true;
     81 				break;
     82 			}
     83 		}
     84 		if(possible) break;
     85 	}
     86 	if(!possible)
     87 	{
     88 		no();
     89 		return 0;
     90 	}
     91 	else
     92 	{
     93 		yes();
     94 		printbus(n);
     95 		return 0;
     96 	}
     97 	return 0;
     98 }
     99 ```
    100 
    101 Tutorial is loading...
    102 
    103 **Code**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107 #include <ext/pb_ds/assoc_container.hpp>
    108 #include <ext/pb_ds/tree_policy.hpp>
    109 
    110 using namespace std;
    111 using namespace __gnu_pbds;
    112 
    113 #define fi first
    114 #define se second
    115 #define mp make_pair
    116 #define pb push_back
    117 #define fbo find_by_order
    118 #define ook order_of_key
    119 
    120 typedef long long ll;
    121 typedef pair<int,int> ii;
    122 typedef vector<int> vi;
    123 typedef long double ld; 
    124 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    125 typedef set<int>::iterator sit;
    126 typedef map<int,int>::iterator mit;
    127 typedef vector<int>::iterator vit;
    128 
    129 const int INF = 1e9 + 7;
    130 const int MOD = 1e9 + 7;
    131 const int LG = 20;
    132 
    133 ll a[1001][1001];
    134 ll r[1001]; //row sum
    135 ll c[1001]; //column sum
    136 int n;
    137 
    138 void no()
    139 {
    140 	cout << -1 << '\n';
    141 }
    142 
    143 int main()
    144 {
    145 	ios_base::sync_with_stdio(0); cin.tie(0);
    146 	cin >> n;
    147 	int x, y; ll diagonal1 = 0; ll diagonal2 = 0;
    148 	for(int i = 0; i < n; i++)
    149 	{
    150 		for(int j = 0; j < n; j++)
    151 		{
    152 			cin >> a[i][j];
    153 			if(a[i][j] == 0)
    154 			{
    155 				x = i; y = j;
    156 			}
    157 			else
    158 			{
    159 				r[i] += a[i][j];
    160 				c[j] += a[i][j];
    161 				if(i == j)
    162 				{
    163 					diagonal1 += a[i][j];
    164 				}
    165 				if(i + j == n - 1)
    166 				{
    167 					diagonal2 += a[i][j];
    168 				}
    169 			}
    170 		}
    171 	}
    172 	if(n == 1)
    173 	{
    174 		cout << 1 << '\n';
    175 		return 0;
    176 	}
    177 	ll commonsum = r[0];
    178 	if(x == 0) commonsum = r[1];
    179 	//cout << commonsum << '\n';
    180 	ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1;
    181 	for(int i = 0; i < n; i++)
    182 	{
    183 		if(i != x)
    184 		{
    185 			if(r[i] != commonsum)
    186 			{
    187 				no();
    188 				return 0;
    189 			}
    190 		}
    191 		else
    192 		{
    193 			rowsum = r[i];
    194 		}
    195 	}
    196 	for(int i = 0; i < n; i++)
    197 	{
    198 		if(i != y)
    199 		{
    200 			if(c[i] != commonsum)
    201 			{
    202 				no(); return 0;
    203 			}
    204 		}
    205 		else
    206 		{
    207 			colsum = c[i];
    208 		}
    209 	}
    210 	bool isdiagonal1 = false; bool isdiagonal2 = false;
    211 	if(x == y) isdiagonal1 = true;
    212 	if(x + y == n - 1) isdiagonal2 = true;
    213 	if(!isdiagonal1)
    214 	{
    215 		if(diagonal1 != commonsum)
    216 		{
    217 			no();
    218 			return 0;
    219 		}
    220 	}
    221 	else
    222 	{
    223 		d1sum = diagonal1;
    224 	}
    225 	if(!isdiagonal2)
    226 	{
    227 		if(diagonal2 != commonsum)
    228 		{
    229 			no();
    230 			return 0;
    231 		}
    232 	}
    233 	else
    234 	{
    235 		d2sum = diagonal2;
    236 	}
    237 	if(rowsum == colsum)
    238 	{
    239 		if(isdiagonal1 && d1sum != rowsum)
    240 		{
    241 			no();
    242 			return 0;
    243 		}
    244 		if(isdiagonal2 && d2sum != rowsum)
    245 		{
    246 			no();
    247 			return 0;
    248 		}
    249 		ll value = commonsum - rowsum;
    250 		if(value > 0)
    251 		{
    252 			cout << value << '\n';
    253 			return 0;
    254 		}
    255 		else
    256 		{
    257 			no();
    258 			return 0;
    259 		}
    260 	}
    261 	else
    262 	{
    263 		no();
    264 		return 0;
    265 	}
    266 }
    267 ```
    268 
    269 Tutorial is loading...
    270 
    271 **Code (O(nkm^2))**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275 #include <ext/pb_ds/assoc_container.hpp>
    276 #include <ext/pb_ds/tree_policy.hpp>
    277  
    278 using namespace std;
    279 using namespace __gnu_pbds;
    280  
    281 #define fi first
    282 #define se second
    283 #define mp make_pair
    284 #define pb push_back
    285 #define fbo find_by_order
    286 #define ook order_of_key
    287  
    288 typedef long long ll;
    289 typedef pair<int,int> ii;
    290 typedef vector<int> vi;
    291 typedef long double ld; 
    292 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    293 typedef set<int>::iterator sit;
    294 typedef map<int,int>::iterator mit;
    295 typedef vector<int>::iterator vit;
    296 
    297 const int N = 101;
    298 const int MOD = 1e9 + 7;
    299 const ll INF = ll(1e18);
    300 
    301 ll dp[N][N][N];
    302 int c[N];
    303 ll cost[N][N];
    304 
    305 int main()
    306 {
    307 	ios_base::sync_with_stdio(0); cin.tie(0);
    308 	int n, m, k; cin >> n >> m >> k;
    309 	for(int i = 1; i <= n; i++)
    310 	{
    311 		cin >> c[i];
    312 	}
    313 	for(int i = 0; i <= n; i++)
    314 	{
    315 		for(int j = 0; j <= k; j++)
    316 		{
    317 			for(int a = 0; a <= m; a++)
    318 			{
    319 				dp[i][j][a] = INF;
    320 			}
    321 		}
    322 	}
    323 	for(int i = 1; i <= n; i++)
    324 	{
    325 		for(int j = 1; j <= m; j++)
    326 		{
    327 			cin >> cost[i][j];
    328 		}
    329 	}
    330 	if(c[1] == 0)
    331 	{
    332 		for(int i = 1; i <= m; i++)
    333 		{
    334 			dp[1][1][i] = cost[1][i];
    335 		}
    336 	}
    337 	else
    338 	{
    339 		dp[1][1][c[1]] = 0;
    340 	}
    341 	for(int i = 2; i <= n; i++)
    342 	{
    343 		for(int j = 1; j <= k; j++)
    344 		{
    345 			if(c[i] == 0)
    346 			{
    347 				for(int a = 1; a <= m; a++)
    348 				{
    349 					dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
    350 					for(int b = 1; b <= m; b++)
    351 					{
    352 						if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]);
    353 					}
    354 				}
    355 			}
    356 			else
    357 			{
    358 				dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
    359 				for(int b = 1; b <= m; b++)
    360 				{
    361 					if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
    362 				}
    363 				//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
    364 			}
    365 		}
    366 	}
    367 	ll ans = INF;
    368 	for(int i = 1; i <= m; i++)
    369 	{
    370 		ans = min(ans, dp[n][k][i]);
    371 	}
    372 	if(ans >= INF) ans = -1;
    373 	cout << ans;
    374 }
    375 ```
    376 
    377 **Code (O(nkm))**
    378 
    379 ```
    380 #include <bits/stdc++.h>
    381 #include <ext/pb_ds/assoc_container.hpp>
    382 #include <ext/pb_ds/tree_policy.hpp>
    383  
    384 using namespace std;
    385 using namespace __gnu_pbds;
    386  
    387 #define fi first
    388 #define se second
    389 #define mp make_pair
    390 #define pb push_back
    391 #define fbo find_by_order
    392 #define ook order_of_key
    393  
    394 typedef long long ll;
    395 typedef pair<int,int> ii;
    396 typedef vector<int> vi;
    397 typedef long double ld; 
    398 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    399 typedef set<int>::iterator sit;
    400 typedef map<int,int>::iterator mit;
    401 typedef vector<int>::iterator vit;
    402 
    403 const int N = 101;
    404 const int MOD = 1e9 + 7;
    405 const ll INF = ll(1e18);
    406 
    407 ll dp[N][N][N];
    408 int c[N];
    409 ll cost[N][N];
    410 ll idx[N][N];
    411 ll m1[N][N];
    412 ll m2[N][N];
    413 
    414 int main()
    415 {
    416 	ios_base::sync_with_stdio(0); cin.tie(0);
    417 	int n, m, k; cin >> n >> m >> k;
    418 	for(int i = 1; i <= n; i++)
    419 	{
    420 		cin >> c[i];
    421 	}
    422 	for(int i = 0; i <= n; i++)
    423 	{
    424 		for(int j = 0; j <= k; j++)
    425 		{
    426 			m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1;
    427 			for(int a = 0; a <= m; a++)
    428 			{
    429 				dp[i][j][a] = INF;
    430 			}
    431 		}
    432 	}
    433 	for(int i = 1; i <= n; i++)
    434 	{
    435 		for(int j = 1; j <= m; j++)
    436 		{
    437 			cin >> cost[i][j];
    438 		}
    439 	}
    440 	if(c[1] == 0)
    441 	{
    442 		for(int i = 1; i <= m; i++)
    443 		{
    444 			dp[1][1][i] = cost[1][i];
    445 			if(dp[1][1][i] <= m1[1][1])
    446 			{
    447 				if(dp[1][1][i] == m1[1][1])
    448 				{
    449 					idx[1][1] = -2;
    450 				}
    451 				else
    452 				{
    453 					idx[1][1] = i;
    454 				}
    455 				m2[1][1] = m1[1][1];
    456 				m1[1][1] = dp[1][1][i];
    457 			}
    458 			else if(dp[1][1][i] <= m2[1][1])
    459 			{
    460 				m2[1][1] = dp[1][1][i];
    461 			}
    462 		}
    463 	}
    464 	else
    465 	{
    466 		dp[1][1][c[1]] = 0;
    467 		m1[1][1] = 0; idx[1][1] = c[1];
    468 	}
    469 	for(int i = 2; i <= n; i++)
    470 	{
    471 		for(int j = 1; j <= k; j++)
    472 		{
    473 			if(c[i] == 0)
    474 			{
    475 				for(int a = 1; a <= m; a++)
    476 				{
    477 					dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
    478 					ll tmp = INF;
    479 					if(a == idx[i-1][j-1])
    480 					{
    481 						tmp = m2[i-1][j-1];
    482 					}
    483 					else
    484 					{
    485 						tmp = m1[i-1][j-1];
    486 					}
    487 				    dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]);
    488 				}
    489 			}
    490 			else
    491 			{
    492 				dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
    493 				for(int b = 1; b <= m; b++)
    494 				{
    495 					if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
    496 				}
    497 				//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
    498 			}
    499 			for(int a = 1; a <= m; a++)
    500 			{
    501 				if(dp[i][j][a] <= m1[i][j])
    502 				{
    503 					if(dp[i][j][a] == m1[i][j])
    504 					{
    505 						idx[i][j] = -2;
    506 					}
    507 					else
    508 					{
    509 						idx[i][j] = a;
    510 					}
    511 					m2[i][j] = m1[i][j];
    512 					m1[i][j] = dp[i][j][a];
    513 				}
    514 				else if(dp[i][j][a] <= m2[i][j])
    515 				{
    516 					m2[i][j] = dp[i][j][a];
    517 				}
    518 			}
    519 		}
    520 	}
    521 	ll ans = INF;
    522 	for(int i = 1; i <= m; i++)
    523 	{
    524 		ans = min(ans, dp[n][k][i]);
    525 	}
    526 	if(ans >= INF) ans = -1;
    527 	cout << ans;
    528 }
    529 ```
    530 
    531 Tutorial is loading...
    532 
    533 **Code**
    534 
    535 ```
    536 #include <bits/stdc++.h>
    537 #include <ext/pb_ds/assoc_container.hpp>
    538 #include <ext/pb_ds/tree_policy.hpp>
    539 
    540 using namespace std;
    541 using namespace __gnu_pbds;
    542 
    543 #define fi first
    544 #define se second
    545 #define mp make_pair
    546 #define pb push_back
    547 #define fbo find_by_order
    548 #define ook order_of_key
    549 
    550 typedef long long ll;
    551 typedef pair<int,int> ii;
    552 typedef vector<int> vi;
    553 typedef long double ld; 
    554 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    555 typedef set<int>::iterator sit;
    556 typedef map<int,int>::iterator mit;
    557 typedef vector<int>::iterator vit;
    558 
    559 const int INF = 1e9 + 7;
    560 const int MOD = 1e9 + 7;
    561 const int N = 1e6 + 3;
    562 
    563 int a[N];
    564 int visited[N];
    565 ll ans;
    566 vector<int> cycles;
    567 ll dp[N];
    568 int cyclecnt;
    569 
    570 void dfs2(int u)
    571 {
    572 	cycles[cyclecnt]++;
    573 	visited[u] = 3;
    574 	if(visited[a[u]] == 3) return ;
    575 	dfs2(a[u]);
    576 }
    577 
    578 void dfs(int u)
    579 {
    580 	visited[u] = 2;
    581 	if(visited[a[u]] == 0)
    582 	{
    583 		dfs(a[u]);
    584 	}
    585 	else if(visited[a[u]] == 1)
    586 	{
    587 		visited[u] = 1;
    588 		return ;
    589 	}
    590 	else
    591 	{
    592 		cycles.pb(0);
    593 		dfs2(u);
    594 		cyclecnt++;
    595 	}
    596 	visited[u] = 1;
    597 }
    598 
    599 int main()
    600 {
    601 	//ios_base::sync_with_stdio(0); cin.tie(0);
    602 	int n; scanf("%d", &n);
    603 	for(int i = 1; i <= n; i++)
    604 	{
    605 		scanf("%d", a + i);
    606 	}
    607 	dp[0] = 1;
    608 	for(int i = 1; i <= n; i++)
    609 	{
    610 		dp[i] = (dp[i-1]*2LL)%MOD;
    611 	}
    612 	ans = 1;
    613 	memset(visited, 0, sizeof(visited));
    614 	for(int i = 1; i <= n; i++)
    615 	{
    616 		if(visited[i] == 0)
    617 		{
    618 			dfs(i);
    619 		}
    620 	}
    621 	ll cnt = n;
    622 	for(int i = 0; i < cycles.size(); i++)
    623 	{
    624 		cnt -= cycles[i];
    625 		ans = (ans*(dp[cycles[i]]-2+MOD))%MOD;
    626 	}
    627 	ans = (ans*dp[cnt])%MOD;
    628 	if(ans < 0) ans += MOD;
    629 	int ans2 = ans;
    630 	printf("%d\n", ans2);
    631 	return 0;
    632 }
    633 ```
    634 
    635 Tutorial is loading...
    636 
    637 **Code**
    638 
    639 ```
    640 #include <bits/stdc++.h>
    641 
    642 using namespace std;
    643 
    644 typedef long long ll;
    645 typedef vector<int> vi;
    646 
    647 const int MOD = 1e6 + 3;
    648 
    649 ll power(ll base, ll exp)
    650 {
    651 	ll ans = 1;
    652     while(exp)
    653     {
    654 		if(exp&1) ans = (ans*base)%MOD;
    655 		base = (base*base)%MOD;
    656 		exp>>=1;
    657 	}
    658     return ans;
    659 }
    660 
    661 int main()
    662 {
    663 	ios_base::sync_with_stdio(false); cin.tie(0);
    664 	ll n, k;
    665 	cin >> n >> k;
    666 	if(n <= 63 && k > (1LL<<n))
    667 	{
    668 		cout << 1 << " " << 1;
    669 		return 0;
    670 	}
    671 	ll v2 = 0;
    672 	int digits = __builtin_popcountll(k - 1);
    673 	v2 = k - 1 - digits;
    674 	ll ntmp = n % (MOD - 1);
    675 	if(ntmp < 0) ntmp += (MOD - 1);
    676 	ll ktmp = k % (MOD - 1);
    677 	if(ktmp < 0) ktmp += (MOD - 1);
    678 	ll v2tmp = v2 % (MOD - 1);
    679 	if(v2tmp < 0) v2tmp += (MOD - 1);
    680 	ll exponent = ntmp*(ktmp - 1) - v2tmp;
    681 	exponent %= (MOD - 1);
    682 	if(exponent < 0) exponent += MOD - 1;
    683 	ll denom = power(2, exponent);
    684 	ll numpart = 0;
    685 	if(k - 1 >= MOD)
    686 	{
    687 		numpart = 0;
    688 	}
    689 	else
    690 	{
    691 		ll prod = 1;
    692 		ll ntmp2 = power(2, ntmp);
    693 		prod = power(2, v2tmp);
    694 		prod = power(prod, MOD - 2);
    695 		if(prod < 0) prod += MOD;
    696 		for(ll y = 1; y <= k - 1; y++)
    697 		{
    698 			prod = (prod * (ntmp2 - y))%MOD;
    699 		}
    700 		numpart = prod;
    701 	}
    702 	ll num = (denom - numpart)%MOD;
    703 	num %= MOD; denom %= MOD;
    704 	if(num < 0) num += MOD;
    705 	if(denom < 0) denom += MOD;
    706 	cout << num << " " << denom;
    707 	return 0;
    708 }
    709 ```