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$$$.
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";
}
}
Idea:Yugandhar_Master
First solve:Egor
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";
}
}
}
}
Idea:Yugandhar_Master
First solve:Egor
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";
}
}
can you solve the problem for $$$1 \le a_i \le 10^{18}$$$ ?
Idea:Yugandhar_Master
First solve:Egor
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;
}
}
}
}
can you solve the problem for range update instead of point update ?
Idea:Yugandhar_Master
First solve:lonely_forever
constructive algorithm
tree
There will be no tree if the grid $$$a$$$ doesn't satisfy atleast one of the following condition :
- $$$a_{ij} = a_{ji}$$$
- $$$a_{ii}=i$$$
- $$$a_{ij} \le a_{(a_{ij})j}$$$
Otherwise we can construct the tree in many ways, one of the possible way is:
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)$$$.
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";
}
}
Idea:Yugandhar_Master
First solve:methanol
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, where $$$i_1$$$ and $$$i_2$$$ belongs to set $$$k$$$.
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";
}
}
can you construnct any permutation which satisfies the condition for $$$n \le 10^6$$$ ?
Idea:Yugandhar_Master
First solve:
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
Statement of problem E is misleading. I was thinking about arbitrary values of the nodes but not the indexes of the nodes.
Yes but anyway still doable, given E was nothing but value of node i is i. But coming to the misleading I didn't mentioned special values of nodes in the Statement and in sample tests too so I thought no one will confuse. But sorry for that inconvenience
The complexity of problem C should be $$$O(nlog(a_i)+t(D(a_i)+f(a_i)))$$$, where $$$f(a_i)$$$ is the complexity for factorization. Using Pollard's rho algorithm C can be solved with $$$a_i\leq10^{14}$$$ (or $$$10^{18}$$$ even if $$$t\leq100$$$). Is there any way to solve it in faster than this time complexity (e.g. with the original constraint of $$$t\leq1000$$$ ? I don't think that fits in the 2s time limit.)
You can solve this problem using any data structure which finds range gcd faster (for example sparse table). Take prefix gcd array $$$p$$$ and suffix gcd array $$$s$$$ let's call $$$x$$$ and $$$y$$$ special indices where $$$p[x]<p[x-1]$$$ and $$$s[y]<s[y+1]$$$. Note that these special indices are limited. So you can choose any two special factors and assume that you are changing them, for this purpose you need to calculate range gcd faster. Total Time complexity $$$O((n+β^2)logn)$$$ where $$$β$$$ is number of special indices. The upper bound of $$$β$$$ can be around $$$60 -> log(10^{18})$$$. Which got ACed in around $$$200$$$ s in C++
Simpler solution for C same idea as MAXIMGCD on codechef, works for values upto 1e18 too, only indices where prefix or suffix GCD changes matter and there are logarithmic of them so brute over them with some range query DS. https://mirror.codeforces.com/gym/105491/submission/290413088
The problem C can be solved more easily using Idea 3 of this post, and this also works for the bonus problem ($$$a_i \leq 10^{18}$$$).
Really enjoyed the contest . I hope keep more such contests frequently
"It will posted after the first solve or tomorrow"
Well, tomorrow passed 4 days ago and no one solved it...