Balanced centrifuge configurations

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












7














Given an input N as the size of a centrifuge, I need to find out the number of balanced configurations. The full description is here.




Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.



For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube k are $Rsin a, Rcos a$, where $a = 2pifrackn$



The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?



example 1: given N = 6 possible values for K are 2,3,4,6.



example 2: given N = 12, it is possible to balance 5 tubes: put 3 evenly dispersed (every 4th hole), then find a pair of opposite unoccupied holes and insert remaining 2 tubes there.



example 3: given N = 10, it is impossible to balance 7 tubes: put 5 evenly dispersed, and there's no opposite unoccupied holes left!



Input



Line 1: An integer N for the capacity of the centrifuge.



Output



Line 1: An integer M for the number of different possible values of K.




This is my code:



import numpy as np

N=int(input())
angle = 2*np.pi/N
z = complex(np.cos(angle), np.sin(angle))


import itertools
combs =
lst = range(1,N)
for i in range(2, N-1):
combs.append(i)
els = [list(x) for x in itertools.combinations(lst, i)]
combs.append(els)


count=1
lis =
while count<=len(combs):
for a in range(len(combs[count])):
s=0
for b in range(len(combs[count][a])):
s+=z**combs[count][a][b]
if abs(s)<1e-10:
lis.append(combs[count][a])
count+=2


lengths =
for i in lis:
if len(i) not in lengths:
lengths.append(len(i))

print(len(lengths)+1)


The code works fine, but slows down after input size of above 20, and is practically unusable after the input grows to 50 or above, due to the for loops. How do I optimize it?










share|improve this question























  • Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
    – Zeta
    Dec 20 '18 at 7:58










  • @Zeta Is it better now?
    – Kristada673
    Dec 20 '18 at 8:06







  • 2




    Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
    – Zeta
    Dec 20 '18 at 8:10










  • Ok, got it. Replacing it now with your suggested title.
    – Kristada673
    Dec 20 '18 at 8:11















7














Given an input N as the size of a centrifuge, I need to find out the number of balanced configurations. The full description is here.




Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.



For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube k are $Rsin a, Rcos a$, where $a = 2pifrackn$



The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?



example 1: given N = 6 possible values for K are 2,3,4,6.



example 2: given N = 12, it is possible to balance 5 tubes: put 3 evenly dispersed (every 4th hole), then find a pair of opposite unoccupied holes and insert remaining 2 tubes there.



example 3: given N = 10, it is impossible to balance 7 tubes: put 5 evenly dispersed, and there's no opposite unoccupied holes left!



Input



Line 1: An integer N for the capacity of the centrifuge.



Output



Line 1: An integer M for the number of different possible values of K.




This is my code:



import numpy as np

N=int(input())
angle = 2*np.pi/N
z = complex(np.cos(angle), np.sin(angle))


import itertools
combs =
lst = range(1,N)
for i in range(2, N-1):
combs.append(i)
els = [list(x) for x in itertools.combinations(lst, i)]
combs.append(els)


count=1
lis =
while count<=len(combs):
for a in range(len(combs[count])):
s=0
for b in range(len(combs[count][a])):
s+=z**combs[count][a][b]
if abs(s)<1e-10:
lis.append(combs[count][a])
count+=2


lengths =
for i in lis:
if len(i) not in lengths:
lengths.append(len(i))

print(len(lengths)+1)


The code works fine, but slows down after input size of above 20, and is practically unusable after the input grows to 50 or above, due to the for loops. How do I optimize it?










share|improve this question























  • Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
    – Zeta
    Dec 20 '18 at 7:58










  • @Zeta Is it better now?
    – Kristada673
    Dec 20 '18 at 8:06







  • 2




    Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
    – Zeta
    Dec 20 '18 at 8:10










  • Ok, got it. Replacing it now with your suggested title.
    – Kristada673
    Dec 20 '18 at 8:11













7












7








7


2





Given an input N as the size of a centrifuge, I need to find out the number of balanced configurations. The full description is here.




Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.



For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube k are $Rsin a, Rcos a$, where $a = 2pifrackn$



The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?



example 1: given N = 6 possible values for K are 2,3,4,6.



example 2: given N = 12, it is possible to balance 5 tubes: put 3 evenly dispersed (every 4th hole), then find a pair of opposite unoccupied holes and insert remaining 2 tubes there.



example 3: given N = 10, it is impossible to balance 7 tubes: put 5 evenly dispersed, and there's no opposite unoccupied holes left!



Input



Line 1: An integer N for the capacity of the centrifuge.



Output



Line 1: An integer M for the number of different possible values of K.




This is my code:



import numpy as np

