We hope that you have enjoyed this round! Here is the sketch of solutions for the problems.
A. Array and Peaks
Tutorial
Tutorial is loading...
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin>>tests;
while(tests--)
{
int n,k;
cin>>n>>k;
vector<int> ans(n+1);
int num=n;
for(int i=2;i<n;i+=2)
{
if(k==0)break;
ans[i]=num--;
k--;
}
if(k)
{
cout<<-1<<endl;
continue;
}
int cur=1;
for(int i=1;i<=n;i++)
{
if(!ans[i])
ans[i]=cur++;
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
}
B. AND Sequences
Tutorial
Tutorial is loading...
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
void solveTestCase()
{
int MOD=1e9+7;
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
int min1=*min_element(a.begin(),a.end());
int cnt=0;
for(int x:a)
{
if(min1==x)cnt++;
if((min1&x)!=min1)
{
printf("0\n");
return;
}
}
int fact=1;
for(int i=1;i<=n-2;i++)fact=(1LL*fact*i)%MOD;
int ans=(1LL * cnt * (cnt-1))%MOD;
ans = (1LL * ans * fact) % MOD;
printf("%d\n",ans);
}
int main()
{
int tests;
cin>>tests;
while(tests--)
solveTestCase();
return 0;
}
C. Add One
Tutorial
Tutorial is loading...
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int max_n = 200005, mod = 1000000007;
int dp[max_n];
signed main(){
for(int i=0; i<9; i++)dp[i] = 2;
dp[9] = 3;
for(int i=10; i<max_n; i++){
dp[i] = (dp[i-9] + dp[i-10])%mod;
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
int ans = 0;
while(n > 0){
int x = n%10;
ans += ((m + x < 10) ? 1 : dp[m + x - 10]);
ans %= mod;
n/=10;
}
cout<<ans<<"\n";
}
return 0;
}
D. GCD and MST
Tutorial
Tutorial is loading...
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
void solveTestCase()
{
int n,x;
cin>>n>>x;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
//tells whether vertices i and i+1 are connected for 0<=i<n-1
vector<bool> isConnected(n);
vector<pair<int,int>> vals;
for(int i=0;i<n;i++)
vals.push_back(make_pair(a[i],i));
sort(vals.begin(),vals.end());
long long int ans=0;
for(auto p:vals)
{
int cur_val=p.first;
int i=p.second;
if(cur_val>=x)break;
while(i>0)
{
if(isConnected[i-1])break;
if(a[i-1]%cur_val==0)
{
isConnected[i-1]=true;
ans+=cur_val;
i--;
}
else
break;
}
i=p.second;
while(i<n-1)
{
if(isConnected[i])break;
if(a[i+1]%cur_val==0)
{
isConnected[i]=true;
ans+=cur_val;
i++;
}
else
break;
}
}
for(int i=0;i<n-1;i++)
{
if(!isConnected[i])
ans+=x;
}
cout<<ans<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solveTestCase();
}
return 0;
}
E. Cost Equilibrium
Tutorial
Tutorial is loading...
Implementation in C++
#include "bits/stdc++.h"
#define ll long long
#define MOD 1000000007
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
using namespace std;
#define int long long
#define MAX 100005
vector<int> f(MAX);
vector<int> inv(MAX);
void init() {
f[0] = 1;
for(int i=1;i<MAX;i++) f[i] = (f[i-1]*i)%MOD;
inv[MAX-1] = power(f[MAX-1], MOD-2, MOD);
for(int i=MAX-2;i>=0;i--) inv[i] = (inv[i+1]*(i+1)) % MOD;
for(int i=0;i<MAX;i++) assert(inv[i]==power(f[i],MOD-2,MOD));
}
int ncr(int n, int r) {
if(r > n || r < 0) return 0;
int ans = f[n];
ans *= (inv[r] * inv[n - r]) % MOD;
ans %= MOD;
return ans;
}
int solve(const vector<int> &v) {
int n = v.size();
int s = 0;
for(auto x: v) s += x;
if(!(s % n == 0)) return 0;
int src = 0;
int snk = 0;
map<int,int> freqSrc, freqSnk;
for(auto x: v) {
if(s / n < x) {
freqSrc[x]++;
src ++;
}
if(s / n > x) {
freqSnk[x]++;
snk ++;
}
}
if(src == 0 && snk == 0) return 1;
if(src == 1 || snk == 1) {
int ans = f[n];
for(auto x: freqSnk) {
ans = (ans * inv[x.second]) % MOD;
}
for(auto x: freqSrc) {
ans = (ans * inv[x.second]) % MOD;
}
ans *= inv[n - src - snk];
ans %= MOD;
return ans;
}
int ans = (2 * f[src] * f[snk]) % MOD;
// Divide by freq of repeating elements
for(auto x: freqSnk) {
ans = (ans * inv[x.second]) % MOD;
}
for(auto x: freqSrc) {
ans = (ans * inv[x.second]) % MOD;
}
int tot = src + snk;
int left = n - tot;
// Number of Solution: x_0 + x_1 + x_2 + ... + x_tot = left
ans = (ans * ncr(left + tot, tot)) % MOD;
return ans;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
init();
int n;
cin>>n;
vector<int> v(n);
for(auto &x: v) cin>>x;
cout<<solve(v);
}
F. Swapping Problem
Tutorial
Tutorial is loading...
Implementation1 in C++
#include "bits/stdc++.h"
#define ll long long
#define MOD 1000000007
#define inf 1000000000000000000LL
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin>>n;
vector<int> a(n), b(n);
for(auto &x: a) cin>>x;
for(auto &x: b) cin>>x;
map<int,int> segX, segY;
for(int i=0;i<n;i++) {
if(a[i]<=b[i]) {
if(!segX.count(a[i])) segX[a[i]] = b[i];
else segX[a[i]] = max(segX[a[i]], b[i]);
}
else {
if(!segY.count(b[i])) segY[b[i]] = a[i];
else segY[b[i]] = max(segY[b[i]], a[i]);
}
}
// Construct prefix maxima
int mx = -inf;
for(auto &x: segX) {
mx = max(mx, x.second);
x.second = mx;
}
mx = -inf;
for(auto &x: segY) {
mx = max(mx, x.second);
x.second = mx;
}
// Find best swap
int mxGain = 0;
for(int i=0;i<n;i++) {
if(a[i]<=b[i]) {
auto it = segY.upper_bound(a[i]);
if(it==segY.begin()) continue;
it--;
int overlap = min(it->second, b[i]) - a[i];
mxGain = max(mxGain, 2*overlap);
}
else {
auto it = segX.upper_bound(b[i]);
if(it==segX.begin()) continue;
it--;
int overlap = min(it->second, a[i]) - b[i];
mxGain = max(mxGain, 2*overlap);
}
}
// Find ans = initial val - mxGain
int ans = 0;
for(int i=0;i<n;i++) {
ans += abs(a[i]-b[i]);
}
ans -= mxGain;
cout<<ans;
}
Implementation2 in C++
// created by mtnshh
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e18;
#define PI 3.14159265
const ll N = 100005;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
cin >> n;
ll A[n], B[n];
rep(i,0,n) cin >> A[i];
rep(i,0,n) cin >> B[i];
Vpll x1, x2, y1, y2;
ll ans = 0;
rep(i,0,n){
ans += abs(A[i]-B[i]);
if(A[i]<B[i]){
x1.pb({A[i], B[i]});
x2.pb({B[i], A[i]});
}
else{
y1.pb({A[i], B[i]});
y2.pb({B[i], A[i]});
}
}
ll fin = ans;
//
set<ll> s1;
sort(all(x1));
sort(all(y2));
ll cur1 = 0;
for(auto i: x1){
while(cur1 < y2.size() and y2[cur1].ft <= i.ft){
s1.insert(y2[cur1].sd);
cur1++;
}
if(s1.size() > 0){
ll last = *s1.rbegin();
fin = min(fin, ans - 2 * (min(i.sd, last) - i.ft));
}
}
set<ll> s2;
sort(all(x1));
sort(all(y2));
ll cur2 = 0;
for(auto i: y2){
while(cur2 < x1.size() and x1[cur2].ft <= i.ft){
s2.insert(x1[cur2].sd);
cur2++;
}
if(s2.size() > 0){
ll last = *s2.rbegin();
fin = min(fin, ans - 2 * (min(last, i.sd) - i.ft));
}
}
cout << fin << endl;
return 0;
}