SLPCYCLE - Editorial

editorial
, , , ,
4

guys please say where i have mistaken
t=int(input())

for _ in range(t):

h,l=[int(a) for a in input().split()]

re=int(l)

s=input()

z=0

for i in s:

    if i=="0":

        z=z+1

    else:

        if z!=0:

            if (re-z)!=0:

                re=2*(re-z)

            else:

                re=re-z

            z=0

            if re==0:

                break

if z!=0:

    if (re-z)!=0:

        re=2*(re-z)

    else:

        re=re-z

    z=0

if re==0:

    print("YES")

else:

    print("NO")
5

How will the output be “YES”. He 1st sleeps 1 unit so he has to sleep another 2*(5-1)=8 units but the remaining zeros are 5.

6

Can anybody please help me find which case is missing. Please! :pray:

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

int main()
{
int t;
cin>>t;
while(t–)
{
int l,h;
cin>>l>>h;
string s;
cin>>s;

          map<int,int> mp;
          
          //storing what all contiguous unit of time is available
          for(int i=0;i<l;i++)
          {
                 int c=0;
                 while(i<l && s[i]=='0')
                 {
                        c++; i++;
                 }
                 if(c!=0) 
                 mp[c]++;
          }
          
        
          bool ans=false;
          while(mp.empty()==false)
          {
             
                 auto it=mp.lower_bound(h);
                 if(it==mp.end())
                 it--;
                        
                 h=2*(h-((*it).first));
                 ((*it).second)--;
                        
                 if(((*it).second)==0)
                 mp.erase((*it).first);
                 
                 if(h<=0)
                 {
                        ans=true;
                        break;
                 }
   
          }
         
         if(ans==true) cout<<"Yes\n";
          else cout<<"No\n";
   }
   return 0;

}

7

check with edge cases
https://www.codechef.com/viewsolution/48288067

8

didn’t consider the fact that he may have the option of not sleeping during free time. UGHH. But it wasn’t mentioned clearly ;-;

9 Likes
9

But what happens when he does not sleeps 1 unit and work for 1 unit and sleep afterward?
Think You will get your answer.

1 Like
10

You are computing H = 2 ( H - X ) every time x is less than H. That will give you a wrong answer. What you should do is :
if 2(H-X) < H
H = H-X

1 Like
11

what is wrong with my code?suggest some corner cases.

 #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define mod 1000000007


    void solve()
    {
        ll L,H;
        cin>>L>>H;
        string s;
        cin>>s;
        int flag=0;
        ll count=0;
        
        ll i=0;
        for( i=0;i<L;i++)
        {
            if(s[i]=='1')
            {
                if(flag==1)
                {
                    H=2*(H-count);
                   // if(H==0)
                   // break;
                   flag=0;
                }
                count=0;
            }
            if(s[i]=='0' )
            {
                count++;
                flag=1;
            }
        
        }
        if(i==L && s[L-1]=='0')
        {
            H=H-count;
        }
       
        if(H>0)
        cout<<"NO"<<endl;
        else if(H<=0)
        cout<<"YES"<<endl;
    }





    int main()
    {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

        ll T;
        cin>>T;
        while(T--)
        {
            solve();
        }
    }
12

I think quite differently -

1.push all the length of continuous zeroes in a vector (denotes that how much my user can sleep continuously)
2.Now if there are no zero answers is NO
3. else, let prev = h denotes we need this hrs to sleep, now iterate my vector, if my current value (which is basically the length of continuous zeroes ) is less than prev, then I will change my previous to prev = 2 * (prev-vc[i]); (as question said)

Also, one thing is to check sometimes while doing this (prev = 2 * (prev-vc[i]); ) , my prev is greater than h , so now we will set prev to h because from now we will check from that time frame no need to take previously.

otherwise(if vc[i]>prev) will set flag=1 means we get enough continuous hrs to sleep.

