Implementation: Algorithm for a special distribution Problem












6















We are given a number x, and a set of n coins with denominations v1, v2, …, vn.



The coins are to be divided between Alice and Bob, with the restriction that each person's coins must add up to at least x.



For example, if x = 1, n = 2, and v1 = v2 = 2, then there are two possible distributions: one where Alice gets coin #1 and Bob gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)



I'm interested in counting the possible distributions. I'm pretty sure this can be done in O(nx) time and O(n+x) space using dynamic programming; but I don't see how.










share|improve this question

























  • when are 2 distributions different? By values or by coin indexes?

    – juvian
    Nov 21 '18 at 17:17











  • @juvian Coin indexes.

    – faegra
    Nov 21 '18 at 17:28
















6















We are given a number x, and a set of n coins with denominations v1, v2, …, vn.



The coins are to be divided between Alice and Bob, with the restriction that each person's coins must add up to at least x.



For example, if x = 1, n = 2, and v1 = v2 = 2, then there are two possible distributions: one where Alice gets coin #1 and Bob gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)



I'm interested in counting the possible distributions. I'm pretty sure this can be done in O(nx) time and O(n+x) space using dynamic programming; but I don't see how.










share|improve this question

























  • when are 2 distributions different? By values or by coin indexes?

    – juvian
    Nov 21 '18 at 17:17











  • @juvian Coin indexes.

    – faegra
    Nov 21 '18 at 17:28














6












6








6








We are given a number x, and a set of n coins with denominations v1, v2, …, vn.



The coins are to be divided between Alice and Bob, with the restriction that each person's coins must add up to at least x.



For example, if x = 1, n = 2, and v1 = v2 = 2, then there are two possible distributions: one where Alice gets coin #1 and Bob gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)



I'm interested in counting the possible distributions. I'm pretty sure this can be done in O(nx) time and O(n+x) space using dynamic programming; but I don't see how.










share|improve this question
















We are given a number x, and a set of n coins with denominations v1, v2, …, vn.



The coins are to be divided between Alice and Bob, with the restriction that each person's coins must add up to at least x.



For example, if x = 1, n = 2, and v1 = v2 = 2, then there are two possible distributions: one where Alice gets coin #1 and Bob gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)



I'm interested in counting the possible distributions. I'm pretty sure this can be done in O(nx) time and O(n+x) space using dynamic programming; but I don't see how.







algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 23 '18 at 0:35







faegra

















asked Nov 21 '18 at 16:50









faegrafaegra

334




334













  • when are 2 distributions different? By values or by coin indexes?

    – juvian
    Nov 21 '18 at 17:17











  • @juvian Coin indexes.

    – faegra
    Nov 21 '18 at 17:28



















  • when are 2 distributions different? By values or by coin indexes?

    – juvian
    Nov 21 '18 at 17:17











  • @juvian Coin indexes.

    – faegra
    Nov 21 '18 at 17:28

















when are 2 distributions different? By values or by coin indexes?

– juvian
Nov 21 '18 at 17:17





when are 2 distributions different? By values or by coin indexes?

– juvian
Nov 21 '18 at 17:17













@juvian Coin indexes.

– faegra
Nov 21 '18 at 17:28





@juvian Coin indexes.

– faegra
Nov 21 '18 at 17:28












3 Answers
3






active

oldest

votes


















4














Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).



For example,



{2, 3, 3, 5}, x = 5

i matrix
0 2: 1
1 3: 1 (adding to 2 is too much)
2 3: 2
3 N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8


The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.



# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
n1=n
k1=k
if n<=0:
return 1
elif k<=0:
return 0
elif (n==0 and k==0):
return -1
elif n!=0 and n==k:
return 1
elif n<k:
return 0
else:
temp1=stirling(n1-1,k1)
temp1=k1*temp1
return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
a = [1] + (x-1) * [0]

# Code by MBo
# https://stackoverflow.com/a/53418438/2034787
for c in coins:
for i in xrange(x - 1, c - 1, -1):
if a[i - c] > 0:
a[i] = a[i] + a[i - c]

return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16





