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.}