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' ;
}
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;
}
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.
