So I did not find a tutorial for Maths section of CSES on codeforces, so thought of writing one.
I have put all my codes on https://github.com/div5252/CSES-Problem-Set.
This tutorial covers 29 questions of Mathematics Section of CSES.
1. Josephus Queries
We will solve the problem recursively, reducing the problem by at least half at each step. If $$$k<\frac{n}{2}$$$, we can see that the answer would be $$$2k$$$. Otherwise, we have removed all the even positions. The odd positions can be renamed from $$$1,2,\dots,\frac{n}{2}$$$ and we can recursively find the solution for it. And then we can re-map back to our original $$$n$$$ by multiplying by $$$2$$$ and subtracting $$$1$$$.
Time complexity is $$$O(logn)$$$.
ll f(ll n,ll k)
{
if(n==1) return 1;
if(k<=(n+1)/2)
{
if(2*k>n) return (2*k)%n;
else return 2*k;
}
ll temp=f(n/2,k-(n+1)/2);
if(n%2==1) return 2*temp+1;
return 2*temp-1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll q;
cin>>q;
for(int i=0;i<q;i++)
{
ll n,k;
cin>>n>>k;
cout<<f(n,k)<<"\n";
}
}
2. Exponentiation
We will solve this recusively. If we want to find $$$a^x$$$, we can do that by splitting into $$$a^{\frac{x}{2}}.a^{\frac{x}{2}}$$$ if $$$x$$$ is even, or $$$a^{\frac{x-1}{2}}*a^{\frac{x-1}{2}}*a$$$ if $$$x$$$ is odd. Complexity is $$$O(n*log(max(b))$$$.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,a,b;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b;
cout<<POW(a,b)<<"\n";
}
}
3. Exponentiation II
We will use fermat theorem for this. $$$a^{p-1} \equiv 1$$$ mod $$$p$$$. So using the above, we will find $$$b^c$$$ mod $$$(p-1)$$$ and then $$$a^{b^c}$$$ mod $$$p$$$, where $$$p=1e9+7$$$.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b, ll mod)
{
if(b==0) return 1;
if(b==1) return a%mod;
ll temp=POW(a,b/2,mod);
if(b%2==0) return (temp*temp)%mod;
else return (((temp*temp)%mod)*a)%mod;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,a,b,c;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b>>c;
ll pw=POW(b,c,MOD-1);
cout<<POW(a,pw,MOD)<<"\n";
}
}
4. Counting Divisors
For each number $$$i$$$ from $$$1$$$ to $$$1000000$$$, we increase the count of divisor of multiple of $$$i$$$. And then answer the queries in $$$O(1)$$$. Time complexity is $$$O(nlogn)$$$.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll d[1000005]={};
for(int i=1;i<1000005;i++)
{
for(int j=i;j<1000005;j+=i)
{
d[j]++;
}
}
ll n,x;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
cout<<d[x]<<"\n";
}
}
5. Common Divisors
We have to basically find the largest divisor such that it divides atleast 2 numbers in the array $$$x$$$. So we iterate from the max possible answer i.e. $$$1e6$$$ to $$$1$$$, and increase the divisor count if the number is present in array. Time complexity is $$$O(nlogn)$$$
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll x[n];
ll cnt[1000001]={};
for(int i=0;i<n;i++)
{
cin>>x[i];
cnt[x[i]]++;
}
for(int i=1000000;i>=1;i--)
{
ll d=0;
for(int j=i;j<=1000000;j+=i) d+=cnt[j];
if(d>=2)
{
cout<<i;
return 0;
}
}
}
6. Sum of divisors
For each divisor $$$i$$$, the number of times it occurs from $$$1$$$ to $$$n$$$ is $$$\lfloor \frac{n}{i} \rfloor$$$. Thus the sum to be calculated is equivalent to $$$\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor i$$$.
For this to be computed in $$$O(\sqrt{n})$$$, we observe that there are only $$$\sqrt{n}$$$ order of distinct values of $$$\lfloor \frac{n}{i} \rfloor$$$.
We divide our answers into 2 parts-
For the first part, $$$i \leq \sqrt{n}$$$, we will simply find the sum of terms for $$$1$$$ to $$$\sqrt{n}$$$. This can be done in $$$O(\sqrt{n})$$$.
For the second part, $$$\sqrt{n} < i \leq n$$$. Though this interval is of order of $$$O(n)$$$, here we notice that $$$\lfloor \frac{n}{i} \rfloor$$$ takes values only from $$$1$$$ to $$$\sqrt{n}$$$. So we will find points where value of $$$\lfloor \frac{n}{i} \rfloor$$$ changes by maintaining left and right counters and use the AP sum to compute the answer.
See my code for further clarity. (Inverse of $$$2$$$ denotes division by $$$2$$$ when dealing in modulo)
PS. A mistake I made, remember if you are maintaining intervals l and r, they can be $$$>1e9$$$, so take their modulo too.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll ans=0;
for(ll i=1;i*i<=n;i++)
{
ans+=((n/i)*i)%MOD;
ans%=MOD;
}
ll l=(ll)sqrt(n);
for(ll i=sqrt(n);i>=1;i--)
{
ll r=n/i;
ll sum=0;
sum+=((((r%MOD)*((r+1)%MOD))%MOD)*inverse(2))%MOD;
sum%=MOD;
sum-=((((l%MOD)*((l+1)%MOD))%MOD)*inverse(2))%MOD;
sum=(sum+MOD)%MOD;
sum=(sum*i)%MOD;
l=r;
ans=(ans+sum)%MOD;
//cout<<sum<<" ";
}
cout<<ans;
}
7. Divisor Analysis
Number is given to us of the form $$$x_1^{k_1} \times \dots \times x_n^{k_n}$$$.
Number of divisors is $$$(k_1+1) \times \dots \times (k_n+1)$$$.
Sum of divisors is $$$(\frac{x_1^{k_1+1}-1}{x_1-1}) \times \cdots \times (\frac{x_n^{k_n+1}-1}{x_n-1})$$$.
Product of divisors is $$$num^{\frac{d(num)}{2}}$$$, where num is the number given (in form of primes) and $$$d(num)$$$ is the number of divisors. We have to take care to take the exponent mod $$$(p-1)$$$ and have to carefully divide the exponent by $$$2$$$.
const int MOD=1000000007;
const int MOD1=1000000006;
long long int inverse(long long int i, long long int mod){
if(i==1) return 1;
return (mod - ((mod/i)*inverse(mod%i,mod))%mod+mod)%mod;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll x[n],k[n];
for(int i=0;i<n;i++)
{
cin>>x[i]>>k[i];
}
ll num=1;
for(int i=0;i<n;i++)
{
num*=(k[i]+1)%MOD;
num%=MOD;
}
ll sum=1;
for(int i=0;i<n;i++)
{
ll temp=(POW(x[i],k[i]+1)+MOD-1)%MOD;
temp*=inverse(x[i]-1,MOD);
temp%=MOD;
sum*=temp;
sum%=MOD;
}
ll prod,num1=1;
ll flag=0;
for(int i=0;i<n;i++)
{
if(k[i]%2==1 && flag==0)
{
num1*=((k[i]+1)/2);
num1%=MOD1;
flag=1;
}
else
{
num1*=(k[i]+1)%MOD1;
num1%=MOD1;
}
}
if(flag==0)
{
for(int i=0;i<n;i++)
{
k[i]/=2;
}
}
ll number=1;
for(int i=0;i<n;i++)
{
number*=POW(x[i],k[i]);
number%=MOD;
}
prod=POW(number,num1);
cout<<num<<" "<<sum<<" "<<prod;
}
8. Prime Multiples
We will be using Inclusion-Exclusion principle, considering all subsets of given prime numbers. The count of numbers divisible by the subset of primes would be $$$\frac{n}{prod}$$$, where $$$prod$$$ is the product of the subset of primes. The sign would be positive if the size of subset is odd, and negative otherwise.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,k;
cin>>n>>k;
ll a[k];
for(int i=0;i<k;i++)
{
cin>>a[i];
}
ll ans=0;
for(int i=0;i<(1ll<<k);i++)
{
vll v;
for(int j=0;j<k;j++)
{
if((i&(1<<j))!=0)
{
v.PB(a[j]);
}
}
ll prod=1;
for(int j=0;j<v.size();j++)
{
if(prod>n/v[j])
{
prod=n+1;
break;
}
prod*=v[j];
}
if(v.size()%2==0) ans-=n/prod;
else ans+=n/prod;
}
ans+=n;
cout<<ans;
}
9. Counting Coprime Pairs
We will be using Mobius function $$$\mu(k)$$$ for it. You can read about it here — https://en.wikipedia.org/wiki/M%C3%B6bius_function.
The answer to the problem is $$$\sum_{k=1}^{max(x[i])} \mu(k) {d(k) \choose 2}$$$. Here $$$d(k)$$$ is the number of integers in given sequence that are divisible by $$$k$$$.
We see that this result comes from the Inclusion-Exclusion principle. The term in the summation corresponds to choosing two numbers which are multiples of $$$k$$$, and $$$\mu(k)$$$ decides whether we add it or not. Note that in inclusion-exclusion, we don’t consider $$$k$$$ which aren’t square free, as it doesn’t add any effect to our answer.
Time complexity is $$$O(10^6log(10^6))$$$. Check the code below for implementation of Mobius function.
A similar problem for reference — https://discuss.codechef.com/t/coprime3-editorial/6051
ll lpf[1000001],mobius[1000001];
void least_prime_factor()
{
for(int i=2;i<1000001;i++)
{
if(!lpf[i])
{
for(int j=i;j<1000001;j+=i)
{
if(!lpf[j]) lpf[j]=i;
}
}
}
}
void Mobius()
{
for(int i=1;i<1000001;i++)
{
if(i==1) mobius[i]=1;
else
{
if(lpf[i/lpf[i]]==lpf[i]) mobius[i]=0;
else mobius[i]=-1*mobius[i/lpf[i]];
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll x[n],cnt[1000001]={};
for(int i=0;i<n;i++)
{
cin>>x[i];
cnt[x[i]]++;
}
least_prime_factor();
Mobius();
ll ans=0;
for(int i=1;i<1000001;i++)
{
if(mobius[i]==0) continue;
ll d=0;
for(int j=i;j<1000001;j+=i)
{
d+=cnt[j];
}
ans+=(d*(d-1))/2*mobius[i];
}
cout<<ans;
}
10. Binomial Coefficients
First we will pre-build a factorial array. For division with mod, we can do that by multiplying by its modulo inverse. If you don’t have a idea about inverse, see this https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll fact[1000001];
fact[0]=1;
fact[1]=1;
for(int i=2;i<=1000000;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
ll n,a,b;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b;
ll ans=(fact[a]*inverse(fact[b]))%MOD;
ans*=inverse(fact[a-b]);
ans%=MOD;
cout<<ans<<"\n";
}
}
11. Creating Strings II
This is basic combinatorics. The number of ways of arranging these characters is $$$\frac{n!}{\prod_{i=1}^{26} (cnt(alphabet_{i}))!}$$$.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll fact[1000001];
fact[0]=1;
fact[1]=1;
for(int i=2;i<=1000000;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
string s;
cin>>s;
ll n=s.size();
ll cnt[26]={};
for(int i=0;i<n;i++)
{
cnt[s[i]-'a']++;
}
ll tot=fact[n];
for(int i=0;i<26;i++)
{
tot*=inverse(fact[cnt[i]]);
tot%=MOD;
}
cout<<tot;
}
12. Distributing Apples
It is equivalent to finding the number of solution to $$$x_1 + x_2 + \cdots + x_n=m$$$, where $$$x_1,x_2,\cdots,x_n$$$ are non negative integers.
You can see that here- https://www.geeksforgeeks.org/number-of-integral-solutions-of-the-equation-x1-x2-xn-k/.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll fact[2000001];
fact[0]=1;
fact[1]=1;
for(int i=2;i<=2000000;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
ll n,m;
cin>>n>>m;
ll ans=(fact[m+n-1]*inverse(fact[n-1]))%MOD;
ans*=inverse(fact[m]);
ans%=MOD;
cout<<ans;
}
13. Christmas Party
This is a standard problem of finding derangements in a sequence.
The recursive formula is $$$D(n)=(D(n-1)+D(n-2))(n-1)$$$.
For info regarding derangement, see https://en.wikipedia.org/wiki/Derangement.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll d[n+1];
d[1]=0;
d[2]=1;
for(ll i=3;i<=n;i++)
{
d[i]=(((d[i-1]+d[i-2])%MOD)*(i-1))%MOD;
}
cout<<d[n];
}
14. Bracket Sequences I
Let $$$dp[n]$$$ denote the number of bracket sequences with $$$n$$$ pairs of bracket. At first index, there is always a opening bracket and somewhere is between there is a closing bracket. So we look at how many sequences of $$$i$$$ pairs of brackets are there between them and how many sequences of $$$n-i-1$$$ pairs of brackets are after them. So we get the recursive formula – $$$dp[n]=\sum_{i=0}^{n-1}dp[i]dp[n-i-1]$$$.
And $$$dp[0]=0$$$. In fact this is nothing but the Catalan number $$$C_n=\frac{1}{n+1} {2n \choose n}$$$.
You can refer to this — https://cp-algorithms.com/combinatorics/bracket_sequences.html
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
if(n%2==1)
{
cout<<0;
return 0;
}
n/=2;
ll fact[2*n+1];
fact[0]=1;
for(ll i=1;i<=2*n;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
ll ans=(fact[2*n]*inverse(fact[n]))%MOD;
ans*=(inverse(fact[n])*inverse(n+1))%MOD;
ans%=MOD;
cout<<ans;
}
15. Bracket Sequences II
Let $$$k$$$ denote the excess opening brackets which we need to close and $$$n$$$ denote the remaining pairs. This can be easily found out given the length and the prefix portion of the string.
Let us denote the answer by $$$C_n^{(k)}$$$. The generalized formula is -
$$$C_n^{(k)}= \sum_{a+b+\dots+\lambda=n} C_a C_b \dots C_\lambda$$$, $$$C_0=1$$$.
where there are $$$k+1$$$ terms, $$$C_a,C_b,\dots,C_\lambda$$$.
This is basically a convolution on Catalan. Similar to deriving the expression for Catalan number, we get $$$C_n^{(k)}=\frac{k+1}{n+k+1} {2n+k \choose k}$$$.
You can refer to this — https://codeforces.com/blog/entry/87585
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
if(n%2==1)
{
cout<<0;
return 0;
}
n/=2;
string s;
cin>>s;
ll k=0,o=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
{
k++;
o++;
}
else k--;
if(k<0)
{
cout<<0;
return 0;
}
}
n-=o;
if(k<0 || n<0 || 2*n+k<n)
{
cout<<0;
return 0;
}
ll fact[2*n+k+1];
fact[0]=1;
for(int i=1;i<=2*n+k;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
ll ans=(fact[2*n+k]*inverse(fact[n]))%MOD;
ans*=inverse(fact[n+k]);
ans%=MOD;
ans*=((k+1)*inverse(n+k+1))%MOD;
ans%=MOD;
cout<<ans;
}
16. Counting Necklaces
This is computed by using Burnside’s Lemma. It states that the total number of distinct objects is $$$\sum_{k=1}^{N} \frac{c(k)}{N}$$$, where $$$c(k)$$$ is number of combination that remain unchanged when $$$k$$$-th rotation is applied. If we rotate the necklace by $$$i$$$, $$$m^{gcd(i,n)}$$$ necklaces will remain the same.
So the answer would be $$$\sum_{i=1}^{n} \frac{m^{gcd(i,n)}}{n}$$$.
You can refer to this — https://www.geeksforgeeks.org/orbit-counting-theorem-or-burnsides-lemma/
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,m;
cin>>n>>m;
ll ans=0;
for(ll i=0;i<n;i++)
{
ll temp=POW(m,__gcd(i,n));
temp*=inverse(n);
temp%=MOD;
ans+=temp;
ans%=MOD;
}
cout<<ans;
}
17. Counting Grids
18. Fibonacci Numbers
We will be using the following recursion-
If $$$n$$$ is even then $$$k = \frac{n}{2}$$$:
$$$F(n) = [2 \times F(k-1) + F(k)] \times F(k) $$$
If $$$n$$$ is odd then $$$k = \frac{n + 1}{2}$$$:
$$$F(n) = F(k) \times F(k) + F(k-1) \times F(k-1) $$$
This will calculate the fibonacci number in $$$O(logn)$$$. Remember to store the values in a map. For the proof of the recurrence relation- https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
map<ll,ll> f;
ll fib(ll n)
{
if(f.count(n)) return f[n];
if(n==0) return 0;
if(n==1 || n==2) return 1;
if(n%2==0)
{
ll k=n/2;
ll ret1=fib(k-1),ret2=fib(k);
return f[n]=((((2ll*ret1)%MOD+ret2)%MOD)*ret2)%MOD;
}
else
{
ll k=(n+1)/2;
ll ret1=fib(k-1),ret2=fib(k);
return f[n]=( (ret1*ret1)%MOD + (ret2*ret2)%MOD)%MOD;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
cout<<fib(n);
}
19. Throwing Dice
It can be solved in $$$O(n)$$$ using the recurrence relation-
$$$F(n)=F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)+F(n-6)$$$.
But this would give a TLE. So we will be using a technique called matrix exponentiation that involve calculating the $$$n^{th}$$$ term of a linear recurrence relation in time of the order of $$$O(logn)$$$.
See the following for more on it-
https://codeforces.cc/blog/entry/67776
https://www.geeksforgeeks.org/find-nth-term-a-matrix-exponentiation-example/
Check my code below for further clarification.
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
vector<vll> mul(vector<vll> x, vector<vll> y) {
vector<vll> r(6, vll(6));
for (int j = 0; j < 6; j++)
{
for (int k = 0; k < 6; k++)
{
for (int l = 0; l < 6; l++)
{
r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
}
}
}
return r;
}
vector<vll> modpow(vector<vll> x, ll n)
{
if (n == 0)
{
vector<vll> r(6, vll(6));
for (int i = 0; i < 6; i++) r[i][i] = 1;
return r;
}
vector<vll> u = modpow(x, n/2);
u = mul(u, u);
if (n%2==1) u = mul(u, x);
return u;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
vector<vll> a(6,vll(6));
for(int i=0;i<5;i++)
{
a[i][i+1]=1;
}
for(int i=0;i<6;i++)
{
a[5][i]=1;
}
vector<vll> ans=modpow(a,n);
cout<<ans[5][5];
}
20. Graph Paths I
Let’s first create an Adjacency matrix. We can see for the case of $$$k=1$$$, the answer is the constructed Adjacency Matrix, for any 2 pair of nodes.
Next let the matrix $$$M_k$$$ denote the answer matrix for $$$k$$$.
Then $$$M_{k+1}[i][j]=\sum_{l=1}^{n} M_{k}[i][l].AdjMat[l][j]$$$.
Thus the solution of the problem is $$$AdjMat^{k}$$$.
For more info refer- https://cp-algorithms.com/graph/fixed_length_paths.html
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
ll n;
vector<vll> mul(vector<vll> x, vector<vll> y) {
vector<vll> r(n, vll(n));
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
for (int l = 0; l < n; l++)
{
r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
}
}
}
return r;
}
vector<vll> modpow(vector<vll> x, ll pw)
{
if (pw == 0)
{
vector<vll> r(n, vll(n));
for (int i = 0; i < n; i++) r[i][i] = 1;
return r;
}
vector<vll> u = modpow(x, pw/2);
u = mul(u, u);
if (pw%2==1) u = mul(u, x);
return u;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll m,k,a,b;
cin>>n>>m>>k;
vector<vll> v(n,vll (n,0));
for(int i=0;i<m;i++)
{
cin>>a>>b;
a--; b--;
v[a][b]++;
}
cout<<modpow(v,k)[0][n-1];
}
21. Graph Paths II
It’s a really nice problem. The procedure is almost the same as above question. We will create an Adjacency matrix where each entry stores the minimum weight edge, or $$$INF$$$ if no edge.
Next let the matrix $$$M_k$$$ denote the answer matrix for $$$k$$$.
Then $$$M_{k+1}[i][j]=min_{l=(1 \cdots n)} (M_{k}[i][l]+AdjMat[l][j])$$$.
Here we can make an analogy with the multiplication operation. Instead we take the minimum rather than sum.
This can be tackled by matrix exponentiation, just have to modify the $$$mul()$$$ function.
See my code for further clarification.
For more info refer- https://cp-algorithms.com/graph/fixed_length_paths.html#toc-tgt-1
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
ll INF=4e18;
ll n;
vector<vll> mul(vector<vll> x, vector<vll> y) {
vector<vll> r(n, vll(n,INF));
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
for (int l = 0; l < n; l++)
{
r[j][k] = min(r[j][k],x[j][l]+y[l][k]);
}
}
}
return r;
}
vector<vll> modpow(vector<vll> x, ll pw)
{
if (pw == 1)
{
return x;
}
vector<vll> u = modpow(x, pw/2);
u = mul(u, u);
if (pw%2==1) u = mul(u, x);
return u;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll m,k,a,b,c;
cin>>n>>m>>k;
vector<vll> v(n,vll(n,INF));
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
a--; b--;
v[a][b]=min(v[a][b],c);
}
ll ans=modpow(v,k)[0][n-1];
if(ans==INF) cout<<"-1";
else cout<<ans;
}
22. Dice Probability
This can be solved using dp, where $$$dp[i][j]$$$ denotes the probability of getting sum $$$j$$$ when the dice has been rolled $$$i$$$ times.
The transition would be-
$$$dp[i][j]=\frac{\sum_{k=1}^{min(6,j)} dp[i-1][j-k]}{6}$$$.
Then the answer will be $$$\sum_{i=a}^{b} dp[n][i]$$$.
Taking care of rounding off. See my code for that.
Time complexity is $$$O(n^2)$$$.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,a,b;
cin>>n>>a>>b;
vector<vector<ld> > dp(n+1,vector<ld> (6*n+1,0));
dp[0][0]=1.0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=6*n;j++)
{
for(int k=1;k<=6;k++)
{
if(j-k>=0)
{
dp[i][j]+=dp[i-1][j-k];
}
}
dp[i][j]=dp[i][j]/6;
}
}
ld ans=0;
for(int i=a;i<=b;i++)
{
ans+=dp[n][i];
}
ans*=1e6;
ans=llround(ans);
ans/=1e6;
cout<<fixed<<setprecision(6)<<ans;
}
23. Moving Robots
We do something like brute force here. Consider a robot on a single cell only, assuming all others don’t have robot present.
Here $$$dp[k][i][j]$$$ represents the expected probability of a robot to be present in cell $$$(i,j)$$$ after $$$k$$$ steps.
The state transition would be $$$dp[k+1][i+dr[f]][j+dc[f]]+=\frac{dp[k][i][j]}{totaldirections} $$$, where $$$dr[4]$$$ and $$$dc[4]$$$ iterates over the $$$4$$$ possible directions.
The expected answer for each individual cell $$$(i,j)$$$ would be the product of $$$(1-dp[n][i][j])$$$.
Adding all the expected values for a single cell gives us our final answer.
Time complexity is $$$O(8^4n)$$$.
ll dr[4]={1,-1,0,0};
ll dc[4]={0,0,1,-1};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ld dp[n+1][8][8]={};
ld ans[8][8];
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
ans[i][j]=1;
}
}
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
for(int k=0;k<=n;k++)
{
for(int i1=0;i1<8;i1++)
{
for(int j1=0;j1<8;j1++)
{
dp[k][i1][j1]=0;
}
}
}
dp[0][i][j]=1;
for(int k=0;k<n;k++)
{
for(int i1=0;i1<8;i1++)
{
for(int j1=0;j1<8;j1++)
{
ld dir=0;
for(int f=0;f<4;f++)
{
ll u=i1+dr[f],v=j1+dc[f];
if(u>=0 && u<8 && v>=0 && v<8)
{
dir++;
}
}
for(int f=0;f<4;f++)
{
ll u=i1+dr[f],v=j1+dc[f];
if(u>=0 && u<8 && v>=0 && v<8)
{
dp[k+1][u][v]+=dp[k][i1][j1]/dir;
}
}
}
}
}
for(int i1=0;i1<8;i1++)
{
for(int j1=0;j1<8;j1++)
{
ans[i1][j1]*=(1-dp[n][i1][j1]);
}
}
}
}
ld expc=0;
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
expc+=ans[i][j];
}
}
cout<<fixed<<setprecision(6)<<expc;
}
24. Candy Lottery
For each $$$i$$$ from $$$1$$$ to $$$k$$$, we first find the probability such that the maximum is $$$i$$$. That would be equal to $$$(\frac{i}{k})^n -(\frac{i-1}{k})^n$$$. This is because we first uniformly choose $$$n$$$ numbers from $$$1$$$ to $$$i$$$ and subtract those cases in which $$$i$$$ doesn’t occur. Next we multiply it by $$$i$$$ to find the expected maximum, and add all those.
Taking care of rounding off. See my code for that.
Time complexity is $$$O(nk)$$$.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,k;
cin>>n>>k;
ld ans=0;
for(int i=1;i<=k;i++)
{
ld add=1,sub=1;
for(int j=1;j<=n;j++)
{
add*=(ld)i/(ld)k;
sub*=(ld)(i-1)/(ld)k;
}
ans+=(ld)(i)*(ld)(add-sub);
}
ans*=1e6;
ans=llround(ans);
ans/=1e6;
cout<<fixed<<setprecision(6)<<ans;
}
25. Inversion Probability
Due to lower constraint on $$$n$$$, brute force will work. We find expected inversions for every pair of $$$(i,j)$$$ where $$$i<j$$$.
If $$$a[j] \le a[i]$$$, then the number of inversions will be $$$a[j] \choose 2$$$, because $$$i$$$-th element should have values till $$$a[j]$$$.
Otherwise if $$$a[j]>a[i]$$$, then the number of inversions will be $$$a[i] \choose 2$$$ $$$+ ((a[j]-a[i]) \times a[i])$$$, which is the sum of cases when $$$j$$$-th element is less than $$$a[i]$$$ or greater.
Time complexity is $$$O(n^2)$$$.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
ld ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
ll k;
if(a[j]<=a[i])
{
k=(a[j]*(a[j]-1))/2;
}
else
{
k=(a[i]*(a[i]-1))/2 + (a[j]-a[i])*a[i];
}
ans+=(ld)k/(ld)(a[j]*a[i]);
}
}
cout<<fixed<<setprecision(6)<<ans;
}
26. Stick Game
Let $$$dp[i]$$$ denote the result of game if there are total $$$i$$$ sticks. Here $$$dp[i]$$$ is true is first player wins, otherwise false.
We know $$$dp[0]$$$ is false. The transition would be that if $$$dp[i-p[j]]$$$ is false where $$$j={1, \cdots ,k}$$$, then $$$dp[i]$$$ would be true.
Time complexity is $$$O(nk)$$$.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,k;
cin>>n>>k;
ll p[k];
for(int i=0;i<k;i++)
{
cin>>p[i];
}
ll dp[n+1]={};
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)
{
if(i-p[j]>=0 && dp[i-p[j]]==0)
{
dp[i]=1;
}
}
}
for(int i=1;i<=n;i++)
{
if(dp[i]==1) cout<<"W";
else cout<<"L";
}
}
27. Nim Game I
This is a straight nim game questions where the second player wins when the xor of the elements of array is 0, and otherwise first player wins.
For more info regarding nim- https://en.wikipedia.org/wiki/Nim
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t,n;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
ll x[n];
ll xr=0;
for(int i=0;i<n;i++)
{
cin>>x[i];
xr^=x[i];
}
if(xr!=0) cout<<"first";
else cout<<"second";
cout<<"\n";
}
}
28. Nim Game II
It’s a variation of nim game called the subtraction game where an upper bound of stones that can be removed, let say $$$k$$$ be given. All we have to do is to consider the pile mod $$$(k+1)$$$, and then follow the usual nim.
For more info- https://en.wikipedia.org/wiki/Nim#The_subtraction_game
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t,n;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
ll x[n];
ll xr=0;
for(int i=0;i<n;i++)
{
cin>>x[i];
x[i]%=4;
xr^=x[i];
}
if(xr!=0) cout<<"first";
else cout<<"second";
cout<<"\n";
}
}
29. Stair Game
We consider elements at even position and proceed as Nim. I don’t have a proof as to why it works. There is some intuition- to empty a pile a position $$$k$$$, we will have to empty it all the way to position $$$1$$$, which means there are $$$(k-1)$$$ copies of that pile which we have to empty.
So if $$$k$$$ is odd, xor of $$$k$$$ even number of times is $$$0$$$, so the odd positions don't create an effect, and hence we consider the even positions only.
If some one has a formal proof of this, please mention it in the comments.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t,n;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
ll a[n];
ll xr=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(i%2)
{
xr^=a[i];
}
}
if(xr) cout<<"first";
else cout<<"second";
cout<<"\n";
}
}
30. Grundy's Game
We find the Sprague-Grundy values corresponding to the Grundy’s game. This can be easily done by dynamic programming, as we find the mex of all the state reachable from that state. Also we note that for larger values of $$$n$$$ ($$$n \ge 2000$$$), its Sprague-Grundy value is never $$$0$$$. (I don’t have a proof for this, maybe someone can let me know in the comments.)
You can read about Sprague-Grundy theorem here — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
ll mex(vll v)
{
set<ll> s;
for(int i=0;i<v.size();i++)
{
s.insert(v[i]);
}
for(int i=0;i<1000001;i++)
{
if(s.count(i)==0) return i;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll limit=2000;
ll dp[limit];
dp[0]=dp[1]=dp[2]=0;
for(int i=3;i<limit;i++)
{
vll v;
for(int j=1;2*j<i;j++)
{
v.PB(dp[j]^dp[i-j]);
}
dp[i]=mex(v);
}
ll t;
cin>>t;
for(int i=0;i<t;i++)
{
ll n;
cin>>n;
if(n>=limit) cout<<"first";
else if(dp[n]==0) cout<<"second";
else cout<<"first";
cout<<"\n";
}
}
31. Another Game
UPD: I have also added tutorials for the newly added problems in Maths section. I am yet to do two problems — Counting Grids and Another Game. It would be helpful if someone could come up with tutorials for these.
Thanks man...
Thanks a lot!
UPD: The tutorial is now complete. I have put the explanations and codes for all 21 problems.
If you find any typo or any improvement in the explanation, please comment below.
I haven't put the complete code(template portion) in the tutorial above, so as to prevent people for directly copying. Still if you wish to see the complete code, I have to the link to my github which contains AC solutions.
I still do not get sum of divisors :(
link this might help, see the last answer
Yeah sorry, I have updated the explanation. I hope it is clear now.
Thanks
https://www.geeksforgeeks.org/sum-divisors-1-n/
divyamsingal01 can you share the links to the editorials of other sections if you have found them?
Range queries https://codeforces.com/blog/entry/77128
Graph https://codeforces.com/blog/entry/79518
DP https://codeforces.com/blog/entry/70018
can you please verify if i understood moving robots correctly —
for each robot we first get what is the probability for it to be on some i, j cell after k iterations.
then for each cell what is the probability that it was empty after k iterns? — probability that robot 1 isnt there * probability that robot 2 isnt there and so on.... so we multiply the 1 — dp[i1][j1]
now expectation — sum(P(xi)*xi) we calculated P(xi) and xi is 1?
For 21, here's a fairly straightforward proof:
This game is essentially equivalent to Nim with a restricted number of additions permitted, with the piles being on the even indices, and the permitted additions being precisely the ones which can be done due to the shift from the pile on the immediate right (if it exists), with the only other possible move being removal of one element from an even pile at most a finite number of times, and thus this game is equivalent to vanilla Nim (proof here: https://cp-algorithms.com/game_theory/sprague-grundy-nim.html#toc-tgt-5), from where it is obvious.
divyamsingal01
In Graph Paths II, how did you decide the value of INF?
I took INF=7e18 and it was giving WA, but on changing it to 4e18, it got Accepted!
You might be having long long overflow due to 7e18. Initialize, it sufficiently large so that it serves its purpose and encounters no overflow scenario.
Mathematical Proof for Q21. It is a Staircase Nim Problem and can be easily proven that only even position value affects our answer. For the proof click here
Counting Necklaces How to get the inclusion/exclusion right?
Can sombody explain with example n=12?
It's not that trivial if you don't know group theory, try reading about burnside's lemma.
Found this which gives basically the solution. Link
If you would like to solve a similar problem on this theory , you may try this one https://codeforces.com/gym/101873/problem/B
div[i] is ith divisor of n. dp[y] is actual correct answer patterns of length y only.
why we are concerned with divisors?? any pattern can complete it's cycle iff it's length divides n. here's ac code
anyone solved grundy's game ?
In exponentiation II , why we use fermat's theorem ? Can't we just find x = power(b,c) and then power(a,x) ? I tried but it didn't work. So I want to know why? Note : I am not from Maths background so if you will share any resources it will be very useful.
That's because $$$b^c$$$ will overflow (doesn't fit in long long), so we used Fermat's Theorem.
Hi In COUNTING DIVISORS (problem-4), I understand that an array of 0s is created and then each 0 in the array is incremented in the for-loops.
I want to know the rationale behind this. Why this works?
Explained it here
The program given there and even mine gives RE and TLE (at times) when i am executing.
What's wrong in the code given there?
Not mentioned in the snippet but value of $$$N$$$ is $$$10^6+1$$$. That could be the reason for RE.
For Another Game, the first player wins iff there is at least one heap with an odd number of coins.
If all heaps have an even number of coins, the second player can win, by taking coins from the same set of piles as the first player on the previous turn. This ensures that all heaps have an even number of piles at the end of the second player's turn, so the strategy can continue.
If at least one heap has an odd number of coins, the first player can win by taking one coin from each pile with an odd number of coins, reducing the game to the first scenario.
Proof of Stair Game is as follows:
Consider the nim game on the even-numbered piles. If the first player wins this game, they can win the entire game. A valid strategy:
In subsequent moves:
If the second player moves coins from an odd-numbered pile $$$p$$$ to pile $$$p-1$$$, the first player should move the same number of coins from $$$p-1$$$ to $$$p-2$$$. Note that the nim game on the even-numbered piles is unaffected, and it is impossible for the first player to lose during this.
If the second player moves coins from an even-numbered pile, they have effectively made a move in the nim game, so the first player's next move should be to play an optimal move in the nim game.
After all the moves in the nim game have been exhausted, we know that the second player has the next move and that all coins are in odd-numbered piles, which means the first player ultimately wins using this strategy.
If the second player wins the nim game, use a similar strategy as the one above (i.e. if first player plays on odd-numbered pile, mirror their move; if they play on even-numbered pile, play nim game).
Thanks!
https://math.stackexchange.com/questions/3587286/using-group-actions-to-determine-the-different-colourings-of-a-grid
divyamsingal01
17. Counting Grids
We will use Burnside's Lemma. Define a group of rotations $$$G = { 0^\circ, 90^\circ, 180^\circ, 270^\circ }$$$ that will act upon $$$X$$$ which we define as the set of all possible square grids with side length $$$n$$$. Burnside's Lemma states that
Thus, it suffices to find the number of grids that remain the same after a rotation of $$$g$$$ degrees for each $$$g$$$ in $$$G$$$.
The final answer is simply the sum of the four values divided by 4 (or in this case, multiplied $$$4^{-1} \mod 1000000007 = 250000002$$$
(Sorry for the Necropost)
in case someone is wondering how to get $$$250000002$$$ without using online calculator
Wolfram Alpha works perfectly well
for stair game, the proof is as follows:
say player A ( let it be first or second ) have winning strategy in the nim game you considered, how can A still have a winning strategy in the original game?
the new strategy is simple, when player B moves n coins from an odd-numbered stair k, A moves the same amount of coins from stair k-1 to k-2, this preserves the nim game; when B's move is on an even numbered stair, we proceed with our original strategy.
the way I found this property is through testing some possibilities for n = 1,2,3,4,5. Hope this helps!
Another proof for Another Game:
$$$\lbrace 1 \rbrace$$$ is winning for you, just take the coin.
$$$\lbrace 2 \rbrace$$$ is losing, because you can only take one coin, leading to $$${1}$$$ for your opponent, which is winning.
$$$\lbrace \rbrace$$$ is losing, there are no moves to be done.
Let $$$E_{i,j}$$$ be a set which contains the multisets of any $$$i$$$ even nonzero numbers ($$$i \ge 1$$$), with their sum $$$j$$$ ($$$j \ge 2i$$$).
Also, let $$$E_{i,0} = \lbrace\lbrace\rbrace\rbrace$$$ for any $$$i \ge 1 \Rightarrow E_{i,0}$$$ contains only losing multisets for any $$$i \ge 1$$$.
(Induction A)
If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$) all contain only losing multisets, we will prove by induction that $$$E_{i,2i}$$$ also contains only losing multisets.
$$$E_{i,2i}$$$ is only formed from the multiset $$$\lbrace 2, 2, 2, .., 2 \rbrace$$$ (i times)
Any move we will do will lead to $$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) ∪ $$$\lbrace 1, 1, 1, .., 1 \rbrace$$$ (k times) | $$$1 \le k \le i$$$
Our opponent will mimic our move, leading to:
$$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) $$$\in E_{i-k,2i-2k}$$$ , which we already claimed it is losing.
(Induction B)
If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$), $$$E_{i,2i}$$$, $$$E_{i,2i+2}$$$, .., $$$E_{i,2k-2}$$$ all contain only losing multisets, we will prove by induction that $$$E_{i,2k}$$$ also contains only losing multisets.
Let $$$E \in E_{i,2k}$$$, $$$E = \lbrace e_1, e_2, .., e_i | e_1 + e_2 + .. + e_i = 2k \rbrace$$$
Any move we will do will lead to the following split of $$$\lbrace e_1, e_2, .., e_i \rbrace$$$: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}}-1, e_{b_{2}}-1, .., e_{b_{y}}-1 \rbrace$$$ with $$$\lbrace a_1, a_2, .., a_x \rbrace ∪ \lbrace b_1, b_2, .., b_y \rbrace = \lbrace 1, 2, .., i \rbrace, x + y = i$$$.
Our opponent will mimic our move, leading to: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}} - 2, e_{b_{2}} - 2, .., e_{b_{y}} - 2 \rbrace$$$, which $$$\in E_{i,2k-2y}$$$, which we have already claimed to be losing; since it is again our move, $$$E$$$ is losing.
Since $$$E_{1,2} = \lbrace\lbrace 2 \rbrace\rbrace \Leftrightarrow E_{1,2}$$$ contains only losing multisets, by applying (Induction B) (we can apply it, $$$\lbrace\rbrace$$$ is losing) $$$\Rightarrow E_{1,4}$$$, $$$E_{1,6}$$$, $$$E_{1,8}$$$, ... all contain only losing multisets.
So $$$E_{1,j}$$$ (any $$$j \ge 2$$$) contains only losing multisets. Now we apply (Induction A) $$$\Rightarrow$$$ $$$E_{2,4}$$$ contains only losing multisets.
We now apply (Induction B) again $$$\Rightarrow E_{2,6}$$$, $$$E_{2,8}$$$, $$$E_{2,10}$$$, ... all contain only losing multisets.
...
By continuing to repeatedly swap between (Induction B) and (Induction A), we can conclude that $$$E_{i,j}$$$ (any $$$i \ge 1$$$, any $$$j \ge 2i$$$) contains only losing multisets.
In other words, any multiset that contains only even numbers is losing.
If we start with even numbers only, we lose. Otherwise, during our first turn we will subtract $$$1$$$ only from the odd numbers we have, leaving our opponent with a losing configuration of even numbers only.
I have spent over 2 hours over the Josephus Queries Problem, I find it to be most difficult, I can understand we have to halve the range and query for the next and modify the queried value accordingly to the parent caller. But still not able to formulate, It feels too random, what should I do, I want a solution with a proper explanation for EDGE cases :(
Hope this helps. Josephus Queries seems to be modified version of standard Josephus Problem.
Can anyone explain me Q.2 Why to do "mod-1" for b^c ?
Euler's theorem states that if $$$\gcd(a, c)=1$$$ then $$$a^b \equiv a^{b\pmod{\varphi(c)}} \pmod{c}$$$. Since MOD is a prime, $$$\varphi(MOD)=MOD - 1$$$. Thus $$$a^{b^c} \equiv a^{b^c \pmod{MOD - 1}}$$$
My solution for Josephus queries.
I actually simulated the selection process iteratively, instead of recursively reducing it to smaller subproblem.
Before every iteration, the current set of numbers is stored with three number : $$$st$$$, $$$end$$$, $$$period$$$.
It implies that the current set contains these numbers $$$[st, st+period, st+2*period, ... end]$$$
Then we just simulate how the numbers will be chosen and find $$$cntchoosen$$$ denoting the number of elements chosen in this iteration.
If $$$k \le cntchoosen $$$, then we will just choose the $$$k$$$ th element of current set, else we continue the iterations.
Here is the accepted code.
I came up with a different solution for Inversion Probability.
Lets denote $$$SS[i]$$$ by number of all unique arrays of size $$$i$$$. We can find using this way. $$$SS[i] = r[1]*r[2] ... r[i]$$$
Lets denote $$$sumf[y][i]$$$ by sum of frequency of $$$y$$$ in all unique arrays of size $$$i$$$. We can find using this way. $$$sumf[y][i] = r[i]*sumf[y][i-1] + (j<=r[i] ? SS[i-1]:0)$$$
Lets denote max value of $$$r[i]$$$ by $$$mx$$$.
Lets denote $$$sum[i]$$$ by the sum of inversion count of all unique arrays of size $$$i$$$. $$$sum[i] = sum[i-1]*r[i-1] + \sum_{x=1}^{x=r[i]} \sum_{y=x+1}^{y=mx} sumf[y][i-1] $$$
Finally our answer is $$$sum[n] / SS[n]$$$
Complexity : $$$O(n*max(r[i])*max(r[i]))$$$ Complexity can be bought down to $$$O(n*max(r[i]))$$$ by computing the prefix sum of frequencies.
Accepted Code :
nitin sir orz
I do not understand the importance of the problem "Counting Divisors". We previously calculate all answers and then outputting them. I count each prime factor and then apply Combinatorics.
Secondly, I tried to optimize the factor calculation.
in PRIME MULTIPLES , ans+=n at last because iteration was start from i = 0 and for this reason extra n is added to the answer, you can start from i = 1 then everything will be fine.
Counting grids is easily solvable with Burnside lemma.
4cases.
— No rotation.
— Rotate 90*.
— Rotate 180*.
— Rotate 270*.
Very helpful. Thanks!