MAXVAC - Editorial

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Lavish Gupta

Simple

Prefix Sum

PROBLEM:

You are given Chef’s calendar for the next N days, defined as a binary string S of length N where S_i = 0 means that Chef has a holiday on the i^{th} day from now, and S_i = 1 means that Chef has to work on that day.

Chef wants to plan his vacations. For each vacation, Chef needs X consecutive holidays in his calendar. Obviously, he can only go on one vacation at a time.

Chef can take at most one extra holiday. That is, he can flip at most one digit in S from 1 to 0. If he does this optimally, what is the maximum number of vacations that he can go on?

EXPLANATION:

What if no extra holiday is allowed?

Consider a contiguous segment of 0's of length len. The number of times Chef can go to a vacation during this contiguous segment will be len/K.

So, if no extra holiday is allowed, we can first get the length of all contiguous segments of 0's in the string. The answer would be the sum of len/X for all len values that we encounter. Let’s call this answer orig\_ans

What happens when a holiday is taken?

Let’s say we take a holiday on i^{th} day. Then, the contiguous segment of 0's ending at index i-1 is merged with the contiguous segment of 0's starting at index i+1, with S_i also becoming 0.

So now, we need to account for these changes in the previous contiguous segments of 0's to get the maximum number of vacations that Chef can go to, when a holiday is taken on i^{th} day.

Calculating efficiently

The information that we need, when taking a holiday on i^{th} day, is the length of contiguous segment of 0's ending at index i-1 (let’s say len\_end_{i-1}) and the length of contiguous segment of 0's starting at index i+1 (let’s say len\_start_{i+1}).

Consider the original contiguous segments of 0's. After this change, we now have removed contiguous segments of length len\_end_{i-1} and len\_start_{i+1}, and have added a new segment of length len_i = len\_end_{i-1} + len\_start_{i+1} + 1.

So the answer when a holiday is taken on i^{th} day, let say ans_i will be:
ans_i = orig\_ans - \frac{len\_end_{i-1}}{K} - \frac{len\_start_{i+1}}{K} + \frac{len_i}{K}.

To get our final answer, we need to take the max of ans_i \forall i: S_i = 1

So we can first calculate the length of contiguous segments of 0's that ends at index i, and length of contiguous segments of 0's that start at index i, for all 1 \leq i \leq N. After this computation, we can efficiently calculate the maximum number of vacations that the Chef can go to, when the holiday is taken on i^{th} day, and finally take the maximum of all these numbers.

TIME COMPLEXITY:

The above approach will take O(N) time for each test case.

SOLUTION:

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, x;
cin>>n>>x;
string s;
cin>>s;
int ans = 0;
vector<int> v;
v.push_back(-1);
int tot = 0;
for(int i = 0; i < n; i++){
if(s[i] == '1'){
tot += (i - v.back() - 1) / x;
v.push_back(i);
}
}
tot += (n - v.back() - 1)/x;
v.push_back(n);
for(int i = 1; i < v.size() - 1; i++){
int temp = tot - (v[i] - v[i - 1] - 1) / x - (v[i + 1] - v[i] - 1) / x + (v[i + 1] - v[i - 1] - 1) / x;
ans = max(ans, temp);
}
cout<<ans<<"\n";
}
return 0;
}

Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std ;

const ll z = 1000000007 ;

void solve()
{
int n , k ;
cin >> n >> k ;
string str ;
cin >> str ;

int left[n] , right[n] ;

left[0] = (str[0] == '0') ;
right[n-1] = (str[n-1] == '0') ;

for(int i = 1 ; i < n ; i++)
{
if(str[i] == '0')
left[i] = left[i-1]+1 ;
else
left[i] = 0 ;
}

for(int i = n-2 ; i >= 0 ; i--)
{
if(str[i] == '0')
right[i] = right[i+1]+1 ;
else
right[i] = 0 ;
}

int ans = 0 ;
for(int i = 0 ; i < n ; i++)
{
if(left[i] == 0 && i > 0)
ans += (left[i-1]/k) ;
}

ans += left[n-1]/k ;
int orig_ans = ans ;

for(int i = 0 ; i < n ; i++)
{
if(str[i] == '0')
continue ;

int orig_left = 0 , orig_right = 0 ;
if(i > 0)
orig_left = left[i-1] ;
if(i < n-1)
orig_right = right[i+1] ;

int change = (orig_left + orig_right + 1)/k - orig_right/k - orig_left/k ;
ans = max(ans, orig_ans+change) ;
}
cout << ans << endl ;
return ;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t;
cin >> t ;
while(t--)
solve() ;

return 0;
}

