2

I need help to modify the solution I came up with for a programming challenge. The problem statement says as follows:

Martin the zebra of Madagascar (the movie) wants to fill the hole that's left to cover in the floor of the hut that is building in the edge of the beach. The hole has length L and Martin has many pieces of wood, some with length s and others with length t. As Martin is very distracted he wants to know in how many ways the hole can be filled by putting pieces of wood at will.

Input specification
The only line of input contains three integers L, s and t separated with a space (1 <= L, s, t <= 10^6, s != t).

Output specification
A line with the number of different ways to fill the hole modulo 10^9 + 7 (1000000007).

Sample input
6 2 3

Sample output
2

The solution I submitted, uses this function to count:

#include <iostream>
#include <vector>

using namespace std;

int ** create(int n, int m) {
  int ** a = new int*[
  for (int i = 0; i < n; i++) {
    a[i] = new int[m]; 
    a[i][0] = 1; // I assumed there is one way to fill a hole of length zero
  }
  return a;
}

int count(vector<int>  stick, int n, int m) { // Counts ways to fill the hole
  int ** fill = create(n + 1, m + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (j < stick[i - 1])
        fill[i][j] = fill[i - 1][j] % 1000000007;
      else
        fill[i][j] = (fill[i - 1][j] + fill[i][j - stick[i - 1]]) %   1000000007;
  return fill[n][m];
}

int main() {
  int l, a, b;
  cin >> l >> a >> b;
  vector<int> stick{a, b};
  cout << count(stick, stick.size(), l) << endl;
  return 0;
}

The problem is that this only counts the different sets that can fill the hole completely, for example:

Say we have a hole of length L = 6 and sticks of lengths s = 1 and t = 2, my function returns 4. This are the four sets that my function is counting:

{1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 2}
{1, 1, 2, 2}
{2, 2, 2}

But what it's required are all the permutations of this sets, hence this should return 13, that is:

{1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 2}
{1, 1, 1, 2, 1}
{1, 1, 2, 1, 1}
{1, 2, 1, 1, 1}
{2, 1, 1, 1, 1}
{1, 1, 2, 2}
{1, 2, 1, 2}
{2, 1, 1, 2}
{1, 2, 2, 1}
{2, 1, 2, 1}
{2, 2, 1, 1}
{2, 2, 2}

How can I modify my function to count all the permutations? Is there any material that can help me understand how to build a dynamic programming solutions for this kind of problems?

Miguel Angel Perez Colula
  • 33
  • 5
  • Please take a look at http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer . You have the first portion of the solution, namely the sets (n=4). If you permute each set, you should be able to obtain the second (n=13). – rajah9 Jun 12 '15 at 18:23
  • @rajah9 Thank you, it's been really helpful to understand how permutations work, but I don't want to extract the sets from the table and compute all the permutations for each set because it'll be really expensive. Is there a way to use this knowledge to count the permutations in the dp without computing the permutations? – Miguel Angel Perez Colula Jun 13 '15 at 23:35
  • Yes. In the first line, there are 6 choose 0 = 1 way to place the 2. In the second through fifth lines, there are 5 choose 1 = 5 ways to place the 2. In the set of size 4 (the seventh through 12th lines), there are 4 choose 2 = 6 ways to place the 2. In the last line there are 3 choose 3 = 1 way to place the 2s. In each case, we are using the choose function, which is used for permutations. The first number decreases from 6 to 3 by 1. The second number increases from 0 to 3 by 1. – rajah9 Jun 15 '15 at 05:43

1 Answers1

3

let d[i] - number of ways to fill the hole of length i

then d[i] = d[i-s] + d[i-t]

d[0] = 1

d[i < 0] = 0 obviously

Herokiller
  • 2,891
  • 5
  • 32
  • 50
  • Your recursion gives `d[i]=0` for all i. – Edward Doolittle Jun 15 '15 at 10:21
  • Yes. It's interesting that when s=1 and t=2, you get the Fibonacci sequence, which gives me an idea for a very fast implementation. – Edward Doolittle Jun 15 '15 at 16:16
  • @Herokiller Thank you, your recurrence has worked perfectly :) . Although the answer is correct,I won't marked as solved yet. I will try to give an answer explaining why this worked and how to solve similar problems, so it becomes easier for novices like me to understand this particular problem. Thanks again! – Miguel Angel Perez Colula Jun 19 '15 at 21:18
  • @MiguelAngelPerezColula what exactly is unclear here? for any i, we know that the last move could only be s or t and we also know that we've calculated answers for i-s and i-t – Herokiller Jun 29 '15 at 10:10