CareerCup

This is typical 0-1 knapsack problem. Each number could be used either 0 or 1 time. Final result is all 10000 numbers are possible (what a waste of typing...)

public class Main {

        public static void main(String[] args) {
                boolean[] sum = new boolean[10001];
                sum[0] = true;
                for (int i = 1; i <= 1000; i++) {
                      for (int j = sum.length - 1; j >= i; j--) {
                            if (sum[j - i]) {
                                sum[j] = true;
                            }
                      }
                }
		
                int count = 0;
                for (int i = 1; i < sum.length; i++) {
                      if (sum[i]) {
                          count++;
                      }
                }
		
                System.out.println("Total number of combinations are: " + count);
       }

}

I would say sum value of 1-10000 are all possible.

1-1000, n (1 < n < 1000)
1001-1999, 1000+n (1 <= n <= 999)
2000-1999, 1000+999+1+n ( 1 < n <999), 1000+998+2+1, 1000+998+2+9999
....

you could use DP so that you don't have to recalculate sums..

findSums(){
static hash taken;
static int cur_sum = 0;

for (i=1; i <1000 ; ++i){
cur_sum += i;
taken.insert(i);
if(cur_sum < 10000){
// print elements in taken hash
++count;
}
else{ taken.delete(i); break; }
findSums();
taken.delete(i);
}
return count;
}

first of all, all numbers are possible, you don't even need to write an algorithm.

all if you force me to write an algorithm, I would write
for(i = 1000;i>=1;i--){
sum+=i;
if(sum>10000) return true;
}

Total number of possible summations is 2^1000 - 1.
For every new number, there are 2 ^ (N-1) new possible sums to be computed that should be checked against the constraints. That is exponential!
Must be a way to bring it to polynomial.

hows sum of all unmbers going to be <10000.
Ig i use the fomula that gives me the sum of all the numbers from 1-1000 i.e. n(N+1)/2
i get 500500 > 10000.

Can some one clarify?

Using dynamic programming and creating a 2d backtracking table can solve the prob in most efficient way... Will try to write the code... it seems to be similar to knapsack prob except tht here we are not bothered about the reward/smile/etc...

1+2=3
3=3
These are two unique summations, correct? And what this problem is asking is the operands in the summation more than just the answer (e.g. "1+2","3", etc), correct?

I think geniusxy is right, all possible sums between 1 and 10,000 are possible. Hence the number of different summations (ie. distinct sums) possible = 10,000.

I think the solution is all possible subsets of {1,2,3,..,1000} with sum of subset < 10000. Complexity is 2 ^ 1000 (2 ^ N).

all the numbers between 1 and 10000 are possible.

How about something like this?

long long res = 0LL; // the answer
long long dp[10000];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int sum = 1; sum < 10000; ++sum)
{
int lim = sum / 2;
for(int i = 0; i <= lim; ++i)
{
if(i == (sum - i)) continue;
dp[sum] += dp[i] * dp[sum - i];
}
res += dp[sum];
}

Trying to convert a programming program to a mathematical problem
Calculate the number of integral solution for the following equations.

x1 + x2 + x3 +....xn + k = 10000
Constraints
n < 1000
0 < xi <= 1000
0< k < 1000

Let me recall the formula, for the above problem, and then do the programmatic math afterwards.

Please correct me if I got it wrong.

Thanks
Ankush

Number of Positive Integral Solutions of Linear Equations and Inequations

Consider the equation

x1+x2+x3+x4+x5+???+xr = n (I)

where x1,x2,x3,x4,x5,???,xr and n are non negative integers.

This equation may be interpreted as that n identical objects are to be divided into r groups where a group may contain any number of objects. Therefore,


Total number of the non negative integral solutions of equation (I)

= Coefficient of xn in (x0 + x1 + x2 + x3 ??+xn)r

= n+r-1 C r-1