share|improve this answer


























  • Nice catch concerning non-significant nominals!

    – MBo
    Nov 22 '18 at 14:19













  • How exactly do you count count the ways for one person to get just less than x ?

    – faegra
    Nov 22 '18 at 15:55











  • @faegra MBo described such a method. Can you think of how to modify it to achieve this?

    – גלעד ברקן
    Nov 22 '18 at 16:39













  • @faegra added code.

    – גלעד ברקן
    Nov 22 '18 at 16:57






  • 1





    great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

    – juvian
    Nov 23 '18 at 1:28



















3














If sum of all coins is S, then the first person can get x..S-x of money.



Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).



To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction



A[0] = 1
for C in Coins:
for i = S-x downto C:
if A[i - C] > 0:
A[i] = A[i] + A[i - C]
//we can compose value i as i-C and C


then sum A entries in range x..S-x



Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8



Array state after using coins in order:



0 1 2 3 4 5 6 7 8  //idx
1 1
1 1 1 1
1 1 2 2 1 1
1 1 2 3 1 1 3


So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):



2 3      3' 5
2 3' 3 5
2 3 3' 5
2 5 3 3'
3 3' 2 5
3 5 2 3'
3' 5 2 3
5 2 3 3'





share|improve this answer


























  • But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

    – faegra
    Nov 22 '18 at 15:15











  • This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

    – MBo
    Nov 22 '18 at 15:32



















3














You can also solve it in O(A * x^2) time and memory adding memoization to this dp:



solve(A, pos, sum1, sum2):
if (pos == A.length) return sum1 == x && sum2 == x
return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) +
solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))


So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x






share|improve this answer





















  • 1





    UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

    – MBo
    Nov 21 '18 at 19:19













  • It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

    – juvian
    Nov 21 '18 at 19:41











  • @juvian What are the dimensions fo A?

    – faegra
    Nov 21 '18 at 20:10











  • @faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

    – juvian
    Nov 21 '18 at 20:27











  • @juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

    – faegra
    Nov 21 '18 at 20:37











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53416924%2fimplementation-algorithm-for-a-special-distribution-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









4














Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).



For example,



{2, 3, 3, 5}, x = 5

i matrix
0 2: 1
1 3: 1 (adding to 2 is too much)
2 3: 2
3 N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8


The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.



# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
n1=n
k1=k
if n<=0:
return 1
elif k<=0:
return 0
elif (n==0 and k==0):
return -1
elif n!=0 and n==k:
return 1
elif n<k:
return 0
else:
temp1=stirling(n1-1,k1)
temp1=k1*temp1
return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
a = [1] + (x-1) * [0]

# Code by MBo
# https://stackoverflow.com/a/53418438/2034787
for c in coins:
for i in xrange(x - 1, c - 1, -1):
if a[i - c] > 0:
a[i] = a[i] + a[i - c]

return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16





share|improve this answer


























  • Nice catch concerning non-significant nominals!

    – MBo
    Nov 22 '18 at 14:19













  • How exactly do you count count the ways for one person to get just less than x ?

    – faegra
    Nov 22 '18 at 15:55











  • @faegra MBo described such a method. Can you think of how to modify it to achieve this?

    – גלעד ברקן
    Nov 22 '18 at 16:39













  • @faegra added code.

    – גלעד ברקן
    Nov 22 '18 at 16:57






  • 1





    great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

    – juvian
    Nov 23 '18 at 1:28
















4














Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).



For example,



{2, 3, 3, 5}, x = 5

i matrix
0 2: 1
1 3: 1 (adding to 2 is too much)
2 3: 2
3 N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8


The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.



# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
n1=n
k1=k
if n<=0:
return 1
elif k<=0:
return 0
elif (n==0 and k==0):
return -1
elif n!=0 and n==k:
return 1
elif n<k:
return 0
else:
temp1=stirling(n1-1,k1)
temp1=k1*temp1
return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
a = [1] + (x-1) * [0]

# Code by MBo
# https://stackoverflow.com/a/53418438/2034787
for c in coins:
for i in xrange(x - 1, c - 1, -1):
if a[i - c] > 0:
a[i] = a[i] + a[i - c]

