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 is now a complete tutorial, covering all the 21 questions of Mathematics Section of CSES.
1. 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";
}
}
2. 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";
}
}
3. 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";
}
}
4. 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;
}
}
}
5. 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;
}
6. 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";
}
}
7. Creating Strings
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;
}
8. 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;
}
9. 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];
}
10. 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);
}
11. 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.com/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];
}
12. 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];
}
13. 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;
}
14. 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;
}
15. 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;
}
16. 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;
}
17. 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;
}
18. 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";
}
}
19. 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";
}
}
20. 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";
}
}
21. 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";
}
}
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
THanks bro!
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 can you pleaes elaborate on second problem Exponentiation II. I don't know much about Fermat's theorem.
fermat's theorm says that if a,m are coprime and m is prime. then pow(a,m-1)%m = 1.
Thankyou so much for the contribution
dardev cdes graph and yours math are the best!!
Would you care to explain the question Exponentiation II again? I tried to solve it using simple Binary exponentiation but got WA. I see you're using Fermat there what is the reason behind it. can we not solve it using simple Binary Exponentiation?
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.
Where can I find the proof of the recurrence relation in the "Throwing dice" editorial?
some additional explanation for Q-2 ,
so we have a ^ b ^ c
also note that m is a prime !
from Fermat's little theorem we know
a^ m-1 = 1 mod(m) for every prime m
b^c = q*(m-1) + r
where q and r are quotients and remainder resp ,a^(b^c) --> a^(q*(m-1)+r) --> a^q(m-1) * a^r = (1^q) * (a^r) mod(m)
so our ans for
a^b^c = a^r(mod m) where b^c = r mod(m-1)
Hope it helps :-)
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
Thanks a lot!
anyone solved grundy's game ?
Several weeks age CSES problem set presented some interesting new problems, including "Josephus Queries", https://cses.fi/problemset/task/2164 , and I'm looking forward to editorials for these new problems:)