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 is loading...
Relevant Meme
/predownloaded/5c/77/5c774366ddfa8120edea7a0d39f69d5d04d1e8a5.jpg
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;
}
Tutorial is loading...
Relevant Meme
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;
}
Tutorial is loading...
Relevant Meme
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;
}
Tutorial is loading...
Relevant Meme
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;
}
}
Tutorial is loading...
Relevant Meme
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;
}
Tutorial is loading...
Relevant Meme
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;
}
