Sharechat Hackerearth Intern

help
23

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.

24

Thanks man, appreciated

25

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 ?

26

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

1 Like
27

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

28

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

29

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

30

Kth lucky number

31

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.

32 
#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
33

Did u got the mail after test?

34

Really cool. Thanks!

35

No :sweat_smile:

36

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!

37

you got the interview call from last time?

39

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
40

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
41

You all guys are awesome :slight_smile:

42

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)

43

Bro what did they ask in interview?