Note : (i) Total number of solutions of the same equation in the set of natural numbers is
n-1 C r-1
(ii) Use more variable to make the inequality to equation/ equality.

Here , r = 1000 + 1 = 1001
n = 10000
Answer = (10000 -1) C (1001 -1)
= 9999 C 1000

Please correct me if I got it wrong in the formula.

Thanks
Ankush

Any computer code would cause overflow.
Consider change the question to using number 1 to 100, and the sum <= 5050, we can get the answer easily: since the sum of 1 to 100 is 5050, so we have:
C(2, 100) = 100*99/2; C(3,100)= 100*99*98/6; ..., C(99,100) = C(1,100)=100.
C(2,100)+ C(3,100)+...+ C(99,100) = 2^100 - 100.

Using number from 1 to 140 with sum <= 9870, we get 2^140-140.

What about

for(r=1;r<142;r++)//141 being the root of n2+n-20000=0
{ for(k=0;k<10000;k++)
s+=C(10000-k+r-1,10000-k);
}

Please comment

"how many different summations"
if this means different summation ways(not sums), it is very similar to a 0/1 integer knapsack problem; if this means different sums, all number between [1, 10000) are possible

How about this? Does anyone have a polynomial time algorithm?

/**
     * Write an algorithm to determine how many different subsets of integers
     * in the range 1...j have a sum less than k.
     */
    private long sumCount;
    private int n;
    private int maxSum;

    public long howManySums(int j, int k) {

        // This problem is akin to counting the number of sets in a powerset.
        // The brute force approach is to find the powerset of j, counting
        // only those subsets with sums equal to or less than k.

        // If j is greater than k-1, reset its value to k-1 as we won't
        // be using any integers greater than k-1 since our range starts
        // at 1.
        if (j > k - 1)
            j = k - 1;

        // The maximum count (maximum number of subsets) is 2^j and it will
        // occur when 1/2(j(j+1)) is equal to or less than k. If 1/2(j(j+1) is
        // equal to or less than k, return 2^j.
        double d = 0.5 * (j * (j + 1));
        if (d <= k) return (long)Math.pow(2, j);

        // Otherwise, find the powerset of 1..j, counting only those subsets
        // with sums equal to or less than k. Assume that we do not want
        // to save the subsets.
        sumCount = 0;
        n = j+1;

        // Create the original set.
        int[] a = new int[n];
        for (int i = 1; i < n; i++) {
            a[i - 1] = i;
        }

        // Count the valid powersets.
        maxSum = k;
        countValidPowersets(a, new HashSet(), 0, 0);
        return sumCount;
    }

    private void countValidPowersets(int[] a, Set subset, int sum, int start) {
        for (int i = start; i < n; i++) {
            int w = a[i];
            sum = sum + w;
            if (sum >= maxSum) break;
            sumCount++;
            if (i < n - 1) {
                subset.add(w);
                countValidPowersets(a, subset, sum, i + 1);
                subset.remove(w);
            }
        }
    }

Some of you are really morons. Summation is not the same as sum. For example, 10 has at least two different summations: 1+2+7 or 2+3+5. But 1+2+7 and 2+3+5 both have the same sum. So when some of you idiots say that all summations 1 to 10000 are possible, what you really mean is that all SUMS in that range are possible. That is way different than what the question is asking for. Why do you even waste your time answering questions when you lack even basic comprehension skills?

Restating the problem:
In how many ways you can get a given sum by adding the numbers in the range [1,1000] provided a number can be used only once and given sum is less than 10000.
int GetSummationsCount(int sum); //return the number of summations possible

One approach could be
Pick the numbers in order from 1 -n
First we pick 1 and put it in array A. Then A is
1

Now we pick 2. Then A is
1
1+2
2

Now we pick 3. Then A is
1
1+2
2
1+3
1+2+3
2+3
3

Now we pick 4. Then A is
1
1+2
2
1+3
1+2+3
2+3
3
1+4
1+2+4
2+4
1+3+4
1+2+3+4
2+3+4
3+4
4