6 Likes

I calculated the longest subarray such that there is only a single ‘1’ in it.
After that I flipped the ‘1’ to ‘0’.
And then I found the contiguous segments of 0’s in the modified string and incremented the answer accordingly , i.e if the segment contains A zeros , then ans+=A/X;

Plz tell why this is wrong

#include <bits/stdc++.h>
#define int long long int
using namespace std;

void solve()
{
int n, x;
cin >> n >> x;
string str;
cin >> str;
int zero_count = 0;
int i = 0, j = 0, cnt = 0, ans = 0;
int final = 0;
int left;
int right;
//longest subarray having at most one '1' => str[left...right]
for (; j < n; ++j) {
cnt += str[j] == '1';
while (cnt > 1) cnt -= str[i++] == '1';
if ((j - i + 1) > ans)
{
left = i;
right = j;
ans = max(ans, j - i + 1);
}
}
for (int i = left; i <= right; ++i)
{
if (str[i] == '1')
{str[i] = '0'; break;}
}
for (int i = 0; i < n; ++i)
{
if (str[i] == '0')
zero_count++;
else
{
final += (zero_count / x);
zero_count = 0;
}
}
if (str[n - 1] != '1')
final += (zero_count / x);
cout << final << endl;

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tc = 1;
cin >> tc;
while (tc--)
{
solve();
}

}

1 Like

Can anyone tell which test case it is give WA?
Here is my code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using vb = vector<bool>;

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define eb emplace_back
#define ins insert
#define mp make_pair
#define mt make_tuple
#define rev reverse
#define precise(x) cout << fixed << setprecision(x)
#define accum(x, y) accumulate(all(x), y)
#define rep(x) for(int i = 0; i < x; i++)
#define rep2(x, y) for(int i = x; i < y; i++)
#define rep3(x, y, z) for(int i = x; j < y; i += z)
#define per(x) for(int i = x; i >= 0; i--)
#define per2(x, y) for(int i = x; i >= y; i--)
#define per3(x, y, z) for(int i = x; i >= y; i -= z)
#define repa(x, y) for(auto x : y)
#define repr(x, y) for(auto &x : y)
#define krep(i, x) for(int i = 0; i < x; i++)
#define krep2(i, x, y) for(int i = x; i < y; i++)
#define krep3(i, x, y, z) for(int i = x; i < y; i += z)
#define debug(x) cout << #x << " = " << x << endl
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
#define len(x) (int)x.length()

const int dr4[] = {0, 1, 0, -1};
const int dc4[] = {1, 0, -1, 0};

const int dr8[] = {0, 1, 0, -1, 1, -1, -1, 1};
const int dc8[] = {1, 0, -1, 0, -1, -1, 1, 1};

void setIO(str name = "") {
cin.tie(0) -> sync_with_stdio(0);
if(sz(name)) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}

template<typename T>
bool ckmax(T &a, T b) { return b > a ? a = b, 1 : 0; };
template<typename T>
bool ckmin(T &a, T b) { return b < a ? a = b, 1 : 0; };

// Main Code

