MAXVAC Problem Common Mistakes

help
1

A lot of WA were there in this problem , so I thought of writing down the common mistakes done while solving it. Also in the contest the accuracy for this problem was around 5% .

In this problem, you are given a binary string .
’1’ means that particular day is a working day
’0’ means that particular day is a holiday .

The person need X continuous holidays to go to a vacation . You can take only one leave i.e at any position flip ‘1’ to ‘0’ .
And then you have to find the maximum number of vacations the person can go to.

The common mistakes that were done are :-
1 . Only considering the '0’s in the segment where the ‘1’ is flipped and not the other contiguous '0’s
2 . Selecting the longest subarray having atmost one ‘1’ and flipping that ‘1’ and simply dividing the number of zeros in that segment by X plus the other segments of '0’s that are present.

The first mistake is quite obvious why its incorrect. Its simply because you are not counting all the holidays that could have been counted in a vacation.

Now , the second mistake is quite common because it seems selecting the longest subarray having atmost one ‘1’ will be optimal but its not always the case .

This comment by @yellow_tee explains this very well.

Lets consider the following input=

N= 13
X= 5
0000001001000

now if we find longest subarray with only single 1 in it, it would be from index 0 to index 8, ie: “000000100”. let’s flip the 1 according to your solution. Therefore we get 0000000001000 as X =5 only one vacation can be taken in this case.

But the solution is as follows- flip the second one so we get:
“0000001000000”, in this we see that 2 vacations can be taken.

The goal should be to flip the 1 such thats the merged interval has an extra segment of X 0s, this might not be true for the longest contiguous segment of 0s.

And so, the correct approach is that you have to go to every position which is a working day i.e ‘1’ and have to flip it and check whether it increases the total vacations or not.
Your final answer is just the maximum vacation that you got in this process.

2

#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t=0;
cin >> t;
while(t–)
{
//no of days and holiday can be taken
long int n,x;cin>>n>>x;
string s;
cin>>s;
long int count1=0;
long int l=0;
long int w=0;
for(long int f=0;f<n;f++)
{
long int count=0;
w=s.find(‘1’,w);
s[w]=‘0’;

		for(long int i=0;i<n;i++)
		{
			if(s[i]=='0')
			{
				l++;
				if(l==x)
				{
					l=0;
					count++;
				}
			}
			else
			{
				l=0;
			}
		}
		s[w]='1';
		
		if(count1<count)
		{
			count1=count;
		}
		
		if(w==-1)
		{
			break;
		}
		w++;
	}

	cout<<count1<<endl;
}

return 0;
}
what is wrong i it?

Problem Code: MAXVAC

3

thanks, I was doing that 2nd mistake

4

can you tell me what is wrong in my code?

5

Tell in short what have u done

6

first used while loop for testcases
in problem
finded index (let w) of string coming first ‘1’
at this index i change the value from ‘1’ to ‘0’
then counted all vacation
if it is greater than previous than store it else leave it
then index ‘w’ change the value from ‘0’ to ‘1’
increase the value of w by 1

run the problem soln again again till w=-1
it only comes when there is no 1 left later to flip in string and count

7

Can you tell where do I go wrong? First I find the ans when if chef didnt take any holidays (The final answer will then be either this value or one more than this value). I also 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 satisfy, I increment the ans found initially otherwise I leave the ans as it is.

The code (If you want to look at the implementation, I have covered corner cases x=0).

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

First of all in your submission CodeChef: Practical coding for everyone , you are getting RTE because you have done this

if(w==-1)
			{
				break;
			}

after

	s[w]='0';

Hence if w =-1 in line 20, you are doing s[-1] =‘0’ in line 21. Hence RTE .
If you fix this you will get a WA .CodeChef: Practical coding for everyone
This is because of this :-

	else
				{
					l=0;
				}

You are setting l =0 only if s[i]==1. What if the string ended with ‘0’ ? Something like 00100100
When w = 5 , in your second iteration, your l will be already 2 because of the last 2 trailing zeores.
Hence you have to add this condition.

	if(s[n-1]!='1')
			l=0;

Even after you do these correction , you will get a TLE
CodeChef: Practical coding for everyone

Because this is a O(n^2) approach. You are iterating for every ‘1’ and then finding the zeores/vacations in the entire string for every ‘1’ position. You have to precompute so that you find the number of vacations for every ‘1’ in O(1)

9

thanks for the relpy . (’_’)