Idea:MathModel
Note that $$$s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$$$ , so we can assume the sum as $$$f$$$.
And let's denote the median digit by $$$h$$$ , thus the sum is $$$2f+h$$$ , it can be shown that $$$h$$$ can be possibly any digit , thus we can construct all sums which lies between minimum and maximum inclusive .
Now Let's do the same for even values of $$$n$$$ we can re-express $$$s$$$ as
Using the symmetric property we can see $$$s_{\lfloor \frac{n}{2} \rfloor}=s_{\lfloor \frac{n}{2} \rfloor+1}$$$ , if we denote one digit by $$$h$$$ thus the sum of medians is $$$2h$$$ and if we denote the left and right segments by $$$f$$$ as we did for odd $$$n$$$ then we have $$$m=2f+2h=2(f+h)$$$ thus for even $$$n$$$ we have an additional condition that sum must be even
Thus Total Complexity for each test case is $$$\mathcal{O}(1)$$$ time .
for _ in range(int(input())):
n,m= map(int, input().split())
if(m >= n and m <= 9 * n and (n % 2 != 0 or m % 2 == 0)):
print("YES")
else:
print("NO")
Idea:Yugandhar_Master
First solve:sevlll777
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
First solve:sevlll777
Bob will win the game if all piles contains even number of stones, because Bob can follow the Alice operations. Otherwise Alice wins(i.e., atlest one pile conatins odd number of stones).
So Now our task is to construct a permutation $$$p$$$ where subarrays containing atleast one odd element are maximum possible.
It is easy to see that odd elements at odd position increases the subarray count. So we can construct the permutation $$$1,2,3,...,n$$$.
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;
for(ll i=0;i<n;i++) cout<<i+1<<" ";
cout<<"\n";
}
}
C2: Yet Another Nim Game(Counting version)
Idea:Yugandhar_Master
First solve:sevlll777
Note that, for winning of Alice we need odd elements so, let $$$v$$$ is the answer for odd $$$i$$$, then for $$$i+1$$$ the answer is $$$2*v$$$, because from odd $$$i$$$ to even $$$i+1$$$ we are taking extra even element so this element shares either end of the array.
Let $$$v$$$ is the answer for even $$$i$$$, then for $$$i+1$$$ the answer is $$$v*\frac{((i/2)+2)*((i/2)+1)}{2}$$$, because of the extra odd element in $$$i+1$$$.
By this way we can calculate our answer.
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);
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
First solve:Egor
If you observe carefully we don't need to care about the characters in the given string.
Let $$$+$$$ be operation 1 and $$$-$$$ be operation 2. Now our task is to count the different strings of length $$$m$$$ $$$+++--++--++--...$$$ such that prefix sum at point $$$i$$$ is maximum( $$$0$$$, sum of first $$$i$$$ elements) and prefix sum at point $$$m$$$ is equal to $$$n$$$.
This can done using dynamic programing.
Time Complexity : $$$O(nm)$$$
#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
First solve:sevlll777
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.
Divide the array into $$$B$$$ blocks, each with a length of $$$L= \frac{n}{B}$$$. We use set to maintain the information of each block, so that the query only uses the lower_bond() function. The complexity of the modification is $$$O(\log(n))$$$. The complexity of the query is $$$O(L+B\log(n))$$$. So we choose $$$L=\sqrt{n\log(n)}$$$
Time Complexity : $$$O(n\sqrt{n\log(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 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
First solve:pandaforever
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$$$.
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 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;
}
}
}
}
