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">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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>↵
↵
↵
[tutorial:1363A]↵
↵
Author of this problem was [user:Ashishgup,2020-05-31]. ↵
↵
<spoiler summary="Relevant Meme">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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">↵
↵
</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>↵
↵