N=int(input())
angle = 2*np.pi/N
z = complex(np.cos(angle), np.sin(angle))


import itertools
combs =
lst = range(1,N)
for i in range(2, N-1):
combs.append(i)
els = [list(x) for x in itertools.combinations(lst, i)]
combs.append(els)


count=1
lis =
while count<=len(combs):
for a in range(len(combs[count])):
s=0
for b in range(len(combs[count][a])):
s+=z**combs[count][a][b]
if abs(s)<1e-10:
lis.append(combs[count][a])
count+=2


lengths =
for i in lis:
if len(i) not in lengths:
lengths.append(len(i))

print(len(lengths)+1)


The code works fine, but slows down after input size of above 20, and is practically unusable after the input grows to 50 or above, due to the for loops. How do I optimize it?










share|improve this question















Given an input N as the size of a centrifuge, I need to find out the number of balanced configurations. The full description is here.




Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.



For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube k are $Rsin a, Rcos a$, where $a = 2pifrackn$



The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?



example 1: given N = 6 possible values for K are 2,3,4,6.



example 2: given N = 12, it is possible to balance 5 tubes: put 3 evenly dispersed (every 4th hole), then find a pair of opposite unoccupied holes and insert remaining 2 tubes there.



example 3: given N = 10, it is impossible to balance 7 tubes: put 5 evenly dispersed, and there's no opposite unoccupied holes left!



Input



Line 1: An integer N for the capacity of the centrifuge.



Output



Line 1: An integer M for the number of different possible values of K.




This is my code:



import numpy as np

N=int(input())
angle = 2*np.pi/N
z = complex(np.cos(angle), np.sin(angle))


import itertools
combs =
lst = range(1,N)
for i in range(2, N-1):
combs.append(i)
els = [list(x) for x in itertools.combinations(lst, i)]
combs.append(els)


count=1
lis =
while count<=len(combs):
for a in range(len(combs[count])):
s=0
for b in range(len(combs[count][a])):
s+=z**combs[count][a][b]
if abs(s)<1e-10:
lis.append(combs[count][a])
count+=2


lengths =
for i in lis:
if len(i) not in lengths:
lengths.append(len(i))

print(len(lengths)+1)


The code works fine, but slows down after input size of above 20, and is practically unusable after the input grows to 50 or above, due to the for loops. How do I optimize it?







python python-3.x programming-challenge time-limit-exceeded mathematics






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 20 '18 at 15:28









200_success

128k15151413




128k15151413










asked Dec 20 '18 at 7:06









Kristada673

1363




1363











  • Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
    – Zeta
    Dec 20 '18 at 7:58










  • @Zeta Is it better now?
    – Kristada673
    Dec 20 '18 at 8:06







  • 2




    Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
    – Zeta
    Dec 20 '18 at 8:10










  • Ok, got it. Replacing it now with your suggested title.
    – Kristada673
    Dec 20 '18 at 8:11
















  • Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
    – Zeta
    Dec 20 '18 at 7:58










  • @Zeta Is it better now?
    – Kristada673
    Dec 20 '18 at 8:06







  • 2




    Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
    – Zeta
    Dec 20 '18 at 8:10










  • Ok, got it. Replacing it now with your suggested title.
    – Kristada673
    Dec 20 '18 at 8:11















Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
– Zeta
Dec 20 '18 at 7:58




Welcome to Code Review. The current question title, which states your concerns about the code, obfuscates the original intend of your code. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
– Zeta
Dec 20 '18 at 7:58












@Zeta Is it better now?
– Kristada673
Dec 20 '18 at 8:06





@Zeta Is it better now?
– Kristada673
Dec 20 '18 at 8:06





2




2




Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
– Zeta
Dec 20 '18 at 8:10




Now your title only states the concerns and wishes you have for your code. A better title would be something similar to "Balancing centrifuges" or "Balanced centrifuge configurations".
– Zeta
Dec 20 '18 at 8:10












Ok, got it. Replacing it now with your suggested title.
– Kristada673
Dec 20 '18 at 8:11




Ok, got it. Replacing it now with your suggested title.
– Kristada673
Dec 20 '18 at 8:11










2 Answers
2






active

oldest

votes


















7














This is not a review, but an extended comment.



The code cannot be meaningfully optimized. Few notes though.



  • First, thou shalt not bruteforce. It is almost inevitably wrong.


  • Next, you must realize that it is a number-theoretical problem. Even the names of the test cases suggest so. Among other things it means that testing the sum against 1e-10 is not right.


  • Finally, do watch the video referenced in the problem. It is a big spoiler, and it doesn't provide a proof of the claim. The proof is far from trivial; if you are interested in the proof, follow up with this is a fascinating reading (trigger warning: heavy-duty math).