This is the basic idea. Now each time any of the above summations is equal to the desired number, we can print the summation and increase the count.
Storing so many permutations is bad, can anyone optimize it even further

One approach could be
Pick the numbers in order from 1 -n
First we pick 1 and put it in array A. Then A is
1

Now we pick 2. Then A is
1
1+2
2

Now we pick 3. Then A is
1
1+2
2
1+3
1+2+3
2+3
3

Now we pick 4. Then A is
1
1+2
2
1+3
1+2+3
2+3
3
1+4
1+2+4
2+4
1+3+4
1+2+3+4
2+3+4
3+4
4

This is the basic idea. Now each time any of the above summations is equal to the desired number, we can print the summation and increase the count.
Storing so many permutations is bad, can anyone optimize it even further

Dynamic programming: build a 2 dimentional table, with columns being the maximum number used (<= 1000) and rows being the sum (<= 10000).

No. of Summations of n numbers with largest sum till k
S(n,k) = S(n-1,k) + S(n-1,k-n)

nice dp idea above, but it should be:

s(n, k): no. of summations using numbers from [1, n] where sum of them <k

s(n-1, k)+s(n-1, k-n)+1, if n<k
s(n,k)=
s(n-1, k)+s(n-1, k-n), if(n>=k)

initialize, s(1, 2)=1, ...., s(1, 1000)=1, all other s(1, x)=0, x from -9000 to 9000

run the function with s(1000, 10000)

Given numbers 1 to x, let us have a bitmap where every bit indicates a number.
1 for 1, 10 for 2, 100 for 3 etc. For summation of 2 and 3, we can OR the bitmaps to get 110. So, to find every possible summation, we just need to know all the numbers we can make by flipping each of the bits. Now, all you need to do is generate all the numbers between 1 and 11111 (here, x= 5)

This is a subset sum problem.
sum[j]@(i)=sum[j]@(i-1) V sum[j-i]@i

To generate the sum for every number in 1...10000:
1) 1, 2, 3, ...9
2) 10, 20, 30,...90
3) 100, 200, 300, ... 900
4) 981 + 19, 982 + 18, 983 + 17, ... 989 + 11 => 1000, 1000, 1000, .... 1000 (9 possible summation for 1000)
Use the combinations above, any number between 1...9999 can be generated easily. For example:
2476 = (981+19) + (982 + 18) + 400 + 70 + 6
You get the idea. All of the numbers used in the equation are guaranteed to be unique. 10000 is easy to generate as well.

So what's the answer, assuming the question is asking about the number of different ways to form a sum < 10000 (eg. 1+3+4 and 1+2+5 are two different ways)? I had a hard time with the DP recurrence and initial conditions so I am not sure whether my answer (5841289763241281300) is right or not....

Here's an algorithm that works in O(N^4).

void SummationCounts()
 10 {
 11   size_t N = 1000;
 12   unsigned long long summationCount = 0;
 13 
 14   for (size_t i = 1; i <= N; i++)
 15   {
 16     if (i < 10000)
 17     {
 18       summationCount++;
 19       //cout << i << endl;
 20     }
 21     size_t stride = 1;
 22     while (stride < N)
 23     {
 24       for (size_t j = i; j < N; j++)
 25       {
 26         size_t start = j + 1, end = start + stride - 1;
 27         if (end > N) break;
 28         unsigned int sum = i;
 29         stringstream setStr;
 30         setStr << sum << ",";
 31         size_t k = start;
 32         while (k <= end)
 33         {
 34           sum += k;
 35           if (sum > 10000) break;
 36           setStr << k << ",";
 37           k++;
 38         }
 39         if (k > end)
 40         {
 41           //cout << setStr.str() << endl;
 42           summationCount++;
 43         }
 44       }
 45 
 46       stride++;
 47     }
 48   }
 49 
 50   cout << "Total summation counts: " << summationCount << endl;
      }