Problem Statement

PS: Contest has ended!

Thanks in advance!

Ahhh . . . I have an AC for this problem!

1 Like

I stored sorted indices of 0s and 1s separately and just alternated between the two sets. Also used upper bound to find next greater index. And bang got an AC. But I guess there are more optimized solutions to this.

How to confirm that our test is submitted on hackerearth?Yesterday I clicked on end test and it asked for feedback.But then there was no any sign that I have submitted!

use two variables. one for count of subsequences ending at 0 (e0), and one for all ending at 1. Any time you find 0, increment e0 and same when you find 1. O(N) complexity

I got it partially correct(30 pts)

Can you paste your code here please.

Just simulate the process

void solve(){

string s;

cin >> s;

int one =0 ,zero=0 ;

for(char x:s){

if(x==‘0’){

if(one)one–;

zero++;

}else{

if(zero)zero–;

one++;

}

}

return one+zero;

}

2 Likes

n = Integer.parseInt(br.readLine());

String input = br.readLine();

Stack A = new Stack<>();

Stack B = new Stack<>();

int count = 0;

```
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '0') {
if (A.isEmpty()) {
A.push(++count);
}
B.push(A.pop());
}
if (input.charAt(i) == '1') {
if (B.isEmpty()) {
B.push(++count);
}
A.push(B.pop());
}
}
System.out.println(count);
```

python solution

```
t = int(input())
for _ in range(t):
n = int(input())
s = input()
one,zero = 0,0
for i in s:
if(i=='0'):
if(one): one-=1
zero+=1
else:
if(zero): zero-=1
one+=1
print(one+zero)
```

It was mentioned in the hackerearth page that only people with >90% score will be shortlisted and even that will not guarantee them interview. That means, you can afford to loose 24 marks at max out of 236 to atleast have a chance for an interview.

1 Like

can you share your code?I was having problem with this method

where?

HE doesn’t allow seeing submissions made in such hiring contests and I don’t have it locally.

e0 = number of subsequences ending at 0

e1 = number of subsequences ending at 1

e0 = e1 = 0

if current character is ‘0’ then we can either append it to one of the subsequences ending at 1, so (e0 ++, e1–), except if e1 is 0 then we will have to start a new subsequence of ending at 0 (e0++).

Its the same logic for encountering ‘1’.

answer will be max(e0+e1,ans) over the string.

EDIT: nvm, can see the submission

```
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define eb emplace_back
using ll = long long;
const int inf = 1e9+5;
const ll INF = 1e18+5;
const int nax = 2e5+500;
// inline ll hhme(ll a, ll b){
// return 300005LL * a + b;
// }
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
// int operator()(int x) const { return x ^ RANDOM; }
// };
//gp_hash_table<ll, ll, chash> mpp;
int main() {
//freopen("g:/coding/cpp/input.txt","r",stdin);
//freopen("g:/coding/cpp/output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
string s;
cin >> s;
assert((int)s.length() == n);
int e0 = 0, e1 = 0;
vector<bool> done(n+10);
int mx = 0;
for(int i=0;i<n;i++) {
if(s[i] == '0') {
if(e1 > 0) {
e1--;
e0++;
} else {
e0++;
}
} else {
if(e0 > 0) {
e0--;
e1++;
} else {
e1++;
}
}
mx = max(mx, e0 + e1);
debug()<<imie(e0) imie(e1);
}
cout << mx <<"\n";
}
}
```

Sorry, the code isn’t available now on Hackerearth.

Can you explain your approach a bit ?