[Community Puzzle] Bit count to limit

https://www.codingame.com/training/medium/bit-count-to-limit

Send your feedback or ask for help here!

Created by @DPAmar,validated by @tutubalin,@CyberLemonade and @cg123.
If you have any issues, feel free to ping them.

My stupid bruteforce solution passes all testcases but fails on the last submit validator. I’m outraged :rage:.

On a more serious note: the validators should not be harder than their corresponding testcases.

2 Likes

It’s not. As I stated in the problem comments : a damn fast O(n) implementation may solves all the test cases, including validators. But it’s not the goal, obviously : there is a O(ln(n)) one :slight_smile:
N from last validator is as complex as the corresponding TC (id est : it is encoded over the same number of bits)

1 Like

I’m aware of the existence of a faster solution than O(n). I just thought I’ll give it a shot with O(n) anyways to see if I can pass. And I did so on the visible testcases (I can share my code via private message if you want). On submit however I had an unpleasant surprise.

I’m not complaining about not passing with my slow approach. In fact this code should not pass IMO. I’m suggesting to increase the input for the visible testcase to make it bigger than the corresponding validator.

The N of the validator is larger, making it harder for a bruteforce solution. For my code the 1s timelimit given my CodinGame is somewhere between the testcase and validator.

1 Like

As I said, goal was to find a log(N) version. I this configuration, there is no difference between last TC and validator (same complexity)

I tried to find some brute force code that would pass last TC but failed. I posted a brute force C solution that is indeed able to go through last TC in about 2 seconds (interested in a faster solution BTW :slight_smile:) But this is anyway too long for CG

If that is the goal, please make it apparent and tested in the visible set.

1 Like

Don’t get your point.

Aynway. It appears that the same bruteforce implementation

  • fails last TC nor validator in C
  • passes last TC but not last validator in C#
  • passes both last TC and last validator in JS

Yes, the goal actually is to find a smart implementation. Hence, the TC title “Did you get the trick ?”.
And yes, this has been tested. Again, using C. How am I supposed to guess the counter-intuitive fact that JS would have been faster ???

The point is it’s bad practice to have validators be strictly harder than tests. It’s a simple guideline, and it avoids that class of failure.

What does harder mean, then?
Considering logarithmic complexity, a 28-bit-long integer is no more complex than any other 28-bit-long integer, is it?

I haven’t solved it so I theoretically don’t know what it’s about, but obviously @eulerscheZahl found a “natural” counterexample. On an O(N) solution, any N can be presumed “harder” than a lower N. Which seems to be the case for this puzzle, considering his suggestion.

So it seems: just increasing n in the ide test and decreasing it in the validator would make everyone happy… :wink:

By the way, nice puzzle, congrats, very much liked it: very simple to understand, very simple to code, yet it still needed some brainwork (for the O(log n) I mean…). I recommend to put it under ‘easy’ instead of ‘medium’, this is a <5 min puzzle. But it’s up to you.

Ok, I’ve tried it.

And solved it much quicker than expected because my O(N) algorithm passed both tests and validators on first try.

So very easy indeed, a straightforward statement implementation does it.

I don’t know if any of the 20+ languages supported on CG has problem with 64 bit integers. If not, then brute force could be ruled out with a e.g. 58-bit test case (or whatever is the max so that also the result is below <64 bits(

I don’t think that there should be such game-breaking changes after the approval of a puzzle. That’s what the review phase is good for. Javascript only has doubles, no integers.

I don’t understand how can your ‘stupid brute force’ be O(n) complexity. If you check and add-up 1-digit counts for all numbers 1 to n, for each individual number you still need to add the 1s - that is O(log(n)). So in total ‘stupid brute force’ is O(n*log(n)) and not O(n). Otherwise it is already not that ‘stupid’ :slight_smile:

But I understand that in a practical, 64bit limit range, O(n) and O(n * log n) is essentially the same, although mathematically different.

@TBali You’re right of course (we could even say the complexity is ∑ log i = log n! = O(n log n)).

That said, the number of ones can also be counted in O(result) as follows:

def ones(n):
    cnt1 = 0
    while n:
        cnt1 += 1
        n &= n-1
    return cnt1

My language (and CPU) have a constant-time bit-count operation. So I’m constant-time per number (within 64 bits), and constant-time per addition. Θ(N), as long as lgN<64.

Indeed. My solution would degrade to Θ(N×lgN) if I allowed it to exceed 64-bit inputs.

@JBM Well, if you consider log N as a constant, then N is also a constant and it falls down to O(1).

I’ll edit. Edited.

This message will self-destruct tomorrow.

And still there is an O(n) solution:

def count(val, ones):
    if val > limit: return
    solution += ones
    count(2*val, ones)
    count(2*val+1, ones+1)

count(1, 1)
2 Likes