return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16





share|improve this answer


























  • Nice catch concerning non-significant nominals!

    – MBo
    Nov 22 '18 at 14:19













  • How exactly do you count count the ways for one person to get just less than x ?

    – faegra
    Nov 22 '18 at 15:55











  • @faegra MBo described such a method. Can you think of how to modify it to achieve this?

    – גלעד ברקן
    Nov 22 '18 at 16:39













  • @faegra added code.

    – גלעד ברקן
    Nov 22 '18 at 16:57






  • 1





    great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

    – juvian
    Nov 23 '18 at 1:28














4












4








4







Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).



For example,



{2, 3, 3, 5}, x = 5

i matrix
0 2: 1
1 3: 1 (adding to 2 is too much)
2 3: 2
3 N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8


The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.



# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
n1=n
k1=k
if n<=0:
return 1
elif k<=0:
return 0
elif (n==0 and k==0):
return -1
elif n!=0 and n==k:
return 1
elif n<k:
return 0
else:
temp1=stirling(n1-1,k1)
temp1=k1*temp1
return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
a = [1] + (x-1) * [0]

# Code by MBo
# https://stackoverflow.com/a/53418438/2034787
for c in coins:
for i in xrange(x - 1, c - 1, -1):
if a[i - c] > 0:
a[i] = a[i] + a[i - c]

return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16





share|improve this answer















Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).



For example,



{2, 3, 3, 5}, x = 5

i matrix
0 2: 1
1 3: 1 (adding to 2 is too much)
2 3: 2
3 N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8


The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.



# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
n1=n
k1=k
if n<=0:
return 1
elif k<=0:
return 0
elif (n==0 and k==0):
return -1
elif n!=0 and n==k:
return 1
elif n<k:
return 0
else:
temp1=stirling(n1-1,k1)
temp1=k1*temp1
return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
a = [1] + (x-1) * [0]

# Code by MBo
# https://stackoverflow.com/a/53418438/2034787
for c in coins:
for i in xrange(x - 1, c - 1, -1):
if a[i - c] > 0:
a[i] = a[i] + a[i - c]

return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 22 '18 at 17:02

























answered Nov 22 '18 at 13:38









גלעד ברקןגלעד ברקן

13.2k21543




13.2k21543













  • Nice catch concerning non-significant nominals!

    – MBo
    Nov 22 '18 at 14:19













  • How exactly do you count count the ways for one person to get just less than x ?

    – faegra
    Nov 22 '18 at 15:55











  • @faegra MBo described such a method. Can you think of how to modify it to achieve this?

    – גלעד ברקן
    Nov 22 '18 at 16:39













  • @faegra added code.

    – גלעד ברקן
    Nov 22 '18 at 16:57






  • 1





    great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

    – juvian
    Nov 23 '18 at 1:28



















  • Nice catch concerning non-significant nominals!

    – MBo
    Nov 22 '18 at 14:19













  • How exactly do you count count the ways for one person to get just less than x ?

    – faegra
    Nov 22 '18 at 15:55











  • @faegra MBo described such a method. Can you think of how to modify it to achieve this?

    – גלעד ברקן
    Nov 22 '18 at 16:39













  • @faegra added code.

    – גלעד ברקן
    Nov 22 '18 at 16:57






  • 1





    great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

    – juvian
    Nov 23 '18 at 1:28

















Nice catch concerning non-significant nominals!

– MBo
Nov 22 '18 at 14:19







Nice catch concerning non-significant nominals!

– MBo
Nov 22 '18 at 14:19















How exactly do you count count the ways for one person to get just less than x ?

– faegra
Nov 22 '18 at 15:55





How exactly do you count count the ways for one person to get just less than x ?

– faegra
Nov 22 '18 at 15:55













@faegra MBo described such a method. Can you think of how to modify it to achieve this?

– גלעד ברקן
Nov 22 '18 at 16:39







@faegra MBo described such a method. Can you think of how to modify it to achieve this?

– גלעד ברקן
Nov 22 '18 at 16:39















@faegra added code.

– גלעד ברקן
Nov 22 '18 at 16:57





