brute force dp math

If Bob is winning for given $$$n$$$ stones then Alice will win for $$$n + 2$$$ stones and $$$n + 3$$$ stones, because in $$$n + 2$$$ case Alice will remove $$$2$$$ stones and in $$$n + 3$$$ case Alice will remove $$$3$$$ stones resulting in $$$n$$$ stones where players switch their turns i.e., now Bob will play like first player for these $$$n$$$ stones, so obviously Alice will win.

From this information we can create $$$dp$$$ table, where $$$dp[x]$$$ refers who will win if pile contains $$$x$$$ stones. The base case is for $$$n = 1$$$ where Bob will win.

So from this $$$dp$$$ table , if Alice is already winning no need to add stones , otherwise we will iterate untill we reach the state where Alice will win.

If we observe the pattern, it will look like LWWWLLWWWLLWWWLLWWWLL... where $$$L$$$ means Alice loosing, $$$W$$$ means Alice winning. we can easily see from the pattern that if $$$n$$$ mod $$$5 \ge 2$$$ no need to add stones, Otherwise answer will be $$$2 - n$$$ mod $$$5$$$.

Time Complexity : $$$O(t)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int r=(n%5);
        if(r==0) cout<<"2\n";
        else if(r==1) cout<<"1\n";
        else cout<<"0\n";
    }
}

constructive algorithm implementation

The Upperbound value of $$$k$$$ for given $$$n$$$ is $$$⌈ \frac{n}{2} ⌉^2$$$, because the top-left square grid containing $$$⌈ \frac{n}{2} ⌉^2$$$ cells can have any characters which will mirror the other cells.

There are many ways to construct the grid, the below implementation is one of them.

Time Complexity : $$$O(n^2)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int maxi=((n+1)/2)*((n+1)/2);
        if(k>maxi) cout<<"-1\n";
        else{
            vector<vector<int>> v(n,vector<int>(n));
            int val=0;
            for(int i=0;i<(n+1)/2;i++){
                for(int j=0;j<(n+1)/2;j++){
                    v[i][j]=val;
                    v[i][(n-j-1)]=val;
                    val=(val+1)%k;
                }
            }
            int x=1;
            if(n%2) x++;
            for(int i=(n+1)/2;i<n;i++){
                for(int j=0;j<n;j++){
                    v[i][j]=v[i-x][j];
                }
                x+=2;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<(char)('a'+v[i][j]);
                }
                cout<<"\n";
            }
        }
    }
}

number theory math

General idea of the solution is to store the count of the factors of all $$$a_i(1 \le i \le n)$$$, in that the answer is the maximum factors whose count is greater than or equal to $$$n-2$$$, because we can change the remaining elements to this factor. But this solution is too slow. Infact we don't need to calculate all elements factors, it is sufficient to calculate any $$$3$$$ elements factors. Because if you are interested in any $$$4$$$-th element factors then if those factor is not included in the previous $$$3$$$ elements choosen then its not useful because we can only change upto maximum $$$2$$$ elements.

Note that we can actually also solve this problem by taking factors of only $$$1$$$ element, below implementation shows this.

Time Complexity : $$$O(nD(x)+t \sqrt{x})$$$, where $$$x$$$ is any element from $$$a$$$, $$$D(x)$$$ means number of factors of $$$x$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<ll> get(ll n){
    vector<ll> v;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            ll j=(n/i);
            if(j!=i) v.push_back(j);
        }
    }
    return v;
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        ll ans=0;
        for(ll i=0;i<n;i++){
            cin>>a[i];
            ans=__gcd(ans,a[i]);
        }
        sort(a.begin(),a.end());
        vector<ll> v=get(a[0]);
        for(ll i=0;i<(ll)v.size();i++){
            ll cnt=0;
            for(ll j=0;j<n;j++) if(a[j]%v[i]==0) cnt++;
            if(cnt>=(n-2)) ans=max(ans,v[i]);
        }
        vector<ll> p,s;
        for(ll i=1;i<n;i++) p.push_back(a[i]);
        s=p;
        for(ll i=1;i<(ll)p.size();i++) p[i]=__gcd(p[i],p[i-1]);
        for(ll i=(ll)s.size()-2;i>=0;i--) s[i]=__gcd(s[i],s[i+1]);
        for(ll i=0;i<(ll)p.size();i++){
            ll val=0;
            if(i-1>=0) val=__gcd(val,p[i-1]);
            if(i+1<(ll)s.size()) val=__gcd(val,s[i+1]);
            ans=max(ans,val);
        }
        ll val=0;
        for(ll i=2;i<n;i++) val=__gcd(val,a[i]);
        ans=max(ans,val);
        cout<<ans<<"\n";
    }
}

