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.
1 Like
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)
1 Like
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;
}
}
}
I found all the 1’s in the string and one by one flipped them to zero and found no. of holidays possible. And printed the maximum of those. My solution exceeded the time limit. I guess it is beacuse I am using multiple loops for entire string length. It was a very naive approach. Thanks for discussing other approaches here!!
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n,holi;
cin>>n>>holi;
string str;
cin>>str;
int m=0;
for(int i=0;i<str.length();i++)
{
if(str[i]=='1')
{
int count=0;
str[i]='0';
int j=0;
for(int k=0;k<str.length();k++)
{
if(str[k]=='1')
j=0;
else
{
j++;
if(j==holi)
{
count++;
j=0;
}
}
}
m=max(m,count);
str[i]='1';
}
}
cout<<m<<"\n";
}
return 0;
}
@lavish315 ,
I have a solution which takes O(1) auxiliary space -
long n, x;
cin >> n >> x;
string s;
cin >> s;
long ans(0), cnt(0), prev(0);
bool usable(false), is_one(false);
for(long i=0; i<n; i++) {
if(s[i]=='0') {
cnt++;
} else {
ans += cnt/x;
is_one = true;
if(((prev%x + 1 + cnt%x >= x) || cnt%x+1 == x) && !usable) usable = true;
bool is_single_one = (i+1==n || s[i+1]=='0');
prev = is_single_one ? cnt : 0;
cnt = 0;
}
}
ans+=cnt/x;
if(is_one && ((prev%x + 1 + cnt%x >= x) || cnt%x+1 == x) && !usable) usable = true;
if(usable) ans++;
cout << ans;
We only need the length of prev block of 0s to figure if you can flip the one.
Hi Ashutosh,
I have also calculated countZerosBeforeOne & countZerosAfterOne , and then checking whether I’ll get extra vacation if I flip that bit, if “Yes” then I’m keeping it else moving. Also updating “countZerosBeforeOne = countZerosAfterOne”, but only 1st and 4th task is getting passed and not the 2nd and 3rd one.
I also want to know the test case for which it fails. If you have solved it correctly then do let me know. Although I can check other’s solution but I have really put everything in it and want to know where I’m doing wrong.
can anyone say what is wrong my my code please?
#include<bits/stdc++.h>
#define int long long
#define vi vector
#define mod 1000000007
#define ii pair<int,int>
#define vii vector
#define pb push_back
#define ff first
#define ss second
#define fill(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F0R(i,n) for (int i=0; i<(n); i++)
#define all(n) n.begin(),n.end()
#define allr(n) n.rbegin(),n.rend()
#define INF 1e18
using namespace std;
int32_t main(){
IOS;
int t;cin>>t;
while(t–){
int n,x;cin>>n>>x;
string s;cin>>s;
int ar[n];
int cnt=0;
for(int i=0;i<x;i++){
if(s[i]==‘1’)++cnt;
}
int l=0;
ar[l]=cnt;
for(int r=x;r<n;r++){
if(s[l]==‘1’)–cnt;
if(s[r]==‘1’)++cnt;
++l;
ar[l]=cnt;
}
int ans=0;
bool used = false;
int i=0;
while(i < n-x+1){
if(ar[i]==0){
++ans;
i += x;
}
else if(ar[i]==1 && !used){
++ans;
i += x;
used = true;
}
else{
++i;
}
}
cout<<ans<<’\n’;
}
}