Problem Statement
PS: Contest has ended!
Thanks in advance!
1 Like
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?
#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 ?
Has anyone heard back from them after the test?