PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
