Can someone explain what’s wrong with my code? I am first calculating the positions of ones in the string to find the longest segment of zeros. Then I am calculating the remaining groups of zeros to check if they contribute anything to the number of vacations. If they contribute, then I am adding them to the original sum.
void solve() {
int n, x; cin >> n >> x;
string s; cin >> s;
// For string with length less than 2
if(s.length() < 2) {
cout << 1/x << "\n";
return;
}
// Keep track of positions of 1's to calculate zeros between two 1's
vector<int> ones;
ones.pb(0);
for(int i = 0; i < n; i++) {
if(s[i] == '1')
ones.pb(i);
}
ones.pb(s.length() - 1);
int curr = -INF;
int idx = 0;
// Calculate the length of maximum segment of ones
for(int i = 1; i < ones.size() - 1; i++) {
int sum = 0;
if(s[ones[i - 1]] == '1') {
sum += ones[i] - ones[i - 1] - 1;
}
else
sum += ones[i] - ones[i - 1];
if(s[ones[i+1]] == '1') {
sum += ones[i+1] - ones[i] - 1;
}
else
sum += ones[i+1] - ones[i];
if(sum > curr) {
curr = sum;
idx = ones[i];
}
}
// Calculate the remaining groups of zeros to check if they contribute to the vacations days
vector<int> zeros;
int cnt = 0;
int nid = -1;
for(int i = idx + 1; i < n; i++) {
if(s[i] == '1') {
nid = i;
break;
}
}
if(nid != -1) {
for(int i = nid; i < n; i++) {
if(s[i] == '0')
cnt++;
else {
zeros.pb(cnt);
cnt = 0;
}
}
zeros.pb(cnt);
}
int days = (curr + 1) / x;
for(int i : zeros) {
days += (i / x);
}
cout << (curr == -INF ? s.length() / x : days) << "\n";
}
why i am getting WA for this solution: #include <bits/stdc++.h>
using namespace std;
int main()
{
// your code goes here
int t;
cin>>t;
while(t–)
{ string s;
int n,k;
cin>>n>>k;
cin>>s;
int ar[n];
string st[n];
int ct=0;
for(int i=0;i<s.size();i++)
{
if(s[i]==‘1’)
{
st[ct]=s;
st[ct][i]=‘0’;
ct++;
}
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);