data structure greedy

Let's first solve the problem for the entire array. Consider the prefix sum array $$$S$$$, where we want all $$$S[i] > 0$$$.

Consider how a swap operation would change the $$$S$$$ array. Clearly, we only pick $$$a[i] = -1$$$ and $$$a[j] = 1$$$. This makes $$$S[i, \dots, j-1]$$$ increase by 2.

Thus, we have a greedy strategy: each time, select the smallest $$$i$$$ and the largest $$$j$$$ such that $$$a[i] = -1$$$ and $$$a[j] = 1$$$. Let $$$\text{minS} = \min(S[1, \dots, n])$$$. With each operation, $$$\text{minS}$$$ increases by 2, so the required number of operations is easy to calculate.

Returning to the original problem, we can use a segment tree to maintain $$$S$$$. For operation 2, this is simply a range addition operation on the segment tree. For operation 1, we can easily find the $$$\text{minS}$$$ for each interval.

Time Complexity : $$$O(nlogn)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

vector<ll> tree,lazy,v1;

void build(ll v, ll tl, ll tr){
    if(tl==tr) tree[v]=v1[tl];
    else{
        ll m=(tl+tr)/2;
        build(2*v+1,tl,m);
        build(2*v+2,m+1,tr);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}

void push(ll v){
    tree[2*v+1]+=lazy[v];
    tree[2*v+2]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    lazy[2*v+2]+=lazy[v];
    lazy[v]=0;
}

ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(l>r) return 1e18;
    if(l==tl && r==tr) return tree[v];
    push(v);
    ll m=(tl+tr)/2;
    ll val1=get(2*v+1,tl,m,l,min(r,m));
    ll val2=get(2*v+2,m+1,tr,max(l,m+1),r);
    return min(val1,val2);
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll x){
    if(l>r) return;
    if(l==tl && r==tr){
        tree[v]+=x;
        lazy[v]+=x;
    }
    else{
        push(v);
        ll m=(tl+tr)/2;
        update(2*v+1,tl,m,l,min(r,m),x);
        update(2*v+2,m+1,tr,max(l,m+1),r,x);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,q;
        cin>>n>>q;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        v1.clear();
        v1=a;
        for(ll i=1;i<n;i++) v1[i]+=v1[i-1];
        tree.clear();
        tree.resize(4*n);
        lazy.clear();
        lazy.resize(4*n);
        build(0,0,n-1);
        while(q--){
            ll type;
            cin>>type;
            if(type==1){
                ll l,r;
                cin>>l>>r;
                l--;
                r--;
                ll sum=get(0,0,n-1,r,r);
                if(l-1>=0) sum-=get(0,0,n-1,l-1,l-1);
                if(sum<=0) cout<<"-1\n";
                else{
                    ll val=get(0,0,n-1,l,r);
                    if(l-1>=0) val-=get(0,0,n-1,l-1,l-1);
                    if(val>0) cout<<"0\n";
                    else{
                        val=-val;
                        cout<<(val+2)/2<<"\n";
                    }
                }
            }
            else{
                ll pos;
                cin>>pos;
                pos--;
                if(a[pos]==1) update(0,0,n-1,pos,n-1,-2);
                else update(0,0,n-1,pos,n-1,2);
                a[pos]*=-1;
            }
        }
    }
}

constructive algorithm tree

