Help in Nashdaq hiring problem

Problem Statement

PS: Contest has ended!
Thanks in advance!

1 Like

Same problem on codeforces - Problem

2 Likes

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 ?