CODEWITHSUNDEEP
calgorithmperformancetime
yobro97
yobro97

Reputation: 1145

Efficient way to find number of sums possible

Given three integers n, k and d, how many ways can n be represented as sum of positive integers i<=k, such that d occurs at least once in the sum. It is guarenteed that 0<d<=k. My approach was a recursive one;

#include <stdio.h>
#include <stdlib.h>
int n,k,d,ans=0;
void solve(int totw,int flag)//totw is the total sum till now, and flag is to keep track of the number of d's in the sum.
{
    if(totw>n)
        return;
    if(totw==n && flag>0)//flag>0--->at least 1 d
    {
        ans = (ans+1)%1000000007;//answer is expected modulo 10^9+7
        return;
    }
    int i=1,h=k;
    if(h>n-totw)
        h=n-totw;
    while(i<=h)
    {
        if(i==d)
            flag++;
        solve(totw+i,flag);
        i++;
    }
}
int main()
{
    scanf("%d %d %d",&n,&k,&d);
    solve(0,0);
    printf("%d",ans);
}

Input:
3 3 2
Output:
2
But the judge shows Time Limit Exceeded. Is there any more efficient algorithm to proceed with in this case? 0<n,k<=100
PS:I was just wondering whether there is any combinatoric argument that can solve this question without recursion or iteration. And yes....order of sums matter.

Upvotes: 5

Views: 219

Answers (3)

chux
chux

Reputation: 153457

Certainly some combinatoric math can solve this without even using code. But the recursive challenge looked fun to try to code.

A lightly tested, example - not much more efficient than OP's.
(Step 1, use more meaningful variable names)

unsigned long solve(unsigned sum_n, unsigned max_value_k, unsigned special_d) {
  if (sum_n == 0) return special_d == 0;
  unsigned long solutions = 0;

  // Improve efficiency, only loop up to min(k,n)
  if (max_value_k > sum_n) {
    max_value_k = sum_n;
  }

  // Will the loop contain d?
  if (max_value_k >= special_d) {
    for (unsigned i = 1; i <= max_value_k; i++) {
      solutions += solve(sum_n - i, max_value_k,
          i == special_d ? 0 : special_d);
      solutions %= 1000000007;
    }
  }
  return solutions;
}

#include <stdio.h>
int main(void) {
  unsigned n, k, d;
  for (n=0; n<100; n++) {
    printf("%u %lu\n", n, solve(n, 100, 1));
    fflush(stdout);
  }
  scanf("%u %u %u", &n, &k, &d);
  printf("%lu\n", solve(n, k, d));
}

Upvotes: 0

md5
md5

Reputation: 23699

You can represent your recursive calls as a graph. Each node is given by the parameters of your function (totw, flag), and you add an edge whenever you make a recursive call. There are about n*2 nodes and n*2*k edges in this graph.

This graph has a very interesting property: it is a DAG (e.g. because totw is strictly increasing at each call). Therefore, when you call solve(totw, flag), you can keep the result in an array, so that you don't compute it twice.

This is actually a way to explain dynamic programming: an algorithm to find the shortest path in a DAG (with slight modifications it can also compute the longest path/the number of paths, but you get the idea). The time complexity on a graph G = (V, E) will be a O(|V|+|E|) (that's actually a kind of amortized analysis).

Thus, keeping the results in an array will result in a O(nk) time complexity.

Actually you can make the implementation even shorter by changing slightly the graph:

enum { UNKNOWN = -1 };

/* not tested */
/* solve(num, d_seen): returns the answer to the problem with a sum
   target, knowing whether `d` was already used */
int solve(int sum, int d_seen)
{
  if (sum == 0) return d_seen;
  int ans = dp[sum][d_seen];
  if (ans == UNKNOWN) {
    ans = 0;
    /* min(a, b) being what it is supposed to be */
    for (int i = 1; i <= min(sum, k); ++i)
      ans = (ans + solve(sum - i, d_seen || (i == d))) % MOD;
  }

  return (dp[sum][d_seen] = ans);
}

By the way you don't put flag back to 0 after incrementing it.

Upvotes: 1

Benson Lin
Benson Lin

Reputation: 1404

Referring to this Wikipedia page: Stars and Bars

Basically the number of ways to split a number n into k positive integers is (n-1)C(k-1) or n-1 choose k-1. Thus, you can iterate for k = 1 to n-d-1 to find the number of ways you can split n-d-1 into any number of positive integers.

Refer here to find out how to efficiently calculate nCk for large n and k efficiently

Upvotes: 0

Related Questions