Link to contest : SPC — Final Contest : )
If you can't see the tutorial then click on above link first.
A. Fruits
Problem Author : Cheata
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
vector<int>a,o,b;
for(int i=0;i<n;i++)
{
if(s[i]=='a') a.pub(i);
if(s[i]=='b') b.pub(i);
if(s[i]=='o') o.pub(i);
}
for(auto i :a) cout<<i+1<<" ";
cout<<"\n";
for(auto i :b) cout<<i+1<<" ";
cout<<"\n";
for(auto i :o) cout<<i+1<<" ";
cout<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
B. Dice Roll
Problem Author : Mantra7
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int a,b;
cin>>a>>b;
cout<< a+b+7 << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
C. Selfie with Tourist
Problem Author : kuki22102002
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long int T;
cin>>T;
while(T--)
{
long long int N,k,a,b;
long long int minimum=1e18;
cin>>N>>k>>a>>b;
long long int friends[N],diff;
for(long long int j=0;j<N;j++)
{
cin>>friends[j];
diff=abs(a-friends[j]) + abs(b-friends[j]);
minimum=min(minimum,diff);
}
cout<< minimum <<endl;
}
return 0;
}
D. Strong Arrays
Problem Author : Abdullah010
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int n; cin >> n;
int a[n];
for(int i=0; i<n; i++){
cin >> a[i];
if(a[i] >=0) a[i] = -a[i]-1;
}
int ans = 1;
if(n%2==0){
for(int i=0; i<n; i++){
a[i] = abs(a[i]);
ans = (ans*a[i])%mod;
}
cout << ans%mod << endl;
}
else{
sort(a,a+n);
a[0] = -a[0]-1;
for(int i=0; i<n; i++){
a[i] = abs(a[i]);
ans = (ans*a[i])%mod;
}
cout << ans%mod << endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
E. El Clasico
Problem Author : iowiz
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353
void solve()
{
int n; cin >> n;
int a=0,b=0;
for(int i=0; i<n; i++){
int x,y,z; cin >> x >> y >> z;
if(x==1){
ya;
a = y; b= z;
}
else{
int mn1 = min(a,b);
int mx1 = max(a,b);
int mn2 = min(y,z);
int mx2 = max(y,z);
if(y==z){
ya; a=y; b=z; continue;
}
if(mn2 >= mx1){
na; continue;
}
ya;
if(a==mx1) {a = mx2; b = mn2;}
else{a = mn2; b = mx2;}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
F. Array Uniformity
Problem Author : sapta0506
Tutorial
Tutorial is loading...
Solution
#include <cmath>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define all(x) x.begin(),x.end()
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
void solve()
{
int n; cin >> n;
int s[n];
for(int i=0; i<n; i++) cin >> s[i];
map<int,int> m;
int ans = 0;
for(int i = n-1; i>=1; i--){
if(s[i]==s[i-1]){
int x = n-1-i-m[s[i]];
m.clear();
ans += x;
m[s[i]] += n-1-i;
}
m[s[i]]++;
}
cout << ans << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1; cin >> t;
while(t--) solve();
return 0;
}
G. Singleton Code (Easy Version)
Problem Author : sapta0506, KDVinit
Tutorial
Tutorial is loading...
Solution
/*
Mantra's code :)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
int sof(int x)
{
if(x/10==0) return x;
int ans=0;
while(x>0)
{
ans+=x%10;
x/=10;
}
return sof(ans);
}
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=sof(a[0]);
for(int i=1;i<n;i++)
{
ans*=a[i];
ans=sof(ans);
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
H. Singleton Code (Hard version)
Problem Author : sapta0506, KDVinit
Tutorial
Tutorial is loading...
Solution
/*
Mantra's code :)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
int sof(int x)
{
if(x/10==0) return x;
int ans=0;
while(x>0)
{
ans+=x%10;
x/=10;
}
return sof(ans);
}
void solve()
{
int n;
cin>>n;
int flag0=0;
int flag1=0;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]==0) flag0=1;
if(i>0 && a[i]>1) flag1=1;
}
if(flag0)
{
cout<<"1\n";
return;
}
int x=sof(a[0]);
if(n==1)
{
cout<<x<<"\n";
return;
}
if(x==0 || x==1 || x==9)
{
cout<<x<<"\n";
}
if(x==6 || x==3)
{
if(flag1==0)
{
cout<<x<<"\n";
}
else
{
cout<<"9\n";
}
}
if(x==8)
{
int rem=a[1]%2;
for(int i=2;i<n;i++)
{
rem*=(a[i]%2);
}
if(rem==0) cout<<"1\n";
else cout<<"8\n";
}
if(x==4 || x==7)
{
int rem=a[1]%3;
for(int i=2;i<n;i++)
{
rem*=(a[i]%3);
rem%=3;
}
if(rem==2) cout<<(x==4 ? 7 : 4)<<"\n";
if(rem==1) cout<<(x==4 ? 4 : 7)<<"\n";
if(rem==0) cout<<(x==4 ? 1 : 1)<<"\n";
}
if(x==2 || x==5)
{
int rem=a[1]%6;
for(int i=2;i<n;i++)
{
rem*=(a[i]%6);
rem%=6;
}
if(rem==5) cout<<(x==2 ? 5 : 2)<<"\n";
if(rem==4) cout<<(x==2 ? 7 : 4)<<"\n";
if(rem==3) cout<<(x==2 ? 8 : 8)<<"\n";
if(rem==2) cout<<(x==2 ? 4 : 7)<<"\n";
if(rem==1) cout<<(x==2 ? 2 : 5)<<"\n";
if(rem==0) cout<<(x==2 ? 1 : 1)<<"\n";
}
return;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
I. Find The String
Problem Author : Mantra7
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
#define Fact_Length 500001 //Max length here is 519160
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int a,int b)
{
int result=1; a%=mod;
while(b) { if(b%2==1) result*=a; a*=a; a%=mod; result%=mod; b/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int a)
{
a%=mod; a=Power(a,mod-2); return a;
}
int Factorial[Fact_Length];
/** It make the above Factorial array to i! array**/
int Make_Factorial()
{
Factorial[0]=1;
for(int i=1;i<Fact_Length;i++) { Factorial[i]=i*Factorial[i-1]; Factorial[i]%=mod; } return 0;
}
int Implement_Make_Factorial=Make_Factorial(); //To Implement Make_Factorial
void solve()
{
string s;
cin>>s;
int n=s.size();
int freq[26]={0};
for(int i=0;i<n;i++)
{
freq[s[i]-'a']++;
}
int inc=Factorial[n];
for(int j=0;j<26;j++)
{
inc*=Mod_Inv(Factorial[freq[j]]);
inc%=mod;
}
int ans=0;
for(int i=0;i<n;i++)
{
if(i!=0)
{
inc*=freq[s[i-1]-'a']+1;
inc%=mod;
}
inc*=Mod_Inv(n-i);
inc%=mod;
for(int j=0;j<s[i]-'a';j++)
{
int cur_inc=inc*freq[j];
cur_inc%=mod;
ans+=cur_inc;
ans%=mod;
}
freq[s[i]-'a']--;
}
cout<<(ans+1)%mod<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
J. Musical Chairs
Problem Author : sapta0506
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int n;
cin>>n;
int t[n];
for(int i=1;i<n;i++)
{
cin>>t[i];
}
t[0]=0;
int cur=0;
for(int i=n-1;i>0;i--)
{
int delta=t[i]-t[i-1];
delta%=(n-i+1);
int prev=(cur+1+(n-i+1)-delta)%(n-i+1);
cur=prev;
}
cout<<cur+1<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
K. Saving the Programming Club
Problem Author : AdC_AB2
Tutorial
Tutorial is loading...
Solution
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()
const ll mod = 1000000007;
#define NN 1000001
#define Fact_Length 500001 //Max length here is 519160
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
ll Power(ll aaa,ll bbb)
{
ll result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
ll Mod_Inv(ll aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}
bool prime_chk[NN];
vector<ll> p;
int sieve()
{
for(ll i=2;i<NN;i++)
{
prime_chk[i]=true;
}
prime_chk[0]=false;
prime_chk[1]=false;
for(ll i=2;i<NN;i++)
{
if(prime_chk[i]==true)
{
p.push_back(i);
for(ll j=i*i;j<NN;j+=i)
{
prime_chk[j]=false;
}
}
}
return(0);
}
void solv()
{
ll a,m;
cin>>a>>m;
map<ll,ll> ap, mp;
ll t1=a,i=0;
while(t1>1 && i<sz(p))
{
while(t1%p[i]==0)
{
ap[p[i]]++;
t1/=p[i];
}
i++;
}
ll t2=m;i=0;
while(t2>1 && i<sz(p))
{
while(t2%p[i]==0)
{
mp[p[i]]++;
t2/=p[i];
}
i++;
}
ll ans=1, pro=1,c=1;
ll tt;
for(ll i=0; i<sz(p); i++)
{
if(ap[p[i]]>mp[p[i]])
{
pro*=Power(p[i],ap[p[i]]);
pro%=mod;
}
else if(mp[p[i]]>0)
{
tt=Power(p[i],mp[p[i]]+1)-1+mod;
tt*=Mod_Inv(p[i]-1);
tt%=mod;
ans*=tt;
ans%=mod;
c*=mp[p[i]]+1;
c%=mod;
}
}
if(t1!=t2)
pro*=t1%mod;
if(t2!=1)
{
ans*=(t2+1)%mod;
c*=2;
c%=mod;
}
ans%=mod, pro%=mod;
ll ff=(ans)*(pro)-(c)*(a%mod)+mod*mod;
ff%=mod;
cout<<ff<<endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=sieve();
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
L. Can anyone solve it?
Problem Author : AdC_AB2, KDVinit
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)(a.size())
const int mod = 1000000007;
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int aaa,int bbb)
{
int result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}
int gcd(int a, int b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
int sum_pwr(int b,int p) //Computes b+b^2+b^3+...+b^p
{
int ans;
if(b==1)
{
ans=p%mod;
return ans;
}
ans=Power(b,p+1)-1+mod; ans%=mod;
ans*=Mod_Inv(b-1); ans%=mod;
ans+=mod-1; ans%=mod;
return ans;
}
int AGP(int b,int p) //Computes 1b+ 2(b^2) + 3(b^3) +...+ p(b^p)
{
int ans;
if(b==1)
{
p%=mod;
ans=p*(p+1); ans%=mod;
ans*=Mod_Inv((int)2); ans%=mod;
return ans;
}
int tmp=(p%mod)*Power(b,p+1); tmp%=mod;
tmp+=mod-sum_pwr(b,p); tmp%=mod;
tmp*=Mod_Inv(b-1);
ans=tmp%mod;
return ans;
}
void solv()
{
int n,a,b;
cin>>n>>a>>b;
int gc = gcd(a,b);
if(n>=a+b)
{
n/=gc;
int b1=Power(2,gc), b2=Power(5,gc),ans=0, tmp;
ans+=sum_pwr(b1,n); ans%=mod;
ans+=sum_pwr(b2,n); ans%=mod;
tmp=AGP(b1,n)+AGP(b2,n); tmp%=mod;
tmp*=(3*gc)%mod; tmp%=mod;
ans+=tmp;
ans%=mod;
cout<<ans<<endl;
return;
}
n = n/gc;
a = a/gc;
b = b/gc;
vector<int> vi(n+1,0);
queue<int> lvl;
if(n>=a)
{
lvl.push(a);
vi[a]=1;
}
if(n>=b && !vi[b])
{
lvl.push(b);
vi[b]=1;
}
vector<int> save;
int lvl_rn,cnt=0;
while(!lvl.empty())
{
cnt++;
lvl_rn=lvl.front();
save.push_back(lvl_rn);
lvl.pop();
if(lvl_rn+a<=n && !vi[lvl_rn+a])
{
lvl.push(lvl_rn+a);
vi[lvl_rn+a]=1;
}
if(lvl_rn-a>0 && !vi[lvl_rn-a])
{
lvl.push(lvl_rn-a);
vi[lvl_rn-a]=1;
}
if(lvl_rn+b<=n && !vi[lvl_rn+b])
{
lvl.push(lvl_rn+b);
vi[lvl_rn+b]=1;
}
if(lvl_rn-b>0 && !vi[lvl_rn-b])
{
lvl.push(lvl_rn-b);
vi[lvl_rn-b]=1;
}
}
int ans=0,cc;
int b1=Power(2,gc),b2=Power(5,gc);
for(int i=0; i<sz(save); i++)
{
cc=Power(b1,save[i])+Power(b2,save[i]); cc%=mod;
cc*=(1+3*save[i]*gc)%mod; cc%=mod;
ans+=cc; ans%=mod;
}
cout<<ans<<endl;
return;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_cases=1;
//cin>>test_cases;
for(int loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
Alternate solution to K:
Use the fact that $$$lcm(a, b) = \frac{ab}{gcd(a, b)}$$$.
Applying this to the given condition gives $$$ \frac{am}{gcd(a, m)} = \frac{(a+x)m}{gcd(a+x, m)} \implies \frac{a}{gcd(a, m)} = \frac{a+x}{gcd(a+x, m)} \implies x = \frac{a\cdot gcd(a+x, m)}{gcd(a, m)} - a$$$
So, fixing a value for $$$gcd(a+x, m)$$$ fixes the value of $$$x$$$.
$$$gcd(a+x, m)$$$ must be a factor of $$$m$$$ so try all possible factors $$$g$$$ of $$$m$$$, compute $$$x$$$ for each one, and then check if $$$gcd(a+x, m) = g$$$.
Doing it this way runs into a couple of issues:
When computing $$$x$$$, you might end up with numbers as large as $$$1e24$$$, and that clearly exceeds the range of a 64-bit integer. Multiplying them modulo $$$1e9+7$$$ isn't an option because you need the exact value of $$$x$$$ to compute $$$gcd(a+x, m)$$$.
Switching to python or any other language with support for large integers would resolve this problem, but might cause TL issues because limits are quite high.
To work around this, note that $$$gcd(a+x, m) = gcd((a+x)\%m, m)$$$, so it is enough to know $$$x$$$ modulo $$$m$$$.
Naively computing all factors in $$$\mathcal{O}(\sqrt{m})$$$ is, in the worst case, $$$1e6$$$ operations per testcase and then whatever extra computation is done with each divisor. With 1000 testcases, speed could be an issue.
One possible optimization is to use a fast prime factoring algorithm, like Pollard-rho, to find all prime factors of $$$m$$$ and then recursively generate all factors from these. This brings the complexity of the factorization part down from $$$\mathcal{O}(m^{0.5})$$$ to (expected) $$$\mathcal{O}(m^{0.25} + \sigma(m))$$$ where $$$\sigma(m)$$$ is the number of factors of $$$m$$$, which is about 7000 in the worst case.
Really Amazing and Detailed Editorials. Great work.
Plz. Can you help on opening the spoiler it says that tutorial is not available.
Click on the contest link first.
After that, you should be able to see the tutorials.
I am not sure why Codeforces works in this way : )
Thank you for your reply , now it is working.
Solutions for Singleton Code seems strange. After well establishing that S(n) = n % 9 , why not do just that ?
My solutions :
thanks for such a wonderful contest! luckily i solved 6 problems by participating virtually :)