PNG File Reader

[Duthomhas]

Yes, that is very ambiguous wording. I read it as N=5,K=2 would validly produce 00100, but you read it as not. Neither of us are wrong.

[geeloso]

With respect to the Binomial Coefficient u referenced earlier, r u referring to that similar to what u have in a Pascal triangle to determine the coefficients of an n-degree polynomial expansion? If yes, how does that apply here

[Duthomhas]

geeloso wrote:

r u referring to that similar to what u have in a Pascal triangle to determine the coefficients of an n-degree polynomial expansion?

Yes. Exactly.

how does that apply here

Do as jonnin suggested — write out the examples as, for example, given N=7, K=2:

  1 1 1 1 1 1 1
            0 0

rewritten as:

  1 1 1 1 1 k

The number of possibilities are 6 choose 1 ⟶ 6. We can verify this ourselves: 11111(00), 1111(00)1, 111(00)11, 11(00)111, 1(00)1111, (00)11111.

That’s 6, not 7, because each K digits are treated as if they were a single digit.

Next, we have:

  1 1 1 1 1 1 1
        0 0 0 0

rewritten as:

  1 1 1 k k

The number of possibilites are 5 choose 2 ⟶ 10. Again we can verify: 111kk, 11k1k, 11kk1, 1k11k, 1k1k1, 1kk11, k111k, k11k1, k1k11, kk111.

Continuing we get 4, and then we run out of space for another K.

Totaling we get 1 + 6 + 10 + 4 ⟶ 21 possibilities.


Learning to recognize these mathematical patterns is most of the battle.

Hope this helps.

[geeloso]

This looks crazy goooood! Thx a lot Duthomas for ur painstaking, insightful illustrations; it's much clearer to me now. I'd try to apply this and see what comes of it.

[Duthomhas]

When you have your solution, make sure to consider weird inputs.
For example, what if (N K) are:

    0  0
    5 -2
   -7  3
    4  5
    8  1


Each of those inputs has a valid answer!

[geeloso]

These are the stated constraints of the problem:

1 <= n <= 10^5
1 <= k <= n

It seems like ur test cases are more stringent/tasking than the examiner's! I'd let u know how much ur "weird inputs" strain the code I develop.

[Duthomhas]

It shouldn’t strain anything:

  • There are zero ways to arrange zero digits
  • There are zero ways to arrange N,K < 0
  • There is only one way to arrange N < K (all 1s)
  • There are 2^N ways to arrange K==1

The first three problems are just a couple of if checks that should happen before the algorithm gets used.
The last problem is a consequence of binary math, since it describes any binary integer value of size N, and is easily handled by the algorithm.

But yeah, I have a bad habit of missing stuff (or cherry-picking the parts that interest me) when playing with stuff I find on the internet.

[Duthomhas]

Alright, I wanna post my solution, so...

#include <ciso646>
#include <filesystem>
#include <iostream>
#include <sstream>
#include <string>


int usage( std::filesystem::path exename, int exit_code = 1 )
{
  #define T(s) s "\n"
  std::cout <<
    T("usage:")
    T("  " << exename.filename().string() << " N K")
    T("")
    T("Compute the number of binary strings possible when:")
    T("  • each string has length N digits in [0,1]")
    T("  • every 0 in the string must be in a block of")
    T("    some multiple of K consecutive 0s.");
  #undef T
  return exit_code;
}


template <typename T>
T string_to( const std::string& s )
{
  T value;
  std::istringstream ss( s );
  ss >> value >> std::ws;
  if (!ss.eof()) throw std::invalid_argument("T string_to()");
  return value;
}


long choose( long n, long k )
{
  // Compute the Binomial Coefficient
  // (n choose k) = n! / k!(n-k)!
  if (n < k) return 0;
  if (n == k) return 1;

  long product = 1;

  // product ←– n! / (n-k)!
  long n_minus_k = n-k;
  while (n > n_minus_k)
  {
    product *= n--;
  }

  // product ←– product / k!
  while (k > 1)
  {
    product /= k--;
  }

  return product;
}