in last what I add is to check max continuous zeroes, we r checking here from starting and doing all the operations above may increase my prev, so I directly check whether the max continuous zeroes are greater than equal to h or not, if yes then I will simply sleep in that time frame only.

    lli n,h;
    cin>>n>>h;
    string s;
    cin>>s;
    lli cnt=0;
    vi vc;
    loop(i,n)
    {
        if(s[i]=='0')
            cnt++;
        else
        {
            if(cnt)
                vc.pb(cnt);
            cnt=0;
        }
    }
    if(cnt)
      vc.pb(cnt);
    if(sz(vc)==0)
    {
        print("NO");
    }
    else
    {
        lli prev = h;
        lli flag=0;
        loop(i,sz(vc))
        {
            if(vc[i]<prev)
            {
                prev = 2*(prev-vc[i]);
                if(prev>h)
                    prev = h;
            }
            else
                flag=1;
        }
        if(flag==1 or h<=(*max_element(all(vc))))
            print("YES");
        else
            print("NO");
    }
    
}
return 0;
}

solution : CodeChef: Practical coding for everyone

1 Like
13

Same with me too… :no_mouth:

14

Can anyone point out error in my code. I’m unable to understand where is my code failing?

#include
#define ll long long
using namespace std;

int main() {
// your code goes here
ll t,h,l;
cin>>t;
while(t–){
cin>>l>>h;
string s;
cin>>s;
ll count=0,flag=0;
if(h==0){
cout<<“YES”<<endl;
continue;}
for(ll i=0;i<l;i++){
if(s[i]==‘0’)
count++;
else{
if(h<=count){
flag=1;
break;}
if(count){
h=2*(h-count);}
count=0;
}}
if(h<=count || flag==1)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
return 0;
}

15

can someone give a test case which my code might fail to pass because I am still trying but cannot find a test case on which I can improve my code? Any help will be recommended thanks:

My WA code link : CodeChef: Practical coding for everyone

PS: Ignore bad variable names, sorry for that

16

how will it be YES?

17 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
// ios_base :: sync_with_stdio(false);
// cin.tie(NULL);

//////////////////////// Sleep Cycle ///////////////////
void solve() {
   int l , h;
   string s;
   cin >> l >> h;
   cin >> s;
   int req = h;
   int count = 0;
   for(ll i = 0 ; i < s.length() ;) {
       if(s[i] == '0') {
           while((s[i] == '0') && (i < s.length())) {
               count ++;
               i++;
           }
           if(count >= req) {
               cout << "YES" << endl;
               return;
           } else {
               req = 2 * (req-count);
               count = 0;
           }
       } else {
           i++;
       }
     
   }
   cout << "NO" << endl;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    while(tc--) {
        solve();
    }
}

Can anyone tell me what is wrong here ? I passed the sample cases but got WA after submitting.

18

include

using namespace std;
int n,h;
int t;
int a=0;

int main()
{
cin>>t;
while(t–){
cin>>n>>h;
char str[n] ;
cin>>str;
int count=0;
for(int i=0;i<n;i++){
// if(str[i]==‘0’){
// int j=i;
count=0;
while(str[i]==‘0’ && i<n){
count++;
if(count==h){
a=1;
break;
}
i++;

       }
       if(count!=0){
       h=2*(h-count);

   }

}
if(a==0){
cout<<“NO”<<endl;
}
else{
cout<<“YES”<<endl;
}

}

return 0;

}
where am I wrong??

19

https://www.codechef.com/viewsolution/48269643

please can you tell what’s wrong with my code?

20

Now that I realized my mistake, or rather lack of observation: 2(H-x) < H, I feel stupid.

1 Like
21

can someone point out what’s wrong with my code. logic seems to be right but no clue why it fails. not sure if there are any tricky corner case.

https://www.codechef.com/viewsolution/48307279

22

Did you add the condition to update H only if the following condition holds true: 2(H-x) < H?

Here’s an example:
Suppose H=5, and at some point x=2,
then it would not be prudent to update H with 2(H-x) because the new value of H will then become

H = 2 * (5 - 2) = 6 which is actually greater than the previous value of SLEEP REQUIRED. In that case, it would be best it we didn’t update the existing value of H. Hope this solves your issue.

1 Like
25

https://www.codechef.com/viewsolution/48293694

For which test cases is this code failing??