@faegra added code.

– גלעד ברקן
Nov 22 '18 at 16:57




1




1





great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

– juvian
Nov 23 '18 at 1:28





great answer. I think the uncommon case of sum of elements being < 2x should be handled separately

– juvian
Nov 23 '18 at 1:28













3














If sum of all coins is S, then the first person can get x..S-x of money.



Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).



To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction



A[0] = 1
for C in Coins:
for i = S-x downto C:
if A[i - C] > 0:
A[i] = A[i] + A[i - C]
//we can compose value i as i-C and C


then sum A entries in range x..S-x



Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8



Array state after using coins in order:



0 1 2 3 4 5 6 7 8  //idx
1 1
1 1 1 1
1 1 2 2 1 1
1 1 2 3 1 1 3


So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):



2 3      3' 5
2 3' 3 5
2 3 3' 5
2 5 3 3'
3 3' 2 5
3 5 2 3'
3' 5 2 3
5 2 3 3'





share|improve this answer


























  • But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

    – faegra
    Nov 22 '18 at 15:15











  • This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

    – MBo
    Nov 22 '18 at 15:32
















3














If sum of all coins is S, then the first person can get x..S-x of money.



Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).



To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction



A[0] = 1
for C in Coins:
for i = S-x downto C:
if A[i - C] > 0:
A[i] = A[i] + A[i - C]
//we can compose value i as i-C and C


then sum A entries in range x..S-x



Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8



Array state after using coins in order:



0 1 2 3 4 5 6 7 8  //idx
1 1
1 1 1 1
1 1 2 2 1 1
1 1 2 3 1 1 3


So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):



2 3      3' 5
2 3' 3 5
2 3 3' 5
2 5 3 3'
3 3' 2 5
3 5 2 3'
3' 5 2 3
5 2 3 3'





share|improve this answer


























  • But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

    – faegra
    Nov 22 '18 at 15:15











  • This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

    – MBo
    Nov 22 '18 at 15:32














3












3








3







If sum of all coins is S, then the first person can get x..S-x of money.



Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).



To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction



A[0] = 1
for C in Coins:
for i = S-x downto C:
if A[i - C] > 0:
A[i] = A[i] + A[i - C]
//we can compose value i as i-C and C


then sum A entries in range x..S-x



Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8



Array state after using coins in order:



0 1 2 3 4 5 6 7 8  //idx
1 1
1 1 1 1
1 1 2 2 1 1
1 1 2 3 1 1 3


So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):



2 3      3' 5
2 3' 3 5
2 3 3' 5
2 5 3 3'
3 3' 2 5
3 5 2 3'
3' 5 2 3
5 2 3 3'





share|improve this answer















If sum of all coins is S, then the first person can get x..S-x of money.



Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).



To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction



A[0] = 1
for C in Coins:
for i = S-x downto C:
if A[i - C] > 0:
A[i] = A[i] + A[i - C]
//we can compose value i as i-C and C


then sum A entries in range x..S-x



Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8



Array state after using coins in order:



0 1 2 3 4 5 6 7 8  //idx
1 1
1 1 1 1
1 1 2 2 1 1
1 1 2 3 1 1 3


So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):



2 3      3' 5
2 3' 3 5
2 3 3' 5
2 5 3 3'
3 3' 2 5
3 5 2 3'
3' 5 2 3
5 2 3 3'






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 21 '18 at 18:54

























answered Nov 21 '18 at 18:29









MBoMBo

49.4k23051




49.4k23051













  • But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

    – faegra
    Nov 22 '18 at 15:15











  • This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

    – MBo
    Nov 22 '18 at 15:32



















  • But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

    – faegra
    Nov 22 '18 at 15:15











  • This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

    – MBo
    Nov 22 '18 at 15:32

















But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

– faegra
Nov 22 '18 at 15:15





But that needs O(S-x+1) space instead of O(n+x). Is there a way to improve this? Also, the runtime is bigger than O(nx),

– faegra
Nov 22 '18 at 15:15













This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

– MBo
Nov 22 '18 at 15:32





This approach cannot be improved as-is, but @גלעד ברקן proposed inversion - instead of calculation for 0..S-x interval make calculation for complementary 0..x interval