void solve() {
int n, x; cin >> n >> x;
str s; cin >> s;
vpi idx;
pi each;
int i = 0;
while(i < n) {
if(s[i] == '0' && !each.fi) each.fi = i + 1;
else if(s[i] == '1' && !each.se && each.fi) {
each.se = i;
idx.eb(each);
each.fi = each.se = 0;
}
++i;
}
if(each.fi && !each.se) {
each.se = i;
idx.eb(each);
}
int res = 0;
each = { -1, -1 };
rep2(1, sz(idx)) {
int diff1 = idx[i].se - idx[i].fi + 1;
int diff2 = idx[i - 1].se - idx[i - 1].fi + 1;
if(idx[i].fi - idx[i - 1].se == 2) {
int diff = diff1 + diff2 + 1;
if(res < diff && diff >= x) {
res = diff;
each.fi = i - 1;
each.se = i;
}
}
}
rep(sz(idx)) {
if(i != each.fi && i != each.se) {
int diff = idx[i].se - idx[i].fi + 1;
if(diff >= x) res += diff;
}
}
cout << res / x << endl;
}

int main() {
setIO();
int tc = 1; cin >> tc;
while(tc--) solve();
return 0;
}


I have counted max no. of consecutive zeroes including one 1 and divided it by size of 1 vacation to get total no. of vacations.
Can anyone tell me where it’ll fail.

t = int(input())

while t > 0:
t -= 1
n, x = map(int, input().split())
s = input()
flag = 0
max_count = 0
count = 0
prev = 0
i = 0
while i < n:
if flag == 1 and s[i] == ‘1’:
if count > max_count:
max_count = count
count = i-prev-1
prev = i
flag = 1
elif flag == 0 and s[i] == ‘1’:
prev = i
flag = 1

    count += 1
i += 1
if count > max_count:
max_count = count
print(max_count//x)

Lets consider the following input=

N= 13
X= 5
0000001001000

now if we find longest subarray with only single 1 in it, it would be from index 0 to index 8, ie: “000000100”. let’s flip the 1 according to your solution. Therefore we get 0000000001000 as X =5 only one vacation can be taken in this case.

But the solution is as follows- flip the second one so we get:
“0000001000000”, in this we see that 2 vacations can be taken.

The goal should be to flip the 1 such thats the merged interval has an extra segment of X 0s, this might not be true for the longest contiguous segment of 0s.

7 Likes

2
7 1
1111111
7 2
1100000

Yours:
0
2

Correct:
1
3

Can anyone tell me a test case where this code will fail?
Or suggest me where there is a error?
I have calculated total consecutive zeroes before last ‘1’ and before current ‘1’ and calculated the length. At the end if say entire string is full of zeroes then i have subtracted a value since no flipping is required. Please help

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<b;i++)

#define take(n) ll int n;cin>>n;

#define array(n,name) ll int *name=new ll int[n]

#define Zubin ios::sync_with_stdio(false);

#define Shah cin.tie(NULL);cout.tie(0);

#define nl cout<<endl;

using namespace std;

int main(){

Zubin Shah

int N;

cin>>N;

while(N--){

take(n);

take(k);

char array[n];

cin>>array;

int prevrecord=0;

int currentrecord=0;

int ans=1;

for(int i=0;i<n;i++){

if(array[i]=='1'){

ans=max(prevrecord+currentrecord+1,ans);

prevrecord=currentrecord;

currentrecord=0;

}

else currentrecord++;

}

ans=max(prevrecord+currentrecord+1,ans);

if(currentrecord==n) ans-=1;

cout<<ans/k<<endl;

}

return 0;

}


Hi All,
Does anyone know where my approach will fail ?
I went through the whole string from left to write checking required number of days(subarrays). While doing this, I was checking if a subarray has a single one and if, single one is encountered first time in a subarray, then I am changing it to 0 and making it a vacation.
This approach went fine with 1st, and 4th subtask but gave wrong answer for 2nd and 3rd subtask. No idea why. Can anyone give an example where this would fail.
Following is the code that I used.

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i=0;i<T;i++){
int N = sc.nextInt();
int X = sc.nextInt();
sc.nextLine();
String s = sc.nextLine();
Object result = getVacations(N,X,s);
System.out.println(result);
}
}
public static Object getVacations(int N,int X,String s){
int count = 0;
boolean flag = false;
for(int i=0;i<N;i++){
int temp=0;
for(int j=i;j<i+X && j<N;j++){
if(s.charAt(j)=='0'){
temp++;
}
}
if(temp==X){
count++;
i+=(X-1);
}else if((X-temp)==1 && !flag){
count++;
flag=true;
i+=(X-1);
}
}
return count;
}
}