share|improve this answer






















  • Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
    – Kristada673
    Dec 20 '18 at 9:18











  • @Kristada673 Sufficiently small for which Ns?
    – vnp
    Dec 20 '18 at 9:20










  • "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
    – LarsH
    Dec 20 '18 at 19:50


















6














There are two main problems:



  1. Enumerating all combinations, even those that are obviously unbalanced


  2. The use of floating point calculus in a combinatorics problem


Re-read the task carefully, especially examples 2 and 3, which hint a better algorithm:



  1. Factorize N. The factors of N=12 are [2,3], which tells us that all tubes are members of either a balanced pair or triplet.


  2. Find all combinations of factors that sum to K. For N=12, K=10, there are two solutions: 2+2+2+2+2=10 and 2+2+3+3=10.


  3. Find out if the solutions are valid. For N=10, K=7 the only solution is 2+5=7, which is not valid (see example 3).


For large values of K, balance holes instead of tubes. So N=12, K=10 is the same as N=12, K=2.






share|improve this answer






















    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    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: "196"
    ;
    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: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    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%2fcodereview.stackexchange.com%2fquestions%2f210025%2fbalanced-centrifuge-configurations%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    7














    This is not a review, but an extended comment.



    The code cannot be meaningfully optimized. Few notes though.



    • First, thou shalt not bruteforce. It is almost inevitably wrong.


    • Next, you must realize that it is a number-theoretical problem. Even the names of the test cases suggest so. Among other things it means that testing the sum against 1e-10 is not right.


    • Finally, do watch the video referenced in the problem. It is a big spoiler, and it doesn't provide a proof of the claim. The proof is far from trivial; if you are interested in the proof, follow up with this is a fascinating reading (trigger warning: heavy-duty math).






    share|improve this answer






















    • Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
      – Kristada673
      Dec 20 '18 at 9:18











    • @Kristada673 Sufficiently small for which Ns?
      – vnp
      Dec 20 '18 at 9:20










    • "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
      – LarsH
      Dec 20 '18 at 19:50















    7














    This is not a review, but an extended comment.



    The code cannot be meaningfully optimized. Few notes though.



    • First, thou shalt not bruteforce. It is almost inevitably wrong.


    • Next, you must realize that it is a number-theoretical problem. Even the names of the test cases suggest so. Among other things it means that testing the sum against 1e-10 is not right.


    • Finally, do watch the video referenced in the problem. It is a big spoiler, and it doesn't provide a proof of the claim. The proof is far from trivial; if you are interested in the proof, follow up with this is a fascinating reading (trigger warning: heavy-duty math).






    share|improve this answer






















    • Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
      – Kristada673
      Dec 20 '18 at 9:18











    • @Kristada673 Sufficiently small for which Ns?
      – vnp
      Dec 20 '18 at 9:20










    • "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
      – LarsH
      Dec 20 '18 at 19:50













    7












    7








    7






    This is not a review, but an extended comment.



    The code cannot be meaningfully optimized. Few notes though.



    • First, thou shalt not bruteforce. It is almost inevitably wrong.


    • Next, you must realize that it is a number-theoretical problem. Even the names of the test cases suggest so. Among other things it means that testing the sum against 1e-10 is not right.


    • Finally, do watch the video referenced in the problem. It is a big spoiler, and it doesn't provide a proof of the claim. The proof is far from trivial; if you are interested in the proof, follow up with this is a fascinating reading (trigger warning: heavy-duty math).






    share|improve this answer














    This is not a review, but an extended comment.



    The code cannot be meaningfully optimized. Few notes though.



    • First, thou shalt not bruteforce. It is almost inevitably wrong.


    • Next, you must realize that it is a number-theoretical problem. Even the names of the test cases suggest so. Among other things it means that testing the sum against 1e-10 is not right.


    • Finally, do watch the video referenced in the problem. It is a big spoiler, and it doesn't provide a proof of the claim. The proof is far from trivial; if you are interested in the proof, follow up with this is a fascinating reading (trigger warning: heavy-duty math).







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Dec 20 '18 at 9:18

























    answered Dec 20 '18 at 9:06









    vnp

    38.6k13097




    38.6k13097











    • Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
      – Kristada673
      Dec 20 '18 at 9:18











    • @Kristada673 Sufficiently small for which Ns?
      – vnp
      Dec 20 '18 at 9:20










    • "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
      – LarsH
      Dec 20 '18 at 19:50
















    • Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
      – Kristada673
      Dec 20 '18 at 9:18











    • @Kristada673 Sufficiently small for which Ns?
      – vnp
      Dec 20 '18 at 9:20










    • "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
      – LarsH
      Dec 20 '18 at 19:50















    Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
    – Kristada673
    Dec 20 '18 at 9:18





    Well, about the 1e-10, I used it because of the floating point error. So, I thought 1e-10 should be a sufficiently small difference between 0 and s to establish their equality (i.e., s=0).
    – Kristada673
    Dec 20 '18 at 9:18













    @Kristada673 Sufficiently small for which Ns?
    – vnp
    Dec 20 '18 at 9:20




    @Kristada673 Sufficiently small for which Ns?
    – vnp
    Dec 20 '18 at 9:20












    "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
    – LarsH
    Dec 20 '18 at 19:50




    "First, thou shalt not bruteforce. It is almost inevitably wrong." In what context? This is definitely not true in real life (wiki.c2.com/?PrematureOptimization), and often not true in coding challenges either. I was in a coding competition in college. Our team was doing practice problems, and I was working on an efficient way to solve the next one. My teammate beat me handily by using a much simpler, brute-force approach. It all depends on the size and complexity of the data and the algorithm. In this case, yes, brute-force is the wrong approach.
    – LarsH
    Dec 20 '18 at 19:50













    6














    There are two main problems:



    1. Enumerating all combinations, even those that are obviously unbalanced


    2. The use of floating point calculus in a combinatorics problem


    Re-read the task carefully, especially examples 2 and 3, which hint a better algorithm:



    1. Factorize N. The factors of N=12 are [2,3], which tells us that all tubes are members of either a balanced pair or triplet.


    2. Find all combinations of factors that sum to K. For N=12, K=10, there are two solutions: 2+2+2+2+2=10 and 2+2+3+3=10.


    3. Find out if the solutions are valid. For N=10, K=7 the only solution is 2+5=7, which is not valid (see example 3).


    For large values of K, balance holes instead of tubes. So N=12, K=10 is the same as N=12, K=2.






    share|improve this answer



























      6














      There are two main problems:



      1. Enumerating all combinations, even those that are obviously unbalanced


      2. The use of floating point calculus in a combinatorics problem


      Re-read the task carefully, especially examples 2 and 3, which hint a better algorithm:



      1. Factorize N. The factors of N=12 are [2,3], which tells us that all tubes are members of either a balanced pair or triplet.


      2. Find all combinations of factors that sum to K. For N=12, K=10, there are two solutions: 2+2+2+2+2=10 and 2+2+3+3=10.


      3. Find out if the solutions are valid. For N=10, K=7 the only solution is 2+5=7, which is not valid (see example 3).


      For large values of K, balance holes instead of tubes. So N=12, K=10 is the same as N=12, K=2.






      share|improve this answer

























        6












        6








        6






        There are two main problems:



        1. Enumerating all combinations, even those that are obviously unbalanced


        2. The use of floating point calculus in a combinatorics problem


        Re-read the task carefully, especially examples 2 and 3, which hint a better algorithm:



        1. Factorize N. The factors of N=12 are [2,3], which tells us that all tubes are members of either a balanced pair or triplet.


        2. Find all combinations of factors that sum to K. For N=12, K=10, there are two solutions: 2+2+2+2+2=10 and 2+2+3+3=10.


        3. Find out if the solutions are valid. For N=10, K=7 the only solution is 2+5=7, which is not valid (see example 3).


        For large values of K, balance holes instead of tubes. So N=12, K=10 is the same as N=12, K=2.






        share|improve this answer














        There are two main problems:



        1. Enumerating all combinations, even those that are obviously unbalanced


        2. The use of floating point calculus in a combinatorics problem


        Re-read the task carefully, especially examples 2 and 3, which hint a better algorithm:



        1. Factorize N. The factors of N=12 are [2,3], which tells us that all tubes are members of either a balanced pair or triplet.


        2. Find all combinations of factors that sum to K. For N=12, K=10, there are two solutions: 2+2+2+2+2=10 and 2+2+3+3=10.


        3. Find out if the solutions are valid. For N=10, K=7 the only solution is 2+5=7, which is not valid (see example 3).


        For large values of K, balance holes instead of tubes. So N=12, K=10 is the same as N=12, K=2.







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Dec 20 '18 at 9:27

























        answered Dec 20 '18 at 9:13









        Rainer P.

        1,166413




        1,166413



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Code Review Stack Exchange!


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

            Use MathJax to format equations. MathJax reference.


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





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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%2fcodereview.stackexchange.com%2fquestions%2f210025%2fbalanced-centrifuge-configurations%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






            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?