There will be no tree if the grid $$$a$$$ doesn't satisfy atleast one of the following condition :

1. $$$a_{ij} = a_{ji}$$$
2. $$$a_{ii}=i$$$
3. $$$a_{ij} \le a_{(a_{ij})j}$$$

Otherwise we can construct the tree in many ways, one of the possible way is:

1. Lets create a parent array $$$par$$$ where $$$par[x]$$$ denotes the parent of node $$$x$$$, initially $$$par[i]=-1$$$ for every $$$i(1 \le i \le n)$$$.

2. we will iterate for $$$x = 1, 2, 3, \cdots , n$$$ in this order and for every $$$y(1 \le y \le n)$$$ we will update $$$par[y] = x$$$ if $$$a_{xy}=x$$$.

Time Complexity : $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> v(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>v[i][j];
                v[i][j]--;
            }
        }
        bool ok=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j && v[i][j]!=i) ok=false;
                if(v[i][j]!=v[j][i]) ok=false;
                if(v[i][j]>min(i,j)) ok=false;
                if(i<j){
                    if(v[i][j]!=v[v[i][j]][j]) ok=false;
                }
            }
        }
        if(ok){
            vector<int> par(n,0);
            par[0]=-1;
            for(int i=1;i<n;i++){
                for(int j=0;j<n;j++){
                    if(i!=j && v[i][j]==i) par[j]=i;
                }
            }
            for(int i=1;i<n;i++){
                cout<<par[i]+1<<" "<<i+1<<"\n";
            }
        }
        else cout<<"-1\n";
    }
}

dp tree

We can solve this problem using Dynamic programming. Perform $$$DFS(depth first search)$$$ and solve the problem from the leaves to root.

Let $$$dp_{ij}$$$ denotes the number of ways to use the nodes from the subtree of $$$i$$$ such that there are $$$j$$$ connected components. Before processing $$$i$$$ we need to combine the tables of $$$dp_k$$$, where $$$k$$$ is the set of childeren nodes of $$$i$$$. In this combining process every $$$j_1$$$ number of components in $$$dp_{i_{1}j_{1}}$$$ and every $$$j_2$$$ number of components in $$$dp_{i_{2}j_{2}}$$$ will contribute for new $$$dp$$$ states $$$j_1 + j_2$$$ number of components.

Time Complexity : $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}

#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

vector<vector<ll>> adj,dp;
vector<ll> sz,dp1,v1;
ll xx,yy;

void dfs(ll x, ll p){
    dp[x][0]=1;
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x);
            for(ll j=0;j<=sz[x]+sz[i];j++) dp1[j]=0;
            for(ll j=0;j<=sz[x];j++){
                for(ll k=1;k<=sz[i];k++){
                    dp1[j+k]=(dp1[j+k]+(((dp[x][j]*dp[i][k])%mod)*calcnCr(j+k-v1[x]-v1[i],j-v1[x]))%mod)%mod;
                }
            }
            sz[x]+=sz[i];
            v1[x]+=v1[i];
            for(ll j=0;j<=sz[x];j++){
                dp[x][j]=dp1[j];
            }
        }
    }
    sz[x]++;
    for(ll j=0;j<=sz[x];j++) dp1[j]=0;
    for(ll j=0;j<sz[x];j++){
        dp1[j+1]=(dp1[j+1]+(dp[x][j]*(j+1-v1[x]))%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j+1]*j)%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j]*(2*j-v1[x]))%mod)%mod;
    }
    for(ll j=0;j<=sz[x];j++){
        dp[x][j]=dp1[j];
    }
}
 
int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dp.clear();
        dp.resize(n+2);
        for(ll i=0;i<n+2;i++) dp[i].resize(n+2);
        dp1.clear();
        dp1.resize(n+2);
        sz.clear();
        sz.resize(n+2);
        v1.clear();
        v1.resize(n+2);
        dfs(0,-1);
        cout<<dp[0][1]<<"\n";
    }
}

It will posted after the first solve or tomorrow

It will posted after the first solve or tomorrow

It will posted after the first solve or tomorrow