Editorial — Codeforces Round #646
Разница между en7 и en8, 0 символ(ов) изменены
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.↵

[tutorial:1363A]↵

Author of this problem was [user:Ashishgup,2020-05-31]. ↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/cd/f1/cdf13618b93c6243dec10ec495181286a2616caa.jpg)↵
</spoiler>↵

<spoiler summary="Code for A">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
#define endl "\n"↵
#define int long long↵
 ↵
const int N = 2e5 + 5;↵
 ↵
int n, x;↵
int a[N], f[2];↵
 ↵
int32_t main()↵
{↵
IOS;↵
int t;↵
cin >> t;↵
while(t--)↵
{↵
    f[0] = f[1] = 0;↵
     cin >> n >> x;↵
     for(int i = 1; i <= n; i++)↵
     {↵
     cin >> a[i];↵
     f[a[i] % 2]++;↵
     }↵
     bool flag = 0;↵
     for(int i = 1; i <= f[1] && i <= x; i += 2) //Fix no of odd↵
     {↵
     int have = f[0], need = x - i;↵
     if(need <= f[0])↵
             flag = 1;↵
     }↵
     if(flag)↵
         cout << "Yes" << endl;↵
     else↵
         cout << "No" << endl;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1363B]↵

Author of this problem was [user:Ashishgup,2020-05-31]. ↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/fb/d3/fbd3213de4db6e8b4b7ae9cdca4dff3ffc04ad87.jpg)↵
</spoiler>↵

<spoiler summary="Code for B">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
#define endl "\n"↵
#define int long long↵
 ↵
const int N = 1e5 + 5;↵
 ↵
int32_t main()↵
{↵
IOS;↵
int t;↵
cin >> t;↵
while(t--)↵
{↵
string s;↵
cin >> s;↵
int suf0 = 0, suf1 = 0;↵
for(auto &it:s)↵
{↵
suf0 += (it == '0');↵
suf1 += (it == '1');↵
}↵
int ans = min(suf0, suf1); //Make whole string 0/1↵
int pref0 = 0, pref1 = 0;↵
for(auto &it:s)↵
{↵
pref0 += (it == '0'), suf0 -= (it == '0');↵
pref1 += (it == '1'), suf1 -= (it == '1');↵
//Cost of making string 0*1*↵
ans = min(ans, pref1 + suf0);↵
//Cost of making string 1*0*↵
ans = min(ans, pref0 + suf1);↵
}↵
cout << ans << endl;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1363C]↵

Author of this problem was [user:TheOneYouWant,2020-05-31].↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/42/07/42078fdea1539547c49265a7b3ad2390524bc92f.jpg)↵
</spoiler>↵

<spoiler summary="Code for C">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
#define endl "\n"↵
#define int long long↵
 ↵
const int N = 2e5 + 5;↵
 ↵
int n, x;↵
int deg[N];↵
vector<int> g[N];↵
 ↵
int32_t main()↵
{↵
IOS;↵
int t;↵
cin >> t;↵
while(t--)↵
{↵
memset(deg, 0, sizeof(deg));↵
cin >> n >> x;↵
for(int i = 1; i <= n - 1; i++)↵
{↵
int u, v;↵
cin >> u >> v;↵
deg[u]++, deg[v]++;↵
}↵
if(deg[x] <= 1)↵
cout << "Ayush" << endl;↵
else↵
{↵
if(n % 2)↵
cout << "Ashish" << endl;↵
else↵
cout << "Ayush" << endl;↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1363D]↵

Author of this problem was [user:FastestFinger,2020-05-31].↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/6f/0f/6f0ffffbe9795ce06c611bf2d2f0a6865c9ef0f5.jpg)↵
</spoiler>↵

<spoiler summary="Code for D">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
 ↵
#define vint vector<int>↵
 ↵
int interact(vint S){↵
cout << "? " << S.size() << ' ';↵
for(int i : S)↵
cout << i << ' ';↵
cout << endl;↵
int x;↵
cin >> x;↵
return x;↵
}↵
 ↵
vint get_complement(vint v, int n){↵
vint ask, occur(n + 1);↵
for(int i : v)↵
occur[i] = 1;↵
for(int i = 1; i <= n; i++)↵
if(!occur[i])↵
ask.push_back(i);↵
return ask;↵
}↵
 ↵
int main(){↵
int tc;↵
cin >> tc;↵
while(tc--){↵
int n, k;↵
cin >> n >> k;↵
vector<vint> S(k);↵
vint ans(k);↵
for(int i = 0; i < k; i++){↵
int c;↵
cin >> c;↵
S[i].resize(c);↵
for(int j = 0; j < c; j++)↵
cin >> S[i][j];↵
}↵
vint ask;↵
for(int i = 1; i <= n; i++)↵
ask.push_back(i);↵
int max_element = interact(ask);↵
//find subset with max element↵
int st = 0, en = k - 1;↵
while(st < en){↵
int mid = (st + en) / 2;↵
ask.clear();↵
for(int i = 0; i <= mid; i++)↵
for(int j : S[i])↵
ask.push_back(j);↵
int x = interact(ask);↵
if(x == max_element)↵
en = mid;↵
else st = mid + 1;↵
}↵
ask = get_complement(S[st], n);↵
for(int i = 0; i < k; i++)↵
if(i == st)↵
ans[i] = interact(ask);↵
else ans[i] = max_element;↵
cout << "! ";↵
for(int i : ans)↵
cout << i << ' ';↵
cout << endl;↵
string correct;↵
cin >> correct;↵
}↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1363E]↵

Author of this problem was [user:Ashishgup,2020-05-31]. ↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/7c/0d/7c0daeb4d5431c6eff54bfff2a65ef4380c38b63.jpg)↵
</spoiler>↵