– MBo
Nov 22 '18 at 15:32











3














You can also solve it in O(A * x^2) time and memory adding memoization to this dp:



solve(A, pos, sum1, sum2):
if (pos == A.length) return sum1 == x && sum2 == x
return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) +
solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))


So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x






share|improve this answer





















  • 1





    UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

    – MBo
    Nov 21 '18 at 19:19













  • It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

    – juvian
    Nov 21 '18 at 19:41











  • @juvian What are the dimensions fo A?

    – faegra
    Nov 21 '18 at 20:10











  • @faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

    – juvian
    Nov 21 '18 at 20:27











  • @juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

    – faegra
    Nov 21 '18 at 20:37
















3














You can also solve it in O(A * x^2) time and memory adding memoization to this dp:



solve(A, pos, sum1, sum2):
if (pos == A.length) return sum1 == x && sum2 == x
return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) +
solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))


So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x






share|improve this answer





















  • 1





    UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

    – MBo
    Nov 21 '18 at 19:19













  • It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

    – juvian
    Nov 21 '18 at 19:41











  • @juvian What are the dimensions fo A?

    – faegra
    Nov 21 '18 at 20:10











  • @faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

    – juvian
    Nov 21 '18 at 20:27











  • @juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

    – faegra
    Nov 21 '18 at 20:37














3












3








3







You can also solve it in O(A * x^2) time and memory adding memoization to this dp:



solve(A, pos, sum1, sum2):
if (pos == A.length) return sum1 == x && sum2 == x
return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) +
solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))


So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x






share|improve this answer















You can also solve it in O(A * x^2) time and memory adding memoization to this dp:



solve(A, pos, sum1, sum2):
if (pos == A.length) return sum1 == x && sum2 == x
return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) +
solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))


So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 21 '18 at 20:47

























answered Nov 21 '18 at 18:57









juvianjuvian

13.4k22127




13.4k22127








  • 1





    UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

    – MBo
    Nov 21 '18 at 19:19













  • It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

    – juvian
    Nov 21 '18 at 19:41











  • @juvian What are the dimensions fo A?

    – faegra
    Nov 21 '18 at 20:10











  • @faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

    – juvian
    Nov 21 '18 at 20:27











  • @juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

    – faegra
    Nov 21 '18 at 20:37














  • 1





    UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

    – MBo
    Nov 21 '18 at 19:19













  • It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

    – juvian
    Nov 21 '18 at 19:41











  • @juvian What are the dimensions fo A?

    – faegra
    Nov 21 '18 at 20:10











  • @faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

    – juvian
    Nov 21 '18 at 20:27











  • @juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

    – faegra
    Nov 21 '18 at 20:37








1




1





UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

– MBo
Nov 21 '18 at 19:19







UV for alternative. Seems the last argument is missed in the first recursive call. And is ==x correct here?

– MBo
Nov 21 '18 at 19:19















It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

– juvian
Nov 21 '18 at 19:41





It's ==x because we never have values over x. Code was wrong using max instead of min, fixed ^^ @MBo

– juvian
Nov 21 '18 at 19:41













@juvian What are the dimensions fo A?

– faegra
Nov 21 '18 at 20:10





@juvian What are the dimensions fo A?

– faegra
Nov 21 '18 at 20:10













@faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

– juvian
Nov 21 '18 at 20:27





@faegra A in the code is the array of coins, in the complexity is the amount of coins, a bit of notation abuse ^^

– juvian
Nov 21 '18 at 20:27













@juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

– faegra
Nov 21 '18 at 20:37





@juvian I am a bit confused. Where exactly is the solution displayed? At the end sum1 == x && sum2 == x will output but this is a boolean and not the solution?

– faegra
Nov 21 '18 at 20:37


















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53416924%2fimplementation-algorithm-for-a-special-distribution-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







這個網誌中的熱門文章

Xamarin.form Move up view when keyboard appear

Post-Redirect-Get with Spring WebFlux and Thymeleaf

Anylogic : not able to use stopDelay()