long solve( long N, long K )
{
  if (N <= 0 or K < 0) return 0;
  if (K == 0) return 1;

  // There are always possible strings of length N '1's.
  long sum = 1;

  // For each m multiples of K
  for (long m = 1;  m*K <= N;  m++)
  {
    // add in the number of possible arrangements
    sum += choose( N - m*K + m, m );
  }

  return sum;
}


int main( int, char ** argv )
try
{
  long N = string_to <long> ( argv[1] );
  long K = string_to <long> ( argv[2] );

  std::cout << solve( N, K ) << "\n";

  return 0;
}
catch (...)
{
  return usage( argv[0] );
}

Linux:

$ clang++ -Wall -Wextra -Werror -pedantic-errors -O3 -std=c++17 a.cpp -o bs

$ ./bs --help
usage:
  bs N K

Compute the number of binary strings possible when:
  • each string has length N digits in [0,1]
  • every 0 in the string must be in a block of
    some multiple of K consecutive 0s.

$ for k in $(seq 0 9); do echo -n "(8 $k) --> "; ./bs 8 $k; done
(8 0) --> 1
(8 1) --> 256
(8 2) --> 34
(8 3) --> 13
(8 4) --> 7
(8 5) --> 5
(8 6) --> 4
(8 7) --> 3
(8 8) --> 2
(8 9) --> 1

$ █

Windows:

C:> cl /nologo /EHsc /W4 /Ox /std:c++17 a.cpp /Fe:bs.exe
a.cpp

C:> bs /?
usage:
  bs N K

Compute the number of binary strings possible when:
  • each string has length N digits in [0,1]
  • every 0 in the string must be in a block of
    some multiple of K consecutive 0s.

C:> for /L %k in (0,1,9) do (<nul set /p=^(8 %k^) --^> & bs 8 %k)
(8 0) --> 1
(8 1) --> 256
(8 2) --> 34
(8 3) --> 13
(8 4) --> 7
(8 5) --> 5
(8 6) --> 4
(8 7) --> 3
(8 8) --> 2
(8 9) --> 1

C:> █

IDK why I enjoy little problems like this so much... heh.

^{BTW, I am pleased if you learn from this. But if you, dear future googler, simply copy-n-paste code for an assignment, you might not be caught, but even if you aren’t (because the prof or TA is too lazy to bother with the simplest of checks), you will have learned nothing, and I feel sorry for the people who will have to put up with you later. Don’t be that fool.}

[geeloso]

@ Duthomhas,

Apologies for my apparently long hiatus! Days ago, upon stumbling on what I cursorily perceived as a solution posted by you, I quickly decided not to go through your posts (last two) till I came up with a working code using the pseudo-algorithm you had given me earlier. Shown below is what I came up with:

int countStr(int n, int k) {
    
    const unsigned int M = 1000000007;
   
    //lambda to calculate factorial
    auto z {[](int n){
        unsigned long long fac {1};
        for (int i = 1; i <= n; i++)
            fac = (fac * i) % M;
        return fac;}
    };
   
    //lambda to calculate combinations
    auto y {[z](int n, int k){
        unsigned long long comb1{1};
        for (int i = n; i >= n-k+1; i--)
            comb1 = (comb1 * i) % M;
        comb1 /= z(k);
        return comb1;}
    };
   
    //accumulating the combinations
    int c{0}, comb{0};
    for (int i = 0; k*i <= n; i++){
        c = y(n-k*i+i, i);  
        comb = (comb + c) % M;
    }

    return comb;
}

It worked for a significant range of values but only for cases where the ratio of n to k is not high. In other words, if n is a lot bigger than k, then I get wrong results. The answer is required to be provided MOD 10e9+7 since the results could be so large, that explains its appearance in the code.

Thanks a ton for the solution you provided; I really wish I fully understood it! Whether due to its overall elegance and/or the arcane nature of some parts of it, I'm thinking you and Bjarne Stroustrup must be pals! LOL! Anyways, my code got the same results as in your test-run that fell within my given constraints. Some parts of your submission are just way over my head! But I hope to explore them some more for learning purposes. I do have myriad questions but, if you don't mind, I'd ask these for now:

1. How does your code handle cases where the ratio of n to k is very high, say when n = 300, k = 2? In this case, I only started getting correct answers from k >= 48. I don't really know why! Is there a way to try these values on your code to see what you get as result?

2. I actually tried running your code with the above values (n = 300, k = 2) on the cpp.sh using the link provided but it seemed to be interminably waiting for some inputs from me. I'm not sure what to feed it as there are no printed input prompts.

3. Ironically, the block in your code that threw me for a loop the most is the first function, usage. Pls, what is going on here?!

4. And how are you using it, usage, in the catch block in main(int, char**)?

Please indulge me if I ask other questions later about your brilliant code after I have fully delved deeper into its workings. Thx.

[Duthomhas]

Hey, welcome back!

1. How does your code handle cases where the ratio of n to k is very high, say when n = 300, k = 2?

It fails.

Remember what the math is here: N represents the number of bits available, and the result represents how many values we can get out of N bits (with restrictions). The largest value we can get is if K=1, requiring N+1 bits to represent as an integer value.
^{For example, if N=8 and K=1, there are 256 possible values, which is 1'0000'0000 in binary — a value requiring nine bits to represent.}

So... any n greater than 63 (number of unsigned bits in a signed long int on modern systems) will fail if K is small enough. 300 is waaaay too many bits to represent in a machine integer type.

The answer is required to be provided MOD 10e9+7 since the results could be so large

Yes. ATM I haven’t done more than gloss my eyes over your code (sorry), but where you apply the remainder function may make a difference. I might come back and give it another look later to see if that is the case.

The correct answer for N=300,K=2 (mod 1000000007) is 893039802. Is that not what you are getting?

2. I actually tried running your code with the above values (n = 300, k = 2)

