Sharechat Hackerearth Intern

I used digit dp + binary search

digit dp -> find number of lucky numbers till x

then we need to find k + count(l-1)

just run binary search over it.

Thanks man, appreciated

How much did you score ? i followed the same approach and score 21 only … rest were WA. And what can be expected cutoff according to you ?

I cannot say about expected cutoff. I got full score.

1 Like

last time I got 164/170. this time 20/170. sad rxn.

If anybody receive any mail regarding results, please let us know here .

Do we have to find Kth lucky number, or if Kth number is lucky or not??

Kth lucky number

Can you please explain your DP. I’m able to find for powers of 2 using bits but not able to generalise it. Thanks in advance.

#define int long long
vector<short> num;
int dp[65][2][8][2];

int solve(short pos = 0, bool f = 0, short mask = 0, bool valid = false){
    if(pos == num.size())return valid;
    int &res = dp[pos][f][mask][valid];
    if(~res)return res;
    short lst = 1;
    if( !f) lst = num[pos];
    res = 0;
    for(short i = 0; i <= lst; ++i){
       short newMask = 0;
       if(mask&1)newMask+=2;
       if(mask >> 1 & 1)newMask+=4;
       if(i)newMask++;
       res+=solve(pos+1, f || (i < lst), newMask, valid || (newMask == 5));
    }
   return res;
}

int cnt(int k){
   num.clear();
   while(k)num.emplace_back(k%2),k/=2;
   memset(dp,-1,sizeof(dp));
   return solve();
}

signed main(){
  int t;
  cin >> t;
  while(t--){
      int l,r,k;
      cin >> l >> r >> k;
      if(l) k += cnt(l-1);
      int lo = l, hi = r, ans = -1;
      while(lo <= hi){
           int mi = lo + hi >> 1;
           if(cnt(mi) >= k)ans = mi, hi = mi - 1;
          else lo = mi + 1;
      }
      cout << ans << "\n";
 }
  return 0;
}
2 Likes

Did u got the mail after test?

Really cool. Thanks!

No :sweat_smile:

Anybody who scored well in this test got the call till now? I mean I scored 95 in this test and I am sure that I would not be called but if anybody got the call for this, please reply!

you got the interview call from last time?

Yeah, I know you scored full in that too (that’s not something new XD). If they are not hiring you, whom for they are looking gennady or Petr? hahaha

2 Likes

I agree to your point that he is awesome, but when it comes to hiring maybe after some point in competitive, it may not matter. I am saying this just as a discussion topic and not as a comment on any individual that maybe there are better candidate who show enough problem solving but are better developers.

1 Like

You all guys are awesome :slight_smile:

But they have not selected anybody . They just took the test and interviews and then gone silent until and unless I had to call up the HR to get things clear . I hope this time they do not repeat this unprofessional behavior. (Sad to realize that I will not even clear coding test this time)

Bro what did they ask in interview?