[Community Puzzle] Bit count to limit

Puzzles
#1

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.

#2

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.

5 Likes
#3

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
#4

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
#5

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

#6

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

1 Like
#7

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 ???

#8

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.

#9

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?

#10

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.

#11

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.

#12

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.

#13

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(

#14

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.

#15

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.

#16

@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
#17

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.

#18

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

#19

Iā€™ll edit. Edited.

This message will self-destruct tomorrow.

#20

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