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;
}
}
B1. Count Population(Easy Version)
For, calculating the population remaining in B1 part, as we know that every person is standing on an integral coordinate, so the number of people remaining will simply be the number of points in the circle, we will simply use the brute force method, i.e., for every possible point with x ranging from -a to a and y ranging from -a to a, we will check it whether it is inside the circle (if x^2+y^2<a^2, then the point is inside the circle). And we will count the number of such points.
#include <iostream>
#include <algorithm>
#include <iterator>
#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
using i64 = long long;
#define ull long long int
void solve()
{
int a;
cin>>a;
ull count=0;
for(int i=-a;i<=a;i++)
{
for(int j=-a;j<=a;j++)
{
if(i*i+j*j<=a*a)count++;
}
}
cout<<count<<endl;
}
int main() {
speed
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
B2. Count Population(Hard Version)
For this version of the problem, the constraints differ from the previous version and hence the maximum time complexity that the code must have should be less than O(nlogn), there are two optimized versions of this part, one with time complexity of O(n) and the other with O(nlogn). Firstly lets have a look on O(nlogn) variant, we will divide the problem into 4 quarters as each one will have same number of points, finding only for the 1st quarter: We traverse the y axis from 1 to a(adding origin at the end because it should be counted only once) and for x coordinates, we apply binary search from 0 to a finding the last point between 0 to a that will be the part of the circle.
Now, taking a look on the O(n) version:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
using i64 = long long;
#define ull long long int
void solve()
{
ull a;
cin>>a;
ull count=0;
for(ull i=1;i<=a;i++)
{
ull st=0,en=a;
ull node=-1;
while(st<en)
{
ull mid=(st+en)/2;
if(mid*mid+i*i<=a*a)
{
node=mid;
st=mid+1;
}
else en=mid;
}
count+=node;
}
count+=a;
count*=4;count++;
cout<<count<<endl;
}
int main() {
speed
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
```c++
```
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;
}
This problem is purely \bf{implementation} based. First, we will make two matrices: \bf{height} and \bf{width}.
If there are consecutive numbers in a column of the height matrix starting from the index $$$(i,j)$$$ to $$$(i+x,j)$$$ where $$$i+x \le n$$$, then the elements starting from $$$A[i][j]$$$ to $$$A[i+x][j]$$$ will be there in matrix $$$B$$$ probably starting from the different index but they will be arranged vertically and also they will be in the same order as they were in $$$A$$$.
If there are consecutive numbers in a row of the width matrix starting from the index $$$(i,j)$$$ to $$$(i,j+x)$$$ where $$$j+x \le m$$$, then the elements starting from $$$A[i][j]$$$ to $$$A[i][j+x]$$$ will be there in matrix $$$B$$$ probably starting from the different index but they will be arranged horizontally and also they will be in the same order as they were in $$$A$$$.
Now, using these two matrices, we will calculate the maximum area of the largest common sub-matrix using tricky implementation.
You can see the code for a better understanding.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 5;
pair<ll,ll> position[N];
void solve(){
ll n,m;
cin>>n>>m;
ll a[n+5][m+5],b[n+5][m+5];
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>b[i][j];
position[b[i][j]]={i,j};
}
}
ll ans=1;
ll height[n+1][m+1],width[n+1][m+1];
memset(height,0,sizeof(height));
memset(width,0,sizeof(width));
auto up = [&](ll x,ll y){
return (position[x].first+1==position[y].first && position[x].second==position[y].second);
};
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(i==1) height[i][j]=1;
else{
if(up(a[i-1][j],a[i][j])){
height[i][j]=height[i-1][j]+1;
}
else height[i][j]=1;
}
}
}
auto right = [&](ll x,ll y){
return (position[x].first==position[y].first && position[x].second==position[y].second+1);
};
for(ll i=1;i<=n;i++){
for(ll j=m;j>=1;j--){
if(j==m) width[i][j]=1;
else{
if(right(a[i][j+1],a[i][j])){
width[i][j]=width[i][j+1]+1;
}
else width[i][j]=1;
}
}
}
vector<ll> L(1005), R(1005);
for(ll i=1;i<=n;i++){
ll column=1;
while(column<=m){
stack<ll> st;
ll l=column,r=column+width[i][column]-1;
for(ll j=l;j<=r;j++){
while(!st.empty() && height[i][st.top()]>=height[i][j]) {
st.pop();
}
if(st.empty()) L[j]=l;
else L[j]=st.top()+1;
st.push(j);
}
while(!st.empty()) st.pop();
for(ll j=r;j>=l;j--){
while(!st.empty() && height[i][st.top()]>=height[i][j]) {
st.pop();
}
if(st.empty()) R[j]=r;
else R[j]=st.top()-1;
st.push(j);
}
for(ll j=l;j<=r;j++){
ans=max(ans,height[i][j]*(R[j]-L[j]+1));
}
column+=width[i][column];
}
}
cout<<ans<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
