Idea:Yugandhar_Master
Let $$$count$$$ be the number of $$$1's$$$ in the given binary string $$$S$$$.
Note that if we perform atleast one operation there will be atleast $$$k$$$ $$$0's$$$. So it is always optimal to get minimum $$$k$$$ $$$0's$$$ once we start doing operations.
Let $$$S$$$ = $$$s_1s_2s_3s_4s_5s_6s_7s_8s_9s_{10}$$$ and $$$k = 3$$$
we can do operations in the following way to get $$$k$$$ $$$0's$$$.
Choose $$$i=3$$$, $$$S$$$ = $$$111000s_7s_8s_9s_{10}$$$
Choose $$$i=6$$$, $$$S$$$ = $$$111111000s_{10}$$$
Choose $$$i=7$$$, $$$S$$$ = $$$1111111000$$$.
By this way we can always get minimum of $$$k$$$ $$$0's$$$ once we start doing operations.
Hence, the answer to the problem is maximum( $$$count$$$ , $$$n-k$$$ ).
Time Complexity : $$$O(n)$$$
#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;
string s;
cin>>s;
int ans=count(s.begin(),s.end(),'1');
ans=max(ans,n-k);
cout<<ans<<"\n";
}
}
Idea:Yugandhar_Master
From the above problem, we can know what are the maximum possible $$$1's$$$ in $$$S$$$ we can get for a given $$$k$$$. Now we have to think minimum operations required to get those maximum $$$1's$$$. For given $$$i$$$ let's call $$$S_{i},S_{i-1},S_{i-2},...,S_{i-k+2},S_{i-k+1}$$$ as Left part and $$$S_{i+1},S_{i+2},S_{i+3},...,S_{i+k-1},S_{i+k}$$$ as Right part. It is easy to see that If we wish to do operation then there will be atleast one $$$0$$$ in Left part makes the operation optimal(Because it will decrease the $$$0$$$ count and gradually increase the $$$1$$$ count). So we can come to conclusion that, whenever we have to do the operation, Left part have more number of $$$0's$$$ and $$$S_1 = S_2 = S_3 = ... = S_{i-k} = 1$$$.
Time Complexity : $$$O(n)$$$
#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--){
ll n;
cin>>n;
string s;
cin>>s;
ll ind1=-1,ind2=-1;
for(ll i=0;i<n;i++){
if(s[i]=='0') ind2=i;
}
for(ll i=n-1;i>=0;i--){
if(s[i]=='0') ind1=i;
}
ll cnt=count(s.begin(),s.end(),'1');
for(ll k=1;k<=(n/2);k++){
if(cnt>=(n-k)) cout<<"0 ";
else{
ll l=ind1,r=ind2;
r-=k;
cout<<(r-l+k)/k<<" ";
}
}
cout<<"\n";
}
}
C1: Yet Another Nim Game (Constructive version)
Idea:Yugandhar_Master
#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--){
ll n;
cin>>n;
for(ll i=0;i<n;i++) cout<<i+1<<" ";
cout<<"\n";
}
}
C2: Yet Another Nim Game(Counting version)
Idea:Yugandhar_Master
#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;
const ll N=3e5+11;
vector<ll> v;
int main(){
fast;
v.resize(N);
v[1]=1;
v[2]=2;
ll val=3,diff=3;
for(ll i=3;i<N;i+=2){
v[i]=(v[i-1]*(val%mod))%mod;
v[i+1]=(v[i]*2)%mod;
val+=diff;
diff++;
}
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
cout<<v[n]<<"\n";
}
}
Idea:Yugandhar_Master
#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;
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll m,n;
cin>>m>>n;
string s;
cin>>s;
if(m>n) cout<<"0\n";
else{
vector<ll> dp(n+1);
dp[0]=1;
for(ll i=0;i<n;i++){
vector<ll> ndp(n+1);
for(ll j=0;j<=i;j++){
ndp[j+1]=(ndp[j+1]+dp[j])%mod;
if(j>0) ndp[j-1]=(ndp[j-1]+(26*dp[j])%mod)%mod;
else ndp[j]=(ndp[j]+dp[j])%mod;
}
dp=ndp;
}
cout<<dp[m]<<"\n";
}
}
}
Idea:Yugandhar_Master
It is easy to see that, for a given query we need the count of the lowerbound of given $$$x$$$ in $$$l$$$ to $$$r$$$ segment.
This can be done using various data structures, but in Merge sort tree the constant factor is high so it will give TLE if you didn't implement it properly.
The below solution is based on square-root decomposition.
Time Complexity : $$$O(n\sqrt{n})$$$
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
//#define int long long
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=1000000001;
const int B=3000;//100;
int T,n,q;
int a[N],bnum[N];
/*
struct cmp1 //自定义升序
{
bool operator()(pair<int,int> v1,pair<int,int> v2)
{
return v1.first < v2.first;
}
};
struct cmp2 //自定义降序
{
bool operator()(pair<int,int> v1,pair<int,int> v2)
{
return v1.first > v2.first;
}
};
*/
struct block
{
set<pair<int,int> > S;
unordered_map<int,int> cnt;
}blk[N];
void init()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n+4;i++)
{
blk[i].S.clear();
blk[i].cnt.clear();
}
for(int i=1;i<=n;i++)
{
bnum[i]=i/B+1;
blk[bnum[i]].S.insert(make_pair(a[i],i));
blk[bnum[i]].cnt[a[i]]++;
}
}
void solve()
{
for(int i=1;i<=q;i++)
{
int t;
cin>>t;
if(t==1)
{
int l,r,x,mxl=-INF,cl=0,mnr=INF,cr=0; //l:<x,r:>=x
cin>>l>>r>>x;
if(bnum[l]==bnum[r])
{
for(int i=l;i<=r;i++)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
}
else
{
for(int i=l;bnum[i]==bnum[l];i++)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
for(int i=r;bnum[i]==bnum[r];i--)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
for(int i=bnum[l]+1;i<=bnum[r]-1;i++)
{
set<pair<int,int> >::iterator it=blk[i].S.lower_bound(make_pair(x,0));
if(it!=blk[i].S.end())
{
if(it->first<mnr) mnr=it->first,cr=blk[i].cnt[it->first];
else if(it->first==mnr) cr+=blk[i].cnt[it->first];
}
if(it==blk[i].S.begin()) continue;
it--;
if(it->first>mxl) mxl=it->first,cl=blk[i].cnt[it->first];
else if(it->first==mxl) cl+=blk[i].cnt[it->first];
}
}
//
//cout<<"mxl="<<mxl<<" mnr="<<mnr<<'\n';
//
if(mxl==-INF) cout<<cr<<'\n';
else if(mnr==INF) cout<<cl<<'\n';
else if(x-mxl==mnr-x) cout<<cl+cr<<'\n';
else if(x-mxl<mnr-x) cout<<cl<<'\n';
else cout<<cr<<'\n';
}
else
{
int p,v;
cin>>p>>v;
blk[bnum[p]].S.erase(make_pair(a[p],p));
blk[bnum[p]].cnt[a[p]]--;
a[p]=v;
blk[bnum[p]].S.insert(make_pair(a[p],p));
blk[bnum[p]].cnt[a[p]]++;
}
}
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
signed main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Idea:Yugandhar_Master
Lets root the tree at any node, let $$$r$$$ be the root of the tree.
We can solve the problem using $$$DP$$$ in the following way:
$$$dp1[i][j]$$$ = The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, such that the colour of all nodes containing in the component where node $$$i$$$ is included is red.
$$$dp2[i][j]$$$ =The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, where all components except the one containing node $$$i$$$ doesn't satisfy the condition of "Perfect Tree"(i.e., all other components are non-perfect trees).
If there is no value for particular $$$DP$$$ state, then set it into $$$♾️$$$.
The answer to problem is $$$j-1$$$ where $$$dp1[r][j]<♾️$$$ or $$$dp2[r][j] < 0$$$.
#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 n;
vector<ll> a;
vector<vector<ll>> adj;
vector<pair<ll,ll>> dfs(ll x, ll p){
vector<pair<ll,ll>> dp;
dp.push_back({0,1e18});
for(auto i:adj[x]){
if(i!=p){
vector<pair<ll,ll>> dp1=dfs(i,x);
ll n1=(ll)dp1.size();
dp1.push_back({1e18,1e18});
for(ll j=n1-1;j>=0;j--){
if(dp1[j].first<1e18 || dp1[j].second<0){
dp1[j+1].first=min((ll)0,dp1[j+1].first);
}
}
ll n2=(ll)dp.size()-1;
vector<pair<ll,ll>> dp2(n1+n2+1,{1e18,1e18});
for(ll j=0;j<=n2;j++){
for(ll k=0;k<=n1;k++){
dp2[j+k].first=min(dp2[j+k].first,dp[j].first+dp1[k].first);
dp2[j+k].second=min(dp2[j+k].second,dp[j].first+dp1[k].second);
dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].first);
dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].second);
}
}
dp=dp2;
}
}
ll n2=(ll)dp.size()-1;
vector<pair<ll,ll>> dp2(n2+1);
for(ll i=0;i<=n2;i++){
if(a[x]>0){
dp2[i].first=dp[i].first+a[x];
dp2[i].second=dp[i].second+a[x];
}
else{
dp2[i].first=1e18;
dp2[i].second=min(dp[i].first,dp[i].second)+a[x];
}
}
return dp2;
}
int main(){
fast;
ll t;
t=1;
while(t--){
cin>>n;
a.clear();
a.resize(n);
for(ll i=0;i<n;i++) cin>>a[i];
string s;
cin>>s;
for(ll i=0;i<n;i++){
if(s[i]=='1') a[i]=-a[i];
}
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);
}
vector<pair<ll,ll>> dp=dfs(0,-1);
for(ll i=0;i<n;i++){
if(dp[i].first<1e18 || dp[i].second<0){
cout<<i;
break;
}
}
}
}
