Idea:Yugandhar_Master
First solve:lonely_forever
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$$$.
#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";
}
}
Idea:Yugandhar_Master
First solve:Egor
constructive algorithm
#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";
}
}
}
}
Idea:Yugandhar_Master
First solve:Egor
number theory
math
#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";
}
}
Idea:Yugandhar_Master
First solve:Egor
data structure
greedy
#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;
}
}
}
}
Idea:Yugandhar_Master
First solve:lonely_forever
constructive algorithm
tree
#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";
}
}
Idea:Yugandhar_Master
First solve:methanol
dp
tree
#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";
}
}
Idea:Yugandhar_Master
First solve:[user:NA,2024-11-07]
data structure
#include<iostream>
#include<vector>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<assert.h>
using namespace::std;
using lint=long long;
#define rep(i,n) for(lint i=0;(i)<lint(n);(i)++)
template<typename T>
class dynamic_connectivity{
class euler_tour_tree{
public:
struct node;
using np=node*;
using lint=long long;
struct node{
np ch[2]={nullptr,nullptr};
np p=nullptr;
int l,r,sz,sz2;
T val=et,sum=et;
bool exact=1;
bool child_exact;
bool edge_connected=0;
node(){}
node(int l,int r):l(l),r(r),sz(l==r),sz2(0),child_exact(l<r){}
bool is_root() {
return !p;
}
};
vector<unordered_map<int,np>>ptr;
np get_node(int l,int r){
if(ptr[l].find(r)==ptr[l].end())ptr[l][r]=new node(l,r);
return ptr[l][r];
}
np root(np t){
if(!t)return t;
while(t->p)t=t->p;
return t;
}
bool same(np s,np t){
if(s)splay(s);
if(t)splay(t);
return root(s)==root(t);
}
np reroot(np t){
auto s=split(t);
return merge(s.second,s.first);
}
pair<np,np> split(np s){
splay(s);
np t=s->ch[0];
if(t)t->p=nullptr;
s->ch[0]=nullptr;
return {t,update(s)};
}
pair<np,np> split2(np s){
splay(s);
np t=s->ch[0];
np u=s->ch[1];
if(t)t->p=nullptr;
s->ch[0]=nullptr;
if(u)u->p=nullptr;
s->ch[1]=nullptr;
return {t,u};
}
tuple<np,np,np> split(np s,np t){
auto u=split2(s);
if(same(u.first,t)){
auto r=split2(t);
return make_tuple(r.first,r.second,u.second);
}else{
auto r=split2(t);
return make_tuple(u.first,r.first,r.second);
}
}
template<typename First, typename... Rest>
np merge(First s,Rest... t){
return merge(s,merge(t...));
}
np merge(np s,np t){
if(!s)return t;
if(!t)return s;
while(s->ch[1])s=s->ch[1];
splay(s);
s->ch[1]=t;
if(t)t->p=s;
return update(s);
}
int size(np t){return t?t->sz:0;}
int size2(np t){return t?t->sz2:0;}
np update(np t){
t->sum=et;
if(t->ch[0])t->sum=fn(t->sum,t->ch[0]->sum);
if(t->l==t->r)t->sum=fn(t->sum,t->val);
if(t->ch[1])t->sum=fn(t->sum,t->ch[1]->sum);
t->sz=size(t->ch[0])+(t->l==t->r)+size(t->ch[1]);
t->sz2=size2(t->ch[0])+(t->edge_connected)+size2(t->ch[1]);
t->child_exact=(t->ch[0]?t->ch[0]->child_exact:0)|(t->l<t->r&&t->exact)|(t->ch[1]?t->ch[1]->child_exact:0);
return t;
}
// void push(np t){
// //遅延評価予定
// }
void rot(np t,bool b){
np x=t->p,y=x->p;
if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
t->ch[b]=x,x->p=t;
update(x);update(t);
if((t->p=y)){
if(y->ch[0]==x)y->ch[0]=t;
if(y->ch[1]==x)y->ch[1]=t;
update(y);
}
}
void splay(np t){
//push(t);
while(!t->is_root()){
np q=t->p;
if(q->is_root()){
//push(q), push(t);
rot(t,q->ch[0]==t);
}else{
np r=q->p;
//push(r), push(q), push(t);
bool b=r->ch[0]==q;
if(q->ch[1-b]==t)rot(q,b),rot(t,b);
else rot(t,1-b),rot(t,b);
}
}
}
void debug(np t){
if(!t)return;
debug(t->ch[0]);
cerr<<t->l<<"-"<<t->r<<" ";
debug(t->ch[1]);
}
constexpr static T et=T();
constexpr static T fn(T s,T t){
return s+t;
}
public:
euler_tour_tree(){}
euler_tour_tree(int sz){
ptr.resize(sz);
for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
}
int size(int s){
np t=get_node(s,s);
splay(t);
return t->sz;
}
bool same(int s,int t){
return same(get_node(s,s),get_node(t,t));
}
void set_size(int sz){
ptr.resize(sz);
for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
}
void update(int s,T x){
np t=get_node(s,s);
splay(t);
t->val=fn(t->val,x);
update(t);
}
void edge_update(int s,function<void(int,int)> g){
np t=get_node(s,s);
splay(t);
function<void(np)>dfs=[&](np t){
assert(t);
if(t->l<t->r&&t->exact){
splay(t);
t->exact=0;
update(t);
g(t->l,t->r);
return;
}
if(t->ch[0]&&t->ch[0]->child_exact)dfs(t->ch[0]);
else dfs(t->ch[1]);
};
while(t&&t->child_exact){
dfs(t);
splay(t);
}
}
bool try_reconnect(int s,function<bool(int)> f){
np t=get_node(s,s);
splay(t);
function<bool(np,int)>dfs=[&](np t,int idx)->bool{
assert(t);
if(t->edge_connected&&(size2(t->ch[0])==idx)){
splay(t);
return f(t->l);
}
if(idx<size2(t->ch[0]))return dfs(t->ch[0],idx);
else return dfs(t->ch[1],idx-size2(t->ch[0])-(t->edge_connected));
};
while(size2(t)){
if(dfs(t,0))return 1;
splay(t);
}
return 0;
}
void edge_connected_update(int s,bool b){
np t=get_node(s,s);
splay(t);
t->edge_connected=b;
update(t);
}
bool link(int l,int r){
if(same(l,r))return 0;
merge(reroot(get_node(l,l)),get_node(l,r),reroot(get_node(r,r)),get_node(r,l));
return 1;
}
bool cut(int l,int r){
if(ptr[l].find(r)==ptr[l].end())return 0;
np s,t,u;
tie(s,t,u)=split(get_node(l,r),get_node(r,l));
merge(s,u);
np p=ptr[l][r];
np q=ptr[r][l];
ptr[l].erase(r);
ptr[r].erase(l);
delete p;delete q;
return 1;
}
T get_sum(int p,int v){
cut(p,v);
np t=get_node(v,v);
splay(t);
T res=t->sum;
link(p,v);
return res;
}
T get_sum(int s){
np t=get_node(s,s);
splay(t);
return t->sum;
}
};
int dep=1;
vector<euler_tour_tree> ett;
vector<vector<unordered_set<int>>>edges;
int sz;
public:
dynamic_connectivity(int sz):sz(sz){
ett.emplace_back(sz);
edges.emplace_back(sz);
}
bool link(int s,int t){
if(s==t)return 0;
if(ett[0].link(s,t))return 1;
edges[0][s].insert(t);
edges[0][t].insert(s);
if(edges[0][s].size()==1)ett[0].edge_connected_update(s,1);
if(edges[0][t].size()==1)ett[0].edge_connected_update(t,1);
return 0;
}
bool same(int s,int t){
return ett[0].same(s,t);
}
int size(int s){
return ett[0].size(s);
}
vector<int>get_vertex(int s){
return ett[0].vertex_list(s);
}
void update(int s,T x){
ett[0].update(s,x);
}
T get_sum(int s){
return ett[0].get_sum(s);
}
bool cut(int s,int t){
if(s==t)return 0;
for(int i=0;i<dep;i++){
edges[i][s].erase(t);
edges[i][t].erase(s);
if(edges[i][s].size()==0)ett[i].edge_connected_update(s,0);
if(edges[i][t].size()==0)ett[i].edge_connected_update(t,0);
}
for(int i=dep-1;i>=0;i--){
if(ett[i].cut(s,t)){
if(dep-1==i){
dep++;
ett.emplace_back(sz);
edges.emplace_back(sz);
}
return !try_reconnect(s,t,i);
}
}
return 0;
}
bool try_reconnect(int s,int t,int k){
for(int i=0;i<k;i++){
ett[i].cut(s,t);
}
for(int i=k;i>=0;i--){
if(ett[i].size(s)>ett[i].size(t))swap(s,t);
function<void(int,int)> g=[&](int s,int t){ett[i+1].link(s,t);};
ett[i].edge_update(s,g);
function<bool(int)> f=[&](int x)->bool{
for(auto itr=edges[i][x].begin();itr!=edges[i][x].end();){
auto y=*itr;
itr=edges[i][x].erase(itr);
edges[i][y].erase(x);
if(edges[i][x].size()==0)ett[i].edge_connected_update(x,0);
if(edges[i][y].size()==0)ett[i].edge_connected_update(y,0);
if(ett[i].same(x,y)){
edges[i+1][x].insert(y);
edges[i+1][y].insert(x);
if(edges[i+1][x].size()==1)ett[i+1].edge_connected_update(x,1);
if(edges[i+1][y].size()==1)ett[i+1].edge_connected_update(y,1);
}else{
for(int j=0;j<=i;j++){
ett[j].link(x,y);
}
return 1;
}
}
return 0;
};
if(ett[i].try_reconnect(s,f))return 1;
}
return 0;
}
};
vector<vector<lint>> adj;
vector<bool> vis;
bool ok1,ok2;
lint comp,sz;
void dfs(lint x){
if(x%2) ok1=true;
else ok2=true;
vis[x]=true;
sz++;
for(auto i:adj[x]){
if(!vis[i]) dfs(i);
}
}
int main(){
lint t;
cin>>t;
while(t--){
lint n,q;
cin>>n>>q;
dynamic_connectivity<lint> dc(n+1);
vector<lint> p(n+1);
adj.clear();
adj.resize(n+1);
for(lint i=1;i<=n;i++){
cin>>p[i];
adj[i].push_back(p[i]);
adj[p[i]].push_back(i);
dc.link(i,p[i]);
if(i%2) dc.update(i,1);
}
lint cnt1=0,cnt2=0;
comp=0;
vis.clear();
vis.resize(n+1,false);
for(lint i=1;i<=n;i++){
if(!vis[i]){
ok1=false;
ok2=false;
comp++;
sz=0;
dfs(i);
if(ok1 && !ok2 && sz>1) cnt1++;
if(!ok1 && ok2 && sz>1) cnt2++;
}
}
cout<<(n-comp+2*(max(cnt1,cnt2)))<<" ";
while(q--){
lint x,y;
cin>>x>>y;
if(dc.same(x,y)){
comp++;
lint sum=dc.get_sum(x);
lint siz=dc.size(x);
if(sum==siz && siz>1) cnt1--;
if(sum==0 && siz>1) cnt2--;
dc.cut(x,p[x]);
dc.cut(y,p[y]);
dc.link(x,p[y]);
dc.link(y,p[x]);
sum=dc.get_sum(x);
siz=dc.size(x);
if(sum==siz && siz>1) cnt1++;
if(sum==0 && siz>1) cnt2++;
sum=dc.get_sum(y);
siz=dc.size(y);
if(sum==siz && siz>1) cnt1++;
if(sum==0 && siz>1) cnt2++;
}
else{
comp--;
lint sum=dc.get_sum(x);
lint siz=dc.size(x);
if(sum==siz && siz>1) cnt1--;
if(sum==0 && siz>1) cnt2--;
sum=dc.get_sum(y);
siz=dc.size(y);
if(sum==siz && siz>1) cnt1--;
if(sum==0 && siz>1) cnt2--;
lint sz1=dc.size(x);
if(sz1>2) dc.cut(x,p[x]);
sz1=dc.size(y);
if(sz1>2) dc.cut(y,p[y]);
dc.link(x,p[y]);
dc.link(y,p[x]);
sum=dc.get_sum(x);
siz=dc.size(x);
if(sum==siz && siz>1) cnt1++;
if(sum==0 && siz>1) cnt2++;
}
swap(p[x],p[y]);
cout<<(n-comp+2*(max(cnt1,cnt2)))<<" ";
}
cout<<"\n";
}
}