codeforces-scrape

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

1821.md (6878B)


      1 Source: https://codeforces.com/blog/entry/115296
      2 
      3 [1821A - Matching](/contest/1821/problem/A "Educational Codeforces Round 147 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main()
     19 {
     20 	int t;
     21 	cin >> t;
     22 	for(int i = 0; i < t; i++)
     23 	{
     24 		string s;
     25 		cin >> s;
     26 		int ans = 1;
     27 		if(s[0] == '0') ans = 0;
     28 		if(s[0] == '?') ans = 9;
     29 		for(int j = 1; j < s.size(); j++)
     30 			if(s[j] == '?')
     31 				ans *= 10;
     32 		cout << ans << endl;
     33 	}
     34 }
     35 ```
     36 
     37 [1821B - Sort the Subarray](/contest/1821/problem/B "Educational Codeforces Round 147 (Rated for Div. 2)")
     38 
     39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (BledDest)**
     46 
     47 ```
     48 #include<bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 int main()
     53 {
     54 	int t;
     55 	scanf("%d", &t);
     56 	for(int i = 0; i < t; i++)
     57 	{
     58 		int n;
     59 		scanf("%d", &n);
     60 		vector<int> a(n);
     61 		for(int i = 0; i < n; i++)
     62 			scanf("%d", &a[i]);
     63 		vector<int> a1(n);
     64 		for(int i = 0; i < n; i++)
     65 			scanf("%d", &a1[i]);
     66 		int diffl = -1, diffr = -1;
     67 		for(int j = 0; j < n; j++)
     68 		{
     69 			if(a[j] != a1[j])
     70 			{
     71 				diffr = j;
     72 				if(diffl == -1)
     73 					diffl = j;
     74 			}
     75 		}
     76 		while(diffl > 0 && a1[diffl - 1] <= a1[diffl])
     77 			diffl--;
     78 		while(diffr < n - 1 && a1[diffr + 1] >= a1[diffr])
     79 			diffr++;
     80 		printf("%d %d\n", diffl + 1, diffr + 1);
     81 	}
     82 }
     83 ```
     84 
     85 [1821C - Tear It Apart](/contest/1821/problem/C "Educational Codeforces Round 147 (Rated for Div. 2)")
     86 
     87 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (awoo)**
     94 
     95 ```
     96 for _ in range(int(input())):
     97 	s = input()
     98 	n = len(s)
     99 	ans = n
    100 	for x in range(26):
    101 		c = chr(x + ord('a'))
    102 		i = 0
    103 		cur = 0
    104 		while i < n:
    105 			j = i
    106 			while j < n and (s[j] == c) == (s[i] == c):
    107 				j += 1
    108 			if s[i] != c:
    109 				cur = max(cur, j - i)
    110 			i = j
    111 		if cur == 0:
    112 			ans = 0
    113 			break
    114 		pw = 0
    115 		while (1 << pw) <= cur:
    116 			pw += 1
    117 		ans = min(ans, pw)
    118 	print(ans)
    119 ```
    120 
    121 [1821D - Black Cells](/contest/1821/problem/D "Educational Codeforces Round 147 (Rated for Div. 2)")
    122 
    123 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    124 
    125 **Tutorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Solution (adedalic)**
    130 
    131 ```
    132 fun main() {
    133     repeat(readln().toInt()) {
    134         val (n, k) = readln().split(' ').map { it.toInt() }
    135         val l = readln().split(' ').map { it.toInt() }
    136         val r = readln().split(' ').map { it.toInt() }
    137 
    138         var ans = 2e9.toInt()
    139         var cntShort = 0
    140         var lenLong = 0
    141         for (i in 0 until n) {
    142             val curLen = r[i] - l[i] + 1
    143             if(curLen > 1)
    144                 lenLong += curLen
    145             else
    146                 cntShort++
    147 
    148             if (lenLong < k) {
    149                 if (lenLong + cntShort >= k) {
    150                     val cntSegs = (i + 1 - cntShort) + (k - lenLong)
    151                     ans = minOf(ans, r[i] + 2 * cntSegs)
    152                 }
    153             }
    154             else {
    155                 ans = minOf(ans, r[i] - (lenLong - k) + 2 * (i + 1 - cntShort))
    156                 break
    157             }
    158         }
    159         if (ans == 2e9.toInt())
    160             ans = -1
    161         println(ans)
    162     }
    163 }
    164 ```
    165 
    166 [1821E - Rearrange Brackets](/contest/1821/problem/E "Educational Codeforces Round 147 (Rated for Div. 2)")
    167 
    168 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    169 
    170 **Tutorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Solution 1 (awoo)**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178 
    179 using namespace std;
    180  
    181 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    182 
    183 const long long INF64 = 1e18;
    184 
    185 long long dp[2][11][11][6];
    186 
    187 int main(){
    188 	int t;
    189 	cin >> t;
    190 	while (t--){
    191 		int k;
    192 		cin >> k;
    193 		string s;
    194 		cin >> s;
    195 		int n = s.size();
    196 		forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1) dp[0][balo][balc][mv] = INF64;
    197 		dp[0][k][k][0] = 0;
    198 		int act = 0;
    199 		forn(ii, n){
    200 			int i = ii & 1;
    201 			int ni = i ^ 1;
    202 			forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1)
    203 				dp[ni][balo][balc][mv] = INF64;
    204 			forn(mv, k + 1) forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) if (dp[i][balo][balc][mv] != INF64){
    205 				int bal = act - balo + balc;
    206 				if (balo >= 0 && mv < k)
    207 					dp[i][balo - 1][balc][mv + 1] = min(dp[i][balo - 1][balc][mv + 1], dp[i][balo][balc][mv] + bal);
    208 				if (balc >= 0 && mv < k && bal > 0)
    209 					dp[i][balo][balc - 1][mv + 1] = min(dp[i][balo][balc - 1][mv + 1], dp[i][balo][balc][mv]);
    210 				if (s[ii] == '('){
    211 					dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv] + bal);
    212 					if (balo + 1 <= 2 * k)
    213 						dp[ni][balo + 1][balc][mv] = min(dp[ni][balo + 1][balc][mv], dp[i][balo][balc][mv]);
    214 				}
    215 				else{
    216 					if (bal > 0)
    217 						dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv]);
    218 					if (balc + 1 <= 2 * k)
    219 						dp[ni][balo][balc + 1][mv] = min(dp[ni][balo][balc + 1][mv], dp[i][balo][balc][mv]);
    220 				}
    221 			}
    222 			act += (s[ii] == '(' ? 1 : -1);
    223 		}
    224 		printf("%lld\n", *min_element(dp[n & 1][k][k], dp[n & 1][k][k] + k + 1));
    225 	}
    226 }
    227 ```
    228 
    229 **Solution 2 (awoo)**
    230 
    231 ```
    232 for _ in range(int(input())):
    233 	k = int(input())
    234 	s = input()
    235 	n = len(s)
    236 	st = []
    237 	cnt = [0 for i in range(n + 1)]
    238 	ans = 0
    239 	for i in range(n):
    240 		if s[i] == '(':
    241 			ans += len(st)
    242 			st.append(i)
    243 		else:
    244 			cnt[(i - st.pop()) // 2] += 1
    245 	for i in range(n, -1, -1):
    246 		t = min(k, cnt[i])
    247 		ans -= t * i
    248 		k -= t
    249 	print(ans)
    250 ```
    251 
    252 [1821F - Timber](/contest/1821/problem/F "Educational Codeforces Round 147 (Rated for Div. 2)")
    253 
    254 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    255 
    256 **Tutorial**
    257 
    258 Tutorial is loading...
    259 
    260 **Solution (awoo)**
    261 
    262 ```
    263 #include <bits/stdc++.h>
    264  
    265 using namespace std;
    266 
    267 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    268 
    269 const int MOD = 998244353;
    270 
    271 int add(int a, int b){
    272 	a += b;
    273 	if (a >= MOD)
    274 		a -= MOD;
    275 	if (a < 0)
    276 		a += MOD;
    277 	return a;
    278 }
    279 
    280 int mul(int a, int b){
    281 	return a * 1ll * b % MOD;
    282 }
    283 
    284 int binpow(int a, int b){
    285 	int res = 1;
    286 	while (b){
    287 		if (b & 1)
    288 			res = mul(res, a);
    289 		a = mul(a, a);
    290 		b >>= 1;
    291 	}
    292 	return res;
    293 }
    294 
    295 int main(){
    296 	int n, m, k;
    297 	scanf("%d%d%d", &n, &m, &k);
    298 	
    299 	vector<int> fact(2 * n + 1), rfact(2 * n + 1);
    300 	fact[0] = 1;
    301 	for (int i = 1; i <= 2 * n; ++i) fact[i] = mul(fact[i - 1], i);
    302 	rfact[2 * n] = binpow(fact[2 * n], MOD - 2);
    303 	for (int i = 2 * n - 1; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
    304 	auto cnk = [&](int n, int k){
    305 		if (k < 0 || n < 0 || k > n) return 0;
    306 		return mul(fact[n], mul(rfact[k], rfact[n - k]));
    307 	};
    308 	auto snb = [&](int n, int k){
    309 		return cnk(n + k, k);
    310 	};
    311 	
    312 	int pw2 = 1;
    313 	int ans = 0;
    314 	for (int i = m; i >= 0; --i){
    315 		int cur = 0;
    316 		if (n - (m - i) * 1ll * (k + 1) - i * 1ll * (2 * k + 1) >= 0)
    317 			cur = mul(snb(n - (m - i) * (k + 1) - i * (2 * k + 1), m), mul(pw2, cnk(m, i)));
    318 		ans = add(ans, i & 1 ? -cur : cur);
    319 		pw2 = mul(pw2, 2);
    320 	}
    321 	
    322 	printf("%d\n", ans);
    323 }
    324 ```