You have discovered UB — Undefined Behavior (https://en.cppreference.com/w/cpp/language/ub).
Since N is too big, the math fails for the integer type, and you wind up with unexpected behavior.

I suspect that the loop on line 70 is the culprit:

  // For each m multiples of K
  for (long m = 1;  m*K <= N;  m++)
  {

Since m*K overflows it can never be larger than N, hence infinite loop.

3. [Usage magic] Pls, what is going on here?!

The string_to<long>() function throws an exception if the argument string cannot be converted to a long. 😉


If you actually wanted to calculate astronomical values you’d need a bignum
A bignum is an arbitrary-precision integer value, meaning it can have as many digits as memory allows. The Boost Libraries (https://www.boost.org/) conveniently provide us access to easy bignums.
<sup>If you are serious about using C++, you should have Boost Libraries installed. For the following it is enough to simply have the Boost header files properly installed — the cpp_int bignum is a header-only library.

If you are on Windows, use the MSVC installer again and make sure to add the Boost Libraries as part of your install package.
If you are on a Debian-based Linux you can simply sudo apt-get install libboost-all-dev.
Alas, cpp.sh cannot link with Boost, so you’ll have to use https://godbolt.org/ or something that can.</sup>

Here is my program with the minor adjustment of using a bignum instead of a machine long int:

#include <ciso646>
#include <filesystem>
#include <iostream>
#include <sstream>
#include <string>

#include <boost/multiprecision/cpp_int.hpp>
using integer = boost::multiprecision::cpp_int;


int usage( std::filesystem::path exename, int exit_code = 1 )
{
  #define T(s) s "\n"
  std::cout <<
    T("usage:")
    T("  " << exename.filename().string() << " N K")
    T("")
    T("Compute the number of binary strings possible when:")
    T("  • each string has length N digits in [0,1]")
    T("  • every 0 in the string must be in a block of")
    T("    some multiple of K consecutive 0s.");
  #undef T
  return exit_code;
}


template <typename T>
T string_to( const std::string& s )
{
  T value;
  std::istringstream ss( s );
  ss >> value >> std::ws;
  if (!ss.eof()) throw std::invalid_argument("T string_to()");
  return value;
}


integer choose( integer n, integer k )
{
  // Compute the Binomial Coefficient
  // (n choose k) = n! / k!(n-k)!
  if (n < k) return 0;
  if (n == k) return 1;

  integer product = 1;

  // product ←– n! / (n-k)!
  integer n_minus_k = n-k;
  while (n > n_minus_k)
  {
    product *= n--;
  }

  // product ←– product / k!
  while (k > 1)
  {
    product /= k--;
  }

  return product;
}


integer solve( integer N, integer K )
{
  if (N <= 0 or K < 0) return 0;
  if (K == 0) return 1;

  // There are always possible strings of length N '1's.
  integer sum = 1;

  // For each m multiples of K
  for (integer m = 1;  m*K <= N;  m++)
  {
    // add in the number of possible arrangements
    sum += choose( N - m*K + m, m );
  }

  return sum;
}


int main( int, char ** argv )
try
{
  integer N = string_to <integer> ( argv[1] );
  integer K = string_to <integer> ( argv[2] );

  std::cout << solve( N, K ) << "\n";

  return 0;
}
catch (...)
{
  return usage( argv[0] );
}

Again, make sure boost is properly in your include path. Compile as before.

Now we can get the answer to your question:

$ ./bs 300 2
359579325206583560961765665172189099052367214309267232255589801

$ █

That is a lot of combinations!

$ tclsh
% expr {359579325206583560961765665172189099052367214309267232255589801 % 1000000007}
893039802
% exit

An even bigger number is:

$ ./bs 300 1
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376

$ █

We can plug 2³⁰⁰ into any bignum calculator and verify that it is correct.

$ tclsh
% expr {2**300}
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376
% exit

$ █

Always feel free to ask questions.
I will probably peruse your code in a day or two.

[geeloso]

1. The caution you're expressing about the overflow possibilities in your explanation to Qn #1 makes a lot of sense; the accompanying insightful explanation is noteworthy. I think that's why the use of MOD 1e9 + 7 (not 10e9 + 7 as I had written!) is made mandatory for the problem. As you stated, I definitely knew that where I applied the MOD was critical. I've been thinking it may well be the culprit here for not getting the correct answers since this only happens when the ratios are humongous! You are spot on: the correct answer (when n = 300 and k = 2) is 893039802; by the way, I didn't get that with my code!

2. What I was trying to highlight in Qn #2 was my inability to supply values for n & k to your code when I was trying to run it on the C++ shell through the link you provided. There were no clear prompts to cue me in what to provide. I see that in lines 83 and 84 are where you determine n and k, apparently from string arguments fed in through main's formal parameters (int, char** argv). So the string arguments, argv[1] & argv[2], from a logical standpoint, would have to be the inputs; right? I'm more used to dealing with function main having just int in its formal parameter list or just empty.

3. As I asked in Qn #3, what is function usage doing exactly? I know you wrote

The string_to<long>() function throws an exception if the argument string cannot be converted to a long. 😉

I'm still not getting it! It seems like that winking Emoji is a telltale sign that there's much more than meets the eye about this function!! Like I said in my last post, it's the one part of your code that is the most puzzling to me! If I could be more specific, what is that pre-processor directive define in line 10 doing? If it's not classified or proprietary, could you pls explain what this function does vis-a-vis its contents?

4. Thx for the bignum/boost info! It's quite enlightening.

[Ganado]

> #include <ciso646>
Note that <ciso646> was removed in C++20. But I don't think it's even needed for your program.
https://en.cppreference.com/w/cpp/header/ciso646

It's also funny that your inclusion of <filesystem> for the usage information makes the program unable to compile on a bunch of online compilers. :/ Even in the current year™ of 2025.

geeloso wrote:

So the string arguments, argv[1] & argv[2], from a logical standpoint, would have to be the inputs; right?

Yes. Those are command-line arguments. You could change the logic to get the integers from stdin as well. e.g.

integer N;
integer K;
std::cin >> N >> K;

what is function usage doing exactly?

It's just there to print information to the user about how to correctly feed command-line arguments into the program.
Although, Duthomhas's program should be bounds checking argc before dereferencing argv! Bad Duthomhas :)