1363.md (7125B)
1 Source: https://codeforces.com/blog/entry/78202 2 3 Hello, everyone! It was a delight for us to have you participate in our contest. We hope you enjoyed the problems! Here, we present to you the solutions of the problems. I have also prepared some memes for you to enjoy — disclaimer: not all of them were created by me. 4 5 Tutorial is loading... 6 7 Author of this problem was [Ashishgup](/profile/Ashishgup "International Master Ashishgup"). 8 9 **Relevant Meme** 10 11  12 13 **Code for A** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 20 #define endl "\n" 21 #define int long long 22 23 const int N = 2e5 + 5; 24 25 int n, x; 26 int a[N], f[2]; 27 28 int32_t main() 29 { 30 IOS; 31 int t; 32 cin >> t; 33 while(t--) 34 { 35 f[0] = f[1] = 0; 36 cin >> n >> x; 37 for(int i = 1; i <= n; i++) 38 { 39 cin >> a[i]; 40 f[a[i] % 2]++; 41 } 42 bool flag = 0; 43 for(int i = 1; i <= f[1] && i <= x; i += 2) //Fix no of odd 44 { 45 int have = f[0], need = x - i; 46 if(need <= f[0]) 47 flag = 1; 48 } 49 if(flag) 50 cout << "Yes" << endl; 51 else 52 cout << "No" << endl; 53 } 54 return 0; 55 } 56 ``` 57 58 Tutorial is loading... 59 60 Author of this problem was [Ashishgup](/profile/Ashishgup "International Master Ashishgup"). 61 62 **Relevant Meme** 63 64  65 66 **Code for B** 67 68 ``` 69 #include <bits/stdc++.h> 70 using namespace std; 71 72 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 73 #define endl "\n" 74 #define int long long 75 76 const int N = 1e5 + 5; 77 78 int32_t main() 79 { 80 IOS; 81 int t; 82 cin >> t; 83 while(t--) 84 { 85 string s; 86 cin >> s; 87 int suf0 = 0, suf1 = 0; 88 for(auto &it:s) 89 { 90 suf0 += (it == '0'); 91 suf1 += (it == '1'); 92 } 93 int ans = min(suf0, suf1); //Make whole string 0/1 94 int pref0 = 0, pref1 = 0; 95 for(auto &it:s) 96 { 97 pref0 += (it == '0'), suf0 -= (it == '0'); 98 pref1 += (it == '1'), suf1 -= (it == '1'); 99 //Cost of making string 0*1* 100 ans = min(ans, pref1 + suf0); 101 //Cost of making string 1*0* 102 ans = min(ans, pref0 + suf1); 103 } 104 cout << ans << endl; 105 } 106 return 0; 107 } 108 ``` 109 110 Tutorial is loading... 111 112 Author of this problem was [TheOneYouWant](/profile/TheOneYouWant "International Master TheOneYouWant"). 113 114 **Relevant Meme** 115 116  117 118 **Code for C** 119 120 ``` 121 #include <bits/stdc++.h> 122 using namespace std; 123 124 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 125 #define endl "\n" 126 #define int long long 127 128 const int N = 2e5 + 5; 129 130 int n, x; 131 int deg[N]; 132 vector<int> g[N]; 133 134 int32_t main() 135 { 136 IOS; 137 int t; 138 cin >> t; 139 while(t--) 140 { 141 memset(deg, 0, sizeof(deg)); 142 cin >> n >> x; 143 for(int i = 1; i <= n - 1; i++) 144 { 145 int u, v; 146 cin >> u >> v; 147 deg[u]++, deg[v]++; 148 } 149 if(deg[x] <= 1) 150 cout << "Ayush" << endl; 151 else 152 { 153 if(n % 2) 154 cout << "Ashish" << endl; 155 else 156 cout << "Ayush" << endl; 157 } 158 } 159 return 0; 160 } 161 ``` 162 163 Tutorial is loading... 164 165 Author of this problem was [FastestFinger](/profile/FastestFinger "Grandmaster FastestFinger"). 166 167 **Relevant Meme** 168 169  170 171 **Code for D** 172 173 ``` 174 #include<bits/stdc++.h> 175 using namespace std; 176 177 #define vint vector<int> 178 179 int interact(vint S){ 180 cout << "? " << S.size() << ' '; 181 for(int i : S) 182 cout << i << ' '; 183 cout << endl; 184 int x; 185 cin >> x; 186 return x; 187 } 188 189 vint get_complement(vint v, int n){ 190 vint ask, occur(n + 1); 191 for(int i : v) 192 occur[i] = 1; 193 for(int i = 1; i <= n; i++) 194 if(!occur[i]) 195 ask.push_back(i); 196 return ask; 197 } 198 199 int main(){ 200 int tc; 201 cin >> tc; 202 while(tc--){ 203 int n, k; 204 cin >> n >> k; 205 vector<vint> S(k); 206 vint ans(k); 207 for(int i = 0; i < k; i++){ 208 int c; 209 cin >> c; 210 S[i].resize(c); 211 for(int j = 0; j < c; j++) 212 cin >> S[i][j]; 213 } 214 vint ask; 215 for(int i = 1; i <= n; i++) 216 ask.push_back(i); 217 int max_element = interact(ask); 218 //find subset with max element 219 int st = 0, en = k - 1; 220 while(st < en){ 221 int mid = (st + en) / 2; 222 ask.clear(); 223 for(int i = 0; i <= mid; i++) 224 for(int j : S[i]) 225 ask.push_back(j); 226 int x = interact(ask); 227 if(x == max_element) 228 en = mid; 229 else st = mid + 1; 230 } 231 ask = get_complement(S[st], n); 232 for(int i = 0; i < k; i++) 233 if(i == st) 234 ans[i] = interact(ask); 235 else ans[i] = max_element; 236 cout << "! "; 237 for(int i : ans) 238 cout << i << ' '; 239 cout << endl; 240 string correct; 241 cin >> correct; 242 } 243 } 244 ``` 245 246 Tutorial is loading... 247 248 Author of this problem was [Ashishgup](/profile/Ashishgup "International Master Ashishgup"). 249 250 **Relevant Meme** 251 252  253 254 **Code for E** 255 256 ``` 257 #include <bits/stdc++.h> 258 using namespace std; 259 260 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 261 #define endl "\n" 262 #define int long long 263 264 const int N = 2e5 + 5; 265 266 int n, cost = 0; 267 int arr[N], b[N], c[N]; 268 vector<int> g[N]; 269 270 pair<int, int> dfs(int u, int par, int mn) 271 { 272 pair<int, int> a = {0, 0}; 273 if(b[u] != c[u]) 274 { 275 if(b[u]) 276 a.first++; 277 else 278 a.second++; 279 } 280 for(auto &it:g[u]) 281 { 282 if(it == par) 283 continue; 284 pair<int, int> p = dfs(it, u, min(mn, arr[u])); 285 a.first += p.first; 286 a.second += p.second; 287 } 288 if(arr[u] < mn) 289 { 290 int take = min(a.first, a.second); 291 cost += 2 * take * arr[u]; 292 a.first -= take; 293 a.second -= take; 294 } 295 return a; 296 } 297 298 int32_t main() 299 { 300 IOS; 301 cin >> n; 302 for(int i = 1; i <= n; i++) 303 cin >> arr[i] >> b[i] >> c[i]; 304 for(int i = 1; i <= n - 1; i++) 305 { 306 int u, v; 307 cin >> u >> v; 308 g[u].push_back(v); 309 g[v].push_back(u); 310 } 311 pair<int, int> ans = dfs(1, 0, 2e9); 312 if(ans.first || ans.second) 313 cout << -1; 314 else 315 cout << cost; 316 return 0; 317 } 318 ``` 319 320 Tutorial is loading... 321 322 Author of this problem was [FastestFinger](/profile/FastestFinger "Grandmaster FastestFinger"). 323 324 **Relevant Meme** 325 326  327 328 **Code for F** 329 330 ``` 331 #include <bits/stdc++.h> 332 using namespace std; 333 334 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 335 #define endl "\n" 336 #define int long long 337 338 const int N = 2005; 339 340 int n; 341 string s, t; 342 int suf[26][N], suf2[26][N]; 343 int cache[N][N]; 344 345 int dp(int i, int j) 346 { 347 if(j == 0) 348 return 0; 349 int &ans = cache[i][j]; 350 if(ans != -1) 351 return ans; 352 ans = 2e9; 353 if(i > 0) 354 { 355 ans = 1 + dp(i - 1, j); 356 if(s[i - 1] == t[j - 1]) 357 ans = min(ans, dp(i - 1, j - 1)); 358 } 359 int ch = t[j - 1] - 'a'; 360 if(suf[ch][i + 1] - suf2[ch][j + 1] > 0) 361 ans = min(ans, dp(i, j - 1)); 362 return ans; 363 } 364 365 int32_t main() 366 { 367 IOS; 368 int tc; 369 cin >> tc; 370 while(tc--) 371 { 372 cin >> n >> s >> t; 373 for(int i = 0; i <= n; i++) 374 for(int j = 0; j <= n; j++) 375 cache[i][j] = -1; 376 for(int i = 0; i <= 25; i++) 377 for(int j = 0; j <= n + 1; j++) 378 suf[i][j] = suf2[i][j] = 0; 379 for(int i = n; i >= 1; i--) 380 { 381 for(int j = 0; j < 26; j++) 382 { 383 suf[j][i] = suf[j][i + 1]; 384 suf2[j][i] = suf2[j][i + 1]; 385 } 386 suf[s[i - 1] - 'a'][i]++; 387 suf2[t[i - 1] - 'a'][i]++; 388 } 389 int ans = dp(n, n); 390 if(ans > 1e9) 391 ans = -1; 392 cout << ans << endl; 393 } 394 return 0; 395 } 396 ```