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
b = 0
index = 0
t = int(input())
for i in range(1,t+1):
n,w = input().split()
n = int(n)
w = int(w)
a = list(map(int, input().split()))
a.sort(reverse=True)
print(a)
for indexs in a:
index += 1
b += indexs
if b > w:
print(n-index)
break
if indexs == a[-1] and b <= w :
print(â0â)
break
b = 0
indexs = 0
index = 0
Hey can you please provide your code along with proper indentation, as it is pretty confusing what a python code is exactly intended to do without indentation
As a general hint though, you can preserve formatting by adding a line that starts with three back ticks ``` before and after your code.
As a specific observation, you donât need the audioop library for any problem on this site that I know of. The sort/sorted built-ins take reverse as a parameter anyway.
