Submission link ( http://codeforces.com/contest/914/submission/34580268 )
I used simple dfs but getting a WA.
I just want to know why this approach is wrong.
Problem Link (http://codeforces.com/contest/914/problem/C )
I think u didn’t read the question properly.
It’s saying that count those number such that it takes exactly k operation to reduce to 1.
Like:
11111
2
for this you can have 3 or 011 as 011->2 and 2 in binary is 10->1
similarly for 5 (101)->10->1
similarly for 15(1111)->100->1
In all these cases we perform operation k times(2 times)
actually in the code dfs() i am trying to do the same thing, to identify numbers having k set bits but not greater than n . Lets say if binary length of n is 8 then it will try to calculate all the numbers less or equal to n and having bit length less or equal to 8 (having k set bits). The variable CHAIN_LENGTH in dfs() will keep track of number of set bits doesn’t exceed k, if it does then the recurrence will simply return. As i am adding pow(2, k) each time this will make a single bit set to one at a time. please look at my submission once.
I saw ur code.Try printing ur num value in binary ,u’ll get to Know.
And again u didnt get the point,we dount have to count numbers less than n which have k set bits.
Read my explaination again.
(Run your code for the test u were getting wrong and Print the num in binary form and see if u get any num = 1111 (you wont) )