This problem also has a simple dp solution, where the states are dp[i][0/1], which means amount of max holidays when we change (or not change) the 1 at position i.

Here is my code: https://www.codechef.com/viewsolution/57135979

4 Likes

Someone please provide an edge case. I don’t know where my solution is failing!!!

Ohk thanks

Can anyone tell when this code will fail? Few of my test cases are running well.

#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int x;
cin>>x;
string s;
cin>>s;
int c=0;
int sum=0,maxsum=0,currsum=0;
for(int i=0;i<n;i++){
if(s[i]=='0')
sum++;
else if(s[i]=='1'){

currsum=sum+currsum;
maxsum=max(currsum,maxsum);
currsum=sum;
sum=0;
}
}
if(sum>=0)
{currsum=sum+currsum;
maxsum=max(currsum,maxsum);
currsum=sum;
sum=0;
}
maxsum=maxsum+1;
cout<<maxsum/x<<endl;

}
}



This was a really nice problem
My solution if any one wants to refer
https://www.codechef.com/viewsolution/57197838

#include <bits/stdc++.h>
#define int long long int
using namespace std;

void solve()
{
int n, x;
cin >> n >> x;
string str;
cin >> str;
int left[n];
int right[n];
int zero_count = 0;
int temp_ans = 0;
int final_ans = 0;
for (int i = 0; i < n; ++i)
{
if (str[i] == '1')
{
left[i] = zero_count;
zero_count = 0;
}
else {
zero_count++;
left[i] = -1;
}

}
zero_count = 0;
for (int i = n - 1; i >= 0; --i)
{
if (str[i] == '1')
{
right[i] = zero_count;
zero_count = 0;
}
else {
zero_count++;
right[i] = -1;
}

}
zero_count = 0;
for (int i = 0; i < n; ++i)
{
if (str[i] == '0')
zero_count++;
else
{
temp_ans += (zero_count / x);
zero_count = 0;
}
}
if (str[n - 1] != '1')
temp_ans += (zero_count / x);
// cout << temp_ans << endl;
for (int i = 0; i < n; ++i)
{
if (left[i] == 0)
continue;
else
{
int temp;
temp = temp_ans;
temp -= (left[i] / x);
temp -= (right[i] / x);
temp += (left[i] + right[i] + 1) / x;
final_ans = max(final_ans, temp);
}
}
cout << final_ans << endl;

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tc = 1;
cin >> tc;
while (tc--)
{
solve();
}

}

2 Likes

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";

}


Blockquote
Can any one tell where my code fails ?

#include <bits/stdc++.h>

using namespace std;

void solve(){
int n,x;
string str;
cin >> n >> x;
cin >> str;
vector<int> v,diff;
int pos = 0;
for(auto x: str){
if(x == '1')v.push_back(pos);
pos++;
}
int ans = 0,len = v.size();
if(len != 0){
ans += (v[0]/x);
diff.push_back(v[0] % x);
for(auto it = 0;it < len - 1;++it){
int temp = (abs(v[it] - v[it+1]) - 1)%x;
ans += (abs(v[it] - v[it+1]) - 1)/x;
diff.push_back(temp);
}
ans += (n - v[len-1]-1)/x;
diff.push_back((n - v[len - 1] - 1)%x);
if(diff.size() == 1 && diff[0] == x - 1)ans++;
else{
int l = diff.size();
for(int i = 0;i<l - 1;++i){
if(diff[i] + diff[i + 1] == x - 1){
ans++;
break;
}
}
}
}
else ans = (n/x);
cout << ans << "\n";

}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64_t test;
cin >> test;
while(test--){
solve();
}
}



as yellow_tee said:
try
N= 13
X= 5
0000001001000

import java.util.;
import java.lang.
;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
while(test>0)
{
int n=sc.nextInt();
int x=sc.nextInt();
sc.nextLine();
String s=sc.nextLine();
Stack st=new Stack();
ArrayList list=new ArrayList();
for(int i=0; i<n; i++)
{
if(s.charAt(i)==‘0’)
st.push(‘0’);
else
{
// System.out.println(“BeforeStack”+st);
int count=0;
while(st.size()>0 && st.peek()!=‘1’)
{
count++;
st.pop();
}
// System.out.println(“AfterStack”+st);
if(list.size()==0)
else
{
// System.out.println(“BeforeList”+list+" “+count);
if(st.size()>0)
{
int elem=list.get(list.size()-1)+count+1;
int indx=list.size()-1;
list.set(indx,elem);
st.pop();
}
else
{
list.set(list.size()-1,list.get(list.size()-1)+count);
}
// System.out.println(“AfterList”+list+” "+count);
}
st.push(‘1’);
//System.out.println(list);
}
}
int count=0;
while(st.size()>0 && st.peek()!=1)
{
count++;
st.pop();
}
if(st.size()>0)
{
if(list.size()>0)
list.set(list.size()-1,list.get(list.size()-1)+count+1);
}
else
{
if(list.size()>0)
list.set(list.size()-1,list.get(list.size()-1)+count);
}
// System.out.println(list);
Collections.sort(list);
System.out.println((list.get(list.size()-1))/x);
test–;
}
}
}

can you please tell me on which test case this solution will fail??

import java.util.;
import java.lang.
;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
while(test>0)
{
int n=sc.nextInt();
int x=sc.nextInt();
sc.nextLine();
String s=sc.nextLine();
Stack st=new Stack();
ArrayList list=new ArrayList();
for(int i=0; i<n; i++)
{
if(s.charAt(i)==‘0’)
st.push(‘0’);
else
{
// System.out.println(“BeforeStack”+st);
int count=0;
while(st.size()>0 && st.peek()!=‘1’)
{
count++;
st.pop();
}
// System.out.println(“AfterStack”+st);
if(list.size()==0)
else
{
// System.out.println(“BeforeList”+list+" “+count);
if(st.size()>0)
{
int elem=list.get(list.size()-1)+count+1;
int indx=list.size()-1;
list.set(indx,elem);
st.pop();
}
else
{
list.set(list.size()-1,list.get(list.size()-1)+count);
}
// System.out.println(“AfterList”+list+” "+count);
}
st.push(‘1’);
//System.out.println(list);
}
}
int count=0;
while(st.size()>0 && st.peek()!=1)
{
count++;
st.pop();
}
if(st.size()>0)
{
if(list.size()>0)
list.set(list.size()-1,list.get(list.size()-1)+count+1);
}
else
{
if(list.size()>0)
list.set(list.size()-1,list.get(list.size()-1)+count);
}
// System.out.println(list);
Collections.sort(list);
System.out.println((list.get(list.size()-1))/x);
test–;
}
}
}

can you please tell me on which test case it will give wrong answer

why i am getting WA for this solution:
#include <bits/stdc++.h>
using namespace std;

int main()
{
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++;
}

     }
int br[1000000];
for(int it=0;it<ct;it++)
{

int flag=0;
for(int i=0;i<s.size();)
{
if(s[i]=='0')
{     int j;
for(j=i;j<i+k;j++)
{
if(s[i]=='0')
continue;
else
break;
}
if(j==i+k)
{
flag++;
i=i+k;
}
}
else
{
i++;
}
}
br[it]=flag;

}


sort(br,br+ct);
cout<<br[ct-1]<<endl;

}

return 0;


}

Solved in a bit easy way!

my solution : Solution: 57213008 | CodeChef.
time comp. : O(N).
Hope it helps!