In this question, there are only 2 types of chess boards possible, starting with white and starting with black. So we can check this 2 cases manually. Another approach is to check that now to adjacent cells have same color.
#include <bits/stdc++.h>
using namespace std;
int main(){
string str[8];
for(int i=0;i<8;i++){
cin>>str[i];
}
int check1=1,check2=1;
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(((str[i][j]-'0'))!=((i%2)^(j%2))){
check1=0;
}
}
}
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if((str[i][j]-'0')!=((i%2)^(j%2)^1)){
check2=0;
}
}
}
if(check1 || check2){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
D. Can you minimize the string?
We can observe that right rotate operation is same as you select any element with index j, remove it and insert it in ith index. That's why we will select smallest element and place it in sorted position and if there are multiple elements then we will select element which came at last.
#include <bits/stdc++.h>
using namespace std;
int main(){
int tc;
cin>>tc;
while(tc--){
int n,k;
cin>>n>>k;
string str;
cin>>str;
string str2=str;
vector<int> freq(26,0);
for(int i=0;i<n;i++){
freq[str[i]-'a']++;
}
sort(str2.begin(),str2.end());
// cout<<str<<endl;
// cout<<str2<<endl;
int j=0;
for(int i=0;i<n;i++){
if(k==0){
break;
}
cout<<str2[i];
freq[str2[i]-'a']--;
if(str2[i]!=str[j]){
k--;
}
else{
j++;
while(j<n && str[j]<str2[i]){
j++;
}
}
}
for(int i=j;i<n;i++){
if(freq[str[i]-'a']!=0){
cout<<str[i];
freq[str[i]-'a']--;
}
}
cout<<endl;
}
}
Let's first calculate that for any node $$$u$$$, $$$size[u]$$$ of is number of nodes between $$$u(real)$$$ and $$$u(image)$$$. We can find this with the help of depth-first-search in $$$O(n)$$$ time complexity.
We can observe that number of topological sorts between $$$u(real)$$$ and $$$u(image)$$$, denoted as $$$ans[u]$$$ is equal to:
We can solve this with recursive coding with the termination condition at leaf node of given tree for which answer is 1.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll modpower(ll n,ll a,ll p){ ll res=1; while(a){ if(a%2) res= ((res*n)%p) ,a--; else n=((n*n)%p),a/=2;} return res;}
const ll N=2e5;
const ll MOD=1e9+7;
vector<int> edge[N];
int sz[N];
ll ans=1;
ll fact[N];
ll ifact[N];
void dfs(int ind,int par){
sz[ind]=0;
for(auto z:edge[ind]){
if(par==z)continue;
dfs(z,ind);
sz[ind]+=sz[z];
}
ans*=(fact[sz[ind]]);
ans%=MOD;
for(auto z:edge[ind]){
if(z==par)continue;
ans*=(ifact[sz[z]]);
ans%=MOD;
}
if(sz[ind]==0)sz[ind]++;
else sz[ind]+=2;
}
int main(){
long long i;
fact[0]=1;
fact[1]=1;
for(i=2;i<N;i++){
fact[i]=fact[i-1]*i;
fact[i]%=MOD;
}
ifact[N-1]=modpower(fact[N-1],MOD-2,MOD);
for(i=(N-2);i>=0;i--){
ifact[i]=ifact[i+1]*(i+1);
ifact[i]%=MOD;
}
int n;
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
edge[u-1].push_back(v-1);
edge[v-1].push_back(u-1);
}
dfs(0,-1);
cout<<ans<<endl;
return 0;
}