I calculated prefix and suffix and check if i flip 1 to 0 then total number of consecutive 0 and take max of that
It is giving CORRECT ON SUBTASK 1 but WA on any other why
void solve()
{
int n,x; cin>>n>>x;
string bin; cin>>bin;
vector<int> pre(n);
vector<int> suf(n);
int count = 0;
for(int i = 0;i<n;i++)
{
if(bin[i]=='0')
{
count++;
pre[i]=count;
}
else{
pre[i]=count;
count=0;
}
}
count=0;
for(int i = n-1;i>=0;i--)
{
if(bin[i]=='0')
{
count++;
suf[i]=count;
}
else{
suf[i]=count;
count=0;
}
}
int m=-1;
for(int i= 0;i<n;i++)
{
int local = 0;
if(bin[i]!='0')
local = pre[i]+suf[i]+1;
else
local = pre[i]+suf[i]-1;
m=max(m,local);
}
int xx = ceil(m/x);
cout<<ceil(m/x);
}
int32_t main()
{
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
One thing we can observe is that by taking an extra holiday, you can improve the number of vacations by no more than 1.
i.e., if \text{orig\_ans} is the maximum number of vacations without taking extra holiday, then by taking 1 extra holiday, we can get no more than (\text{orig\_ans} + 1) vacations.
Now, it looks easier - we can iterate over all i where s[i] = 1 and check if we can get 1 extra vacation.
Because you are calculating only the segment of zeroes where you flipped the ‘1’. There can be other segments of ‘0’ that can contribute to vacations without flipping any bit .
For example
N = 15 and X =3
100010100000001
Your m will be 9 (index = 5 to 13 ) and hence final answer is just 9/3=3
But you also have to add the segment of zeroes from index = 1 to 3. Hence correct answer is 1+3=4
You are selecting the longest subarray having at most one ‘1’.
This will not give the correct answer always as in this test case.
First you calculate the answer in the original string without flipping any ‘1’.
Then for every ‘1’ position, see by flipping which ‘1’ increases your answer.
Lets the initial answer is ans.
At any position i such that str[i]==‘1’ , you have pre[i] and suff[i].
Then do this :-
int temp = ans;
temp -= pre[i]/x;
temp -=suff[i]/x;
temp +=(pre[i] + suff[i] +1 )/x ;
// +1 because you are flipping str[i]=='1' position
final_ans = max(final_ans,temp);
Can you tell where do I go wrong? I find the ans when if chef didnt take any holidays. I check if there if any contiguous string of ‘0’ is present which is one less than X, 2X … etc. or length%X == 1. Also I check If the string contains atleast a single ‘1’. If both these conditions satsify, I increment the ans found initially otherwise I leave the ans as it is.
int t ;
cin >> t ;
while(t--){
int n, x, ans ;
cin >> n >> x ;
string s ;
cin >> s ;
int sets = 0 ;
bool atleast1 = false, needed = false ;
for(int i = 0 ; i < n ; i++){
if(s[i] == '1'){
atleast1 = true ;
}
else{
int tmp = 0 ;
while(i<n && s[i] == '0'){
tmp++ ;
i++;
}
if(i<n && s[i] == '1')
atleast1 = true ;
if(tmp % x == 1 || x == 1)
needed = true ;
sets += tmp/x ;
}
}
ans = sets ;
if(atleast1 && needed)
ans++ ;
if(ans==0)
ans++ ;
cout << ans << '\n' ;
}
