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. Firstly, here are some comments about the contest:
Mid-contest, a contestant pointed out that F was the same as A in this contest. We're sorry, it was an unfortunate coincidence, and none of the setters/testers/coordinators had seen it elsewhere. Luckily, it did not affect Div-2 standings considering its difficulty, and we'll be more careful next time.
I will add stats and first-solvers for each problem as system testing happens.
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;
}
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;
}
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;
}
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;
}
}
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;
}
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;
}
