We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
- Special thanks to the tester Ajay_2705 in the last moment, correcting Problem C.
Contest Link [](https://codeforces.me/contestInvitation/701bbd9bb27890c9f44ff4ceb70e38f74e0844d6)
A — Costly Divisibility
Writer: amartya110
Editorial
Solution
#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
#define ll long long int
ll lcm(ll a, ll b) {
return (a / __gcd(a, b)) * b;
}
void solved(){
/*start*/
ll n;
cin>>n;
vector <ll> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
vector <ll> b(n);
for(int i=0;i<n;i++){
cin>>b[i];
}
ll cnt=0;
for(int i=0;i<n;i++){
if(a[i]<b[i]){
cnt+=(b[i]-a[i]);
}
}
cout<<cnt<<"\n";
/*end*/
}
int main(){
faster
testcase
solved();
}
B — String Partitioning
Writer: amartya110
Editorial
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t;
cin>>t;
while(t--){
ll n,m,k;
cin>>n>>m>>k;
string s,p;
cin>>s>>p;
int l=0,i=0;
while(l<m&&i<n){
if(s[i]==p[l]){
l++;
}
i++;
}
if(l==m){
cout<<(n-m+k-1)/k<<"\n";
}
else{
cout<<"-1\n";
}
}
}
C — The Multi-Tiered Recruitment Protocol
Writer: amartya110
Editorial
Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
void solve() {
int n , k , c;
cin >> n >> k >> c;
vector<int> a(n) , b(n);
for (int i=0;i<n;i++) {
cin >> a[i];
}
for (int i=0;i<n;i++) {
cin >> b[i];
}
map<int, map<int, int>> m;
for (int i=0;i<n;i++) {
m[b[i]][a[i]]++;
}
int ans = 0;
int tot = 0;
int g_mx = 0;
map<int, int> rem;
for (auto it : m) {
map<int, int> &group = it.second;
int sz = 0;
int mx = 0;
int dom = -1;
for (auto c_it : group) {
int cnt = c_it.second;
int cl = c_it.first;
sz += cnt;
if (cnt > mx) {
mx = cnt;
dom = cl;
}
}
if (mx > sz / 2) {
int p = sz - mx;
ans += p;
int r = sz - (2 * p);
rem[dom] += r;
tot += r;
}
else {
ans += sz / 2;
if (sz % 2 != 0) {
tot += 1;
}
}
}
for (auto r_it : rem) {
if (r_it.second > g_mx) {
g_mx = r_it.second;
}
}
int can_p = tot / 2;
if (tot - g_mx < can_p) {
can_p = tot - g_mx;
}
int bud_p = (c / k) * 2;
int paid = can_p;
if (bud_p < paid) {
paid = bud_p;
}
cout << ans + paid << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D — The Bitwise Harvest
Writer: amartya110
Editorial
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 957483783;
const int MAXB = 41;
ll dp[MAXB][2];
int bitsX[MAXB], bitsB[MAXB];
ll dfs(int pos, bool tight) {
if (pos == MAXB) return 1;
if (!tight && dp[pos][0] != -1)
return dp[pos][0];
ll res = 0;
int limit = tight ? bitsX[pos] : 1;
for (int b = 0; b <= limit; b++) {
if (bitsB[pos] && b == 0) continue;
res += dfs(pos + 1, tight && (b == limit));
}
if (!tight)
dp[pos][0] = res;
return res;
}
ll countUpTo(ll X, ll B) {
if (X < 0) return 0;
for (int i = 0; i < MAXB; i++) {
bitsX[i] = (X >> (MAXB - 1 - i)) & 1;
bitsB[i] = (B >> (MAXB - 1 - i)) & 1;
}
memset(dp, -1, sizeof(dp));
return dfs(0, 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll L, R, K;
cin >> L >> R >> K;
ll ans = 0;
vector<ll> candidates;
candidates.push_back(K);
// Generate prefix-supermasks (only 0..40 bits)
for (int i = MAXB - 1; i >= 0; i--) {
if (!(K & (1LL << i))) {
ll B = K;
B |= (1LL << i);
B &= ~((1LL << i) - 1);
if (B >= K)
candidates.push_back(B);
}
}
for (ll B : candidates) {
ll cnt = countUpTo(R, B) - countUpTo(L - 1, B);
ans = max(ans, cnt);
}
cout << (ans % MOD) << "\n";
}
return 0;
}
E — Infinite Cascades
Writer: mahesh_9996
Editorial
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int mod;
int ma(int a, int b) {return (a%mod + b%mod + mod) % mod;}
int ms(int a, int b) {return (a%mod - b%mod + mod) % mod;}
int mm(int a, int b) {return (a%mod * b%mod) % mod;}
int modexp(int base, int exp) {
int res = 1;
base %= mod;
while(exp) {
if(exp & 1) res = mm(res, base);
base = mm(base, base);
exp >>= 1;
}
return res;
}
int modinv(int x) {
return modexp(x, mod-2);
}
void solve()
{
int q;
cin >> mod >> q;
// Precompute factorials only up to mod-1
vector<int> fact(mod), invfact(mod);
fact[0] = 1;
for(int i = 1; i < mod; i++)
fact[i] = mm(fact[i-1], i);
invfact[mod-1] = modinv(fact[mod-1]);
for(int i = mod-2; i >= 0; i--)
invfact[i] = mm(invfact[i+1], i+1);
auto comb = [&](int n, int r) -> int {
if(n < 0 || r < 0 || r > n) return 0;
return mm(fact[n], mm(invfact[n-r], invfact[r]));
};
auto lucas = [&](int n, int r) -> int {
int ans = 1;
while(n > 0 || r > 0) {
ans = mm(ans, comb(n % mod, r % mod));
n /= mod;
r /= mod;
}
return ans;
};
while(q--) {
int k,l,r;
cin >> k >> l >> r;
int right = lucas(r + k + 1, k + 2);
int left = lucas(l + k, k + 2);
cout << ms(right, left) << endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
F — The Power Seeker
Writer: amartya110
Editorial
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
bool TestCases = false;
int inf = 1e18;
bool check(int i,int n) {
if(i==1) return true;
int l = 2;
int r = 1e9;
while(l<=r) {
int m = (l+r)/2;
int t = 1;
bool ok = true;
for(int j=1;j<=i;j++) {
if(t>inf/m) {
ok = false; break;
}
t*=m;
if(t>n) {
ok = false; break;
}
}
if(!ok) {
r = m-1;
}else if(t==n) {
return true;
}else {
l = m+1;
}
}
return false;
}
void solve()
{
int n; cin>>n;
for(int i=60;i>0;i--) {
if(check(i,n)) {
cout<<i;
return;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
if(TestCases)
{
cin >> t;
}
while(t--)
{
solve();
}
}
G — The Gambit
Writer: Chetan_21
Editorial
Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1000005;
vector<int> divs[MAXN];
int memo[MAXN];
void pre() {
for (int i = 1; i < MAXN; ++i) {
for (int j = 2 * i; j < MAXN; j += i) {
divs[j].push_back(i);
}
}
memset(memo, -1, sizeof(memo));
}
int get_grundy(int u) {
if (memo[u] != -1) return memo[u];
int mask = 0;
for (int v : divs[u]) {
if (u % 2 != 0) {
mask |= (1LL << get_grundy(v));
} else {
if (v % 2 == 0) {
mask |= (1LL << get_grundy(v));
}
}
}
int g = 0;
while ((mask >> g) & 1) g++;
return memo[u] = g;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
int par = 0;
int xr = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
par = (par + a[i]) % 2;
xr ^= get_grundy(a[i]);
}
if (par == 0) {
if (xr > 0) cout << "Alice\n";
else cout << "Bob\n";
}
else {
bool ok = false;
for (int x : a) {
if (x % 2 == 0) {
int target = xr ^ get_grundy(x);
for (int v : divs[x]) {
if (v % 2 != 0) {
if (get_grundy(v) == target) {
ok = true;
break;
}
}
}
}
if (ok) break;
}
if (ok) cout << "Alice\n";
else cout << "Bob\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pre();
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
H — Catalan's Convex Enigma
Writer: Lucifer_K
Editorial
Solution
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(int i=a; i<b; i++)
using vi=vector<int>;
using vii=vector<vi>;
using vpii=vector<pair<int,int>>;
#define pb push_back
int quer(int u, int v) {
cout<<"? "<<u<<" "<<v<<endl;
int ans; cin>>ans;
if (ans==-1) exit(0);
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin>>n;
vi st; vpii diag;
st.pb(1); st.pb(2);
FOR(i,3,n+1) {
while (st.size()>=2) {
int top=st.back();
int pv=st[st.size()-2];
int cut=0;
if (pv==1 && i==n) {
cut=0;
}
else {
cut=quer(pv,i);
}
if (cut==0){
if (!(pv==1 && i==n)){
diag.pb({pv,i});
}
st.pop_back();
}
else {
break;
}
}
st.pb(i);
}
cout<<"!"<<endl;
FOR(i,0,size(diag)) {
cout<<diag[i].first<<" "<<diag[i].second<<endl;
}
cout<<flush;
}
