codeforces-scrape

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

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 ![ ](/predownloaded/cd/f1/cdf13618b93c6243dec10ec495181286a2616caa.jpg)
     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 ![ ](/predownloaded/fb/d3/fbd3213de4db6e8b4b7ae9cdca4dff3ffc04ad87.jpg)
     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 ![ ](/predownloaded/42/07/42078fdea1539547c49265a7b3ad2390524bc92f.jpg)
    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 ![ ](/predownloaded/6f/0f/6f0ffffbe9795ce06c611bf2d2f0a6865c9ef0f5.jpg)
    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 ![ ](/predownloaded/7c/0d/7c0daeb4d5431c6eff54bfff2a65ef4380c38b63.jpg)
    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 ![ ](/predownloaded/32/d9/32d98cc2de57ea038a3b691d9e7cc93200c222ec.jpg)
    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 ```