# CCHEAVEN - Editorial

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

Simple

None

# PROBLEM

Given Chef’s life deeds (good or bad) in the form of a binary string of length L where ‘1’ denotes a good deed year and ‘0’ denotes a bad deed year. Chef goes to heaven if he has atleast 50\% years of his life spent on good deeds.

Strange can reduce Chef’s life span to L' years where 1 \leq L' \leq L, if that way, Chef can go to heaven. Strange wants Chef to succeed, so if there is any choice of L' that allows Chef to go to heaven, he will do so.

Determine if Chef can go to heaven.

# QUICK EXPLANATION

• Since there are only L choices for L', we can check each one.
• Checking if some prefix contains atleast 50\% good deeds can be done by maintaining count of good deeds till year L'.

# EXPLANATION

Scrapping the story, we need to determine, if there’s some prefix (including whole string) of length P such that C/P \geq 1/2 => C*2 \geq P where C is the number of good deeds in prefix of length P.

There are only L prefices of given string (including complete string, but excluding empty string), and if any prefix satisfies the condition, Chef can go to heaven.

To check if some prefix of length P is good, all we need is C, the number of good deeds in prefix of length P.

Hence, by checking prefices in increasing order of length, while maintaining C, we can check all prefices in O(L) time.

Following code snippet depicts the intended solution

yes = false
C = 0
P = 0
for i in range(L):
if S[i] == '1': C++
P++
if C*2 >= P:
yes = true


# TIME COMPLEXITY

The time complexity is O(|S|) per test case.

# SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>

# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const int maxl = 1e5; int maxn = 1e6, maxt = 1e5;
const string newln = "\n", space = " ";

int main()
{
int t; cin >> t;
int tot = 0;
while(t--){
int l; cin >> l; tot += l;
string s; cin >> s;
int cnt1 = 0;
string ans = "No";
for(int i = 1; i <= l; i++){
cnt1 += s[i - 1] - '0';
if(2 * cnt1 >= i){
ans = "YeS"; break;
}
}
cout << ans << endl;
}
assert(tot <= maxn);
}

Tester's Solution
import java.util.*;
import java.io.*;
class CCHEAVEN{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int L = ni();
String S = n();
int good = 0, total = 0;
boolean heaven = false;
for(int i = 0; i< L; i++){
if(S.charAt(i) == '1')good++;
total++;
if(good*2 >= total)heaven = true;
}
pn(heaven?"yEs":"nO");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CCHEAVEN().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

Why this Code is showing as Wrong Answer?
However, it is passing the sample test case,.

why can’t i use index(i) for direct division?
If I put the index into a double and then divide it(i+1/2), It passed the solution.
why?

#include <bits/stdc++.h>

using namespace std;

void solve()
{
int l;
cin>>l;

string s;
cin>>s;

int count=0;
int flag=0;

for(int i=0;i<l;i++)
{
if(s[i]=='1')
{
count++;
if(count>=i+1/2)
{
cout<<"yes";
flag=1;
break;
}
}

}
if(flag==0)
{
cout<<"NO";
}
cout<<endl;
}
int main() {
int t;
cin>>t;

while(t--)
{
solve();
}
return 0;
}

If I add these two lines, then it passed the solution.
Whats wrong in:- if(count>=i+1/2)

double z = i + 1;
double curr = z / 2;

suppose a case where n=5 & s = 00011 for this your code gives yes where as answer is no because 50% of 5 = 2.5, where as (i+1/2) without double will give 2 as i is an integer type variable so upon division it will automatically round off 2.5 to 2, so upon converting to double it will give 2.5 and it will give correct answer which is no.

3
001
5
00011

But these both test cases is giving answer as NO with my code while custom input test case.
Is there any problem with custom input test case?

try
2
3
001
5
00011

Still It gives NO for both input

Change if(count>=i+1/2) to if(count>=(i+1)/2)

1 Like

Got it Man .
Thank You

I wonder why this code gives me a wrong answer. Works fine with the test cases given.

from sys import stdin

def check(string,L):

counts = {i: string.count(i) for i in set(['0','1'])}
count = counts['1']

if count /L >= 0.5:

print('YES')
elif L==1 and count==0:
print('NO')
else:
check(string[:L-1],L-1)


try:

while testcases!= 0:
check(string,L)


except:
pass

I am not sure abt python that much but can you explain in this line what r u doing?

Here was my approach to this, Simply return “YES” if no of 1’s are greater than number of 0’s at any point. ( This will cover the 50% constraint as well, since we have only 0’s and 1’s in the string.

0’s + 1’s = length of string
if 1’s > 0’s : One’s should be 50% greater

#include <iostream>

using namespace std;

void Solve() {
int l;
cin>>l;

string s;
cin>>s;
int z=0, o=0;

for(int i=0; i<l; i++) {
if(s[i]=='0') z++;
else o++;

if(o>=z) break;
}

if(o>=z) cout<<"Yes"<<endl;
else cout<<"No"<<endl;

}

int main() {

int T;
cin>>T;

while(T--) {
Solve();
}

return 0;
}

1 Like

Sure. The function will run on the entire string first. In case, the % condition is met, it will print Yes, else it will run on the string length one less than the previous.(L-1) For instance, first it evaluates on 110010010. Since the condition is unmet, it will run on 11001001.

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

int main(){
int t;
cin >> t;
while(t–){
int l;
cin >> l;

    string s;
cin >> s;

int cnt1 = 0;

bool flag = false;
for(int i=0;i<l;i++){
if(s[i]=='1')
cnt1++;

if(2*cnt1>=(i+1)){
flag = true;
break;
}
}

if(flag)
cout << "YES\n";
else
cout << "NO\n";

}


}

/* package codechef; // don’t place package name! */

import java.util.Scanner;
import java.lang.;
import java.io.
;

/* 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
{

	Scanner sc =new Scanner(System.in);

int t=sc.nextInt();
for(int k=0;k<t;k++) {

int l =sc.nextInt();
sc.nextLine();
String s= sc.nextLine();
int count0=0;
int count1=0;

for(int i=0;i<l;i++) {

if(s.charAt(i)=='1') {
count1++;

if((double)count1 /(count0 + count1)*100 >=50) {
System.out.println("YES");
break;
}
else {
System.out.println("NO");
break;
}
}
else if(s.charAt(i)=='0') {
count0++;
}

}

}
}


}

what wrong with this code
it gives correct answer with custom input

Even I used the same approach. It’s very simple and there is no need for further complexities.
Just check if at any point deeds are greater than or equal to sins

#include <iostream>
#include <string>

#define cin std::cin
#define cout std::cout
#define endl std::endl

void solve(){
int l;
cin>>l;
std::string s;
cin>>s;
int deeds = 0, sins=0;
for(auto x:s){
if(x=='1')
deeds++;
else
sins++;
if(deeds>=sins){
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
}

int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}