<spoiler summary="Code for E">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
#define endl "\n"↵
#define int long long↵
 ↵
const int N = 2e5 + 5;↵
 ↵
int n, cost = 0;↵
int arr[N], b[N], c[N];↵
vector<int> g[N];↵
 ↵
pair<int, int> dfs(int u, int par, int mn)↵
{↵
pair<int, int> a = {0, 0};↵
if(b[u] != c[u])↵
{↵
if(b[u])↵
a.first++;↵
else↵
a.second++;↵
}↵
for(auto &it:g[u])↵
{↵
if(it == par)↵
continue;↵
pair<int, int> p = dfs(it, u, min(mn, arr[u]));↵
a.first += p.first;↵
a.second += p.second;↵
}↵
if(arr[u] < mn)↵
{↵
int take = min(a.first, a.second);↵
cost += 2 * take * arr[u];↵
a.first -= take;↵
a.second -= take;↵
}↵
return a;↵
}↵
 ↵
int32_t main()↵
{↵
IOS;↵
cin >> n;↵
for(int i = 1; i <= n; i++)↵
cin >> arr[i] >> b[i] >> c[i];↵
for(int i = 1; i <= n - 1; i++)↵
{↵
int u, v;↵
cin >> u >> v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
} ↵
pair<int, int> ans = dfs(1, 0, 2e9);↵
if(ans.first || ans.second)↵
cout << -1;↵
else↵
cout << cost;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1363F]↵

Author of this problem was [user:FastestFinger,2020-05-31].↵

<spoiler summary="Relevant Meme">↵
![ ](/predownloaded/32/d9/32d98cc2de57ea038a3b691d9e7cc93200c222ec.jpg)↵
</spoiler>↵

<spoiler summary="Code for F">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
#define endl "\n"↵
#define int long long↵
 ↵
const int N = 2005;↵
 ↵
int n;↵
string s, t;↵
int suf[26][N], suf2[26][N];↵
int cache[N][N];↵
 ↵
int dp(int i, int j)↵
{↵
if(j == 0)↵
return 0;↵
int &ans = cache[i][j];↵
if(ans != -1)↵
return ans;↵
ans = 2e9;↵
if(i > 0)↵
{↵
ans = 1 + dp(i - 1, j);↵
if(s[i - 1] == t[j - 1])↵
ans = min(ans, dp(i - 1, j - 1));↵
}↵
int ch = t[j - 1] - 'a';↵
if(suf[ch][i + 1] - suf2[ch][j + 1] > 0)↵
ans = min(ans, dp(i, j - 1));↵
return ans;↵
}↵
 ↵
int32_t main()↵
{↵
IOS;↵
int tc;↵
cin >> tc;↵
while(tc--)↵
{↵
memset(cache, -1, sizeof(cache));↵
cin >> n >> s >> t;↵
for(int i = 0; i <= n; i++)↵
for(int j = 0; j <= n; j++)↵
cache[i][j] = -1;↵
for(int i = 0; i <= 25; i++)↵
for(int j = 0; j <= n + 1; j++)↵
suf[i][j] = suf2[i][j] = 0;↵
for(int i = n; i >= 1; i--)↵
{↵
for(int j = 0; j < 26; j++)↵
{↵
suf[j][i] = suf[j][i + 1];↵
suf2[j][i] = suf2[j][i + 1];↵
}↵
suf[s[i - 1] - 'a'][i]++;↵
suf2[t[i - 1] - 'a'][i]++;↵
}↵
int ans = dp(n, n);↵
if(ans > 1e9)↵
ans = -1;↵
cout << ans << endl;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский TheOneYouWant 2020-06-01 09:25:41 37 Tiny change: '-)\n {\n memset(cache, -1, sizeof(cache));\n cin >>' -> '-)\n {\n cin >>'
en10 Английский TheOneYouWant 2020-05-31 20:09:09 0 (published)
en9 Английский TheOneYouWant 2020-05-31 20:08:10 0 (saved to drafts)
en8 Английский TheOneYouWant 2020-05-31 20:02:56 0 (published)
en7 Английский TheOneYouWant 2020-05-31 19:55:46 448
en6 Английский TheOneYouWant 2020-05-31 19:53:10 369
en5 Английский TheOneYouWant 2020-05-31 19:47:12 1035
en4 Английский TheOneYouWant 2020-05-31 19:38:57 122
en3 Английский TheOneYouWant 2020-05-31 19:37:05 6029
en2 Английский TheOneYouWant 2020-05-31 19:31:46 721
en1 Английский TheOneYouWant 2020-05-31 19:31:10 1549 Initial revision (saved to drafts)