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.
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.
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;
}
Did u got the mail after test?
Really cool. Thanks!
No
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
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.
You all guys are awesome
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?