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 ```