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.
Implementation: CodeChef: Practical coding for everyone
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
thanks bhai!!! 2 ghante tk sochta rha isko mai!!
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
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;
int pos = -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;
if(m<local)
{
m = local;
pos = i;
}
}
bin[pos] = '0';
int ans = 0;
count=0;
// cout<<pos<<"\n";
for(int i = 0;i<n;i++)
{
if(bin[i] == '0')
count++;
else{
//cout<<count<<" \n";
ans += count/x;
count = 0;
}
}
ans+= count/x;
cout<<ans;
}
int32_t main()
{
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
same isssue aarha hai bhai
when the holiday is taken on ithi^{th}ith day, and finally take the maximum of all these numbers.
See this
What is your output for this test case?
1
13 5
0000001001000
Correct Answer = 2
I think yours should be coming 1.
yes
simple as af
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);
You can refer my code if you want
https://www.codechef.com/viewsolution/57197838
(Line 57 to 72)
THanks bhai I misunderstood the question
got the approach but unable to implement it
any suggestion i am getting intutions for the problems but unable to implement it 
Why here we can not use binary search?
Can anyone tell me what is wrong my approach.
bool check(ll assume,string s,ll x){
vector<ll> a(s.size(),0);
for(ll i=0;i<a.size();i++){
a[i]==s[i]=='1' ? 1: 0;
}
ll len=assume*x;
ll sum=0;
for(ll i=0;i<len;i++) sum+=a[i];
if(sum<=1) return true;
for(ll i=len;i<a.size();i++){
sum+=a[i]=='1' ? 1 : 0;
sum-=a[i-len]=='1' ? 1 : 0;
if(sum<=1) return true;
}
return false;
}
int main(){
fio;
ll t;
cin>>t;
while(t--){
ll n,x;
cin>>n>>x;
string s;
cin>>s;
ll l=0,r=s.size()/x;
while(r>l){
ll mid= l + (r-l + 1)/2LL;
if(check(mid,s,x)){
l=mid;
}
else{
r=mid - 1;
}
}
cout<<l nl;
}
}
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' ;
}
In Editor’s solution
for(int i = 0 ; i < n ; i++)
{
if(left[i] == 0 && i > 0)
ans += (left[i-1]/k) ;
}
ans += left[n-1]/k ;
This could be just
why is left[n-1]/k added at last?
could do you please tell me, what does that dp array actually stores ?
#include <iostream>
#include<string>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
string s;
cin>>s;
bool a[n];
int vac = 0;
int bonus = 1;
for(int i = 0;i < n;i++){
a[i] = s[i] - '0';
}
int zeros = 0,ones = 0;
bool flag = false;
for(int i = 0;i < k;i++){
if(a[i] == 0){
zeros++;
}
else{
ones++;
}
}
if(ones == 1){
vac++;
bonus--;
flag = true;
}
else if(ones == 0){
vac++;
flag = true;
}
int i;
if(flag == true){
i = k;
}
else{
i = 1;
}
for(;i + k - 1< n;i++){
int zrs = 0;
int ons = 0;
flag = false;
for(int j = 0;j < k;j++){
if(a[i + j] == 0){
zrs++;
}
else{
ons++;
}
}
if(ons == 0){
vac++;
flag = true;
}
else if(ons == 1 && bonus != 0){
vac++;
bonus--;
flag = true;
}
if(flag == true){
i += k;
i--;
}
}
cout<<vac<<endl;
}
return 0;
}
I am not able to figure out the failing test case! Can anyone help with it?
What have you done? Tell in brief 
Also, on what parameters are you doing the binary search ? Nothing here is sorted 
Can you explain your approach?
I was unable to solve it during contest, only subtask 1 & 4 passed…After debugging with various test cases I got to know about my mistake. Anyways here is my solution in Java…
// Working program with FastReader
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastReader fs = new FastReader();
int t = fs.nextInt();
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
int n = fs.nextInt(), x = fs.nextInt();
char[] arr = fs.nextLine().toCharArray();
int ans = vacationsBeforeFlip(arr, x);
int max = flipOneBitOptimally(arr, x, ans);
sb.append(max).append("\n");
}
System.out.println(sb);
}
private static int vacationsBeforeFlip(char[] arr, int x) {
int ans = 0;
for (int i = 0; i < arr.length; i++) {
int count = 0;
if (arr[i] == '0') {
int j;
for (j = i; j < arr.length; j++) {
if (count == x) {
ans++;
count = 0;
}
if (arr[j] == '1') {
break;
}
count++;
}
if (count == x) {
ans++;
}
i = j;
}
}
return ans;
}
private static int flipOneBitOptimally(char[] arr, int x, int ans) {
int countZeroBefore = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '1') {
int countZeroAfter = 0;
int j;
for (j = i + 1; j < arr.length; j++) {
if (arr[j] == '1') {
break;
}
countZeroAfter++;
}
int leftCount = countZeroBefore / x;
int rightCount = countZeroAfter / x;
int flipCount = (countZeroAfter + countZeroBefore + 1) / x;
if (flipCount > leftCount + rightCount) {
return ans + 1;
}
i = j - 1;
countZeroBefore = countZeroAfter;
} else {
countZeroBefore++;
}
}
return ans;
}
private static int getGcd(int a, int b) {
if (b == 0) return a;
return getGcd(b, a % b);
}
private static long binaryExponentiation(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(
new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int[] readArray(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(next());
return arr;
}
}
}