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.
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’;
}
}
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–!=0){
int n=sc.nextInt();
int x=sc.nextInt();
String s=sc.next();
int zero=0;
int ans=0;
int one=1;
for(int i=0;i<n;i++){
if(zero==x){
ans++;
zero=0;
}
char ch=s.charAt(i);
if(ch-‘0’==0){
zero++;
So, the dp stores two states: prefix and exact count of flips (which could be 0/1 acc to problem). Now, the transition is, (after i >= x, because when i < x, I can’t go on holiday)
If we have 0 at current index i, then we can’t do any flips here, so either we can have flips earlier in range i - x or we can’t.
If we have 1 at i, then we can flip it, and add the result of i - x to it, and if we’ll not flip it, then result is same as dp[i-1].
Can anyone tell me a test case where this code fails??
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Main
{
public static void solve(String s,int n,int k){
int arr[] = new int[n];
int ext[] = new int[n];
int i=n-1;
int ans=0;
int count=0;
while(i>=0){
if(s.charAt(i)=='0'){
count++;
if(count==k){
ans=ans+1;
arr[i]=ans;
count=0;
}else{
arr[i]=ans;
}
}else{
count=0;
arr[i]=ans;
}
ext[i]=count;
i--;
}
count=0;
i=0;
while(i<n){
if(s.charAt(i)=='0'){
count++;
if(count==k){
count=0;
}
}else{
int t=count+1;
if(t==k){
System.out.println(arr[0]+1);
return;
}
if((i+1) < n && s.charAt(i+1)=='0'){
t+=ext[i+1];
if(t==k){
System.out.println(arr[0]+1);
return;
}
}
count=0;
}
i++;
}
System.out.println(arr[0]);
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc= new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int k=sc.nextInt();
String s=sc.next();
solve(s,n,k);
}
}
}
This can be solved using a simple greedy approach
Count all gaps of ones and zeroes amd store them in a vector
Then iterate over all gaps of ones and check check whether including extra zero in adjacent zeroes gap can increase number of vacations or not .
In case if there is only one 1 between 2 gaps of zeroes merge them and check the same
Good Afternoon sir,
My name is Kunal jain,I am new to coding,I tried to do this maxvac question.
I also didi the code but it is not submitting,it is showing that my two test cases are failing ,So can you please help me to find out my which test cases are failing?
link to my code is this- https://www.codechef.com/viewsolution/57981526