Editorial
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.
Code
#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?
Editorial
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.
Code
#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;
}
}
E. https://codeforces.net/gym/437445/problem/E
Editorial
Code
#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;
}