Project Euler #190: Maximising a weighted product

Sort by

recency

|

9 Discussions

|

  • + 0 comments

    pffffffFFT ! I would think this should be classified as advanced if not expert in order to be consistent with other expert level problems requiring similar techniques.

  • + 1 comment

    It seems the crux of the problem is calculating .

    Letting there is the relation and hence the problem yields to dynamic programming where a buffer can be used to update . However it seems that even this is not fast enough so I think there is another trick that is missing. Any hints?

    Tricks I already used

    • raising to a power by breaking up the exponent into powers of 2 and repeated squaring
    • for prime
    • + 0 comments

      We have the composition of into parts with parts in :

      and the sum

      A member of the composition set can be viewed as the result of filling the intermediate gaps ("")

      with either a "" or a separating "" symbol. We have separators to place, which gives possibilities.

      Having a composition of into parts with parts in we could extend it by adding as new component.

      If we do this for we should have .

      This leads to

      where

  • + 1 comment

    X, A and m:
    x_1 + x_2 + .. + x_m = X
    a_1 + a_2 + .. + a_m = A
    For a given (a_1, a_2, .. a_m), to maximize x_1^a_1 * x_2^a_2 * ... * x_m^a_m, which is Qm(X, (a_1, a_2, .. a_m)).

    Question:
    When trying to find Qm(X, (a_1, a_2, .. a_m)), is there an existing formula to get Qm(X, (a_1, a_2, .. a_m)), or we need to calculate x_1^a_1 * x_2^a_2 * ... * x_m^a_m for all (x_1, x_2, .. x_m) combinations?

    • + 1 comment

      Hint: What values can the vectors take?

      • + 2 comments

        Pretty much unlimited.

        So what mathematics theorem applies here?

        • + 2 comments

          Given through , optimal values for through can be found in closed form via Lagrange multiplier method https://en.wikipedia.org/wiki/Lagrange_multiplier

          You can find that at optimality, and therefore the optimal value

  • + 2 comments

    I am stuck at 38/100. Two tests keep timing out. The unsuccessful test cases switch around between "wrong answer" and "runtime error", depending on my various attempts to optimize.

    My correct test cases seem to finish fast (around 0.2s), while the wrong ones seem slower (around 7s). This could point to some error when the calculations involve more steps.

    I am starting to suspect that the recognition of runtime errors is not working correctly. So the wrong answers might be actually resource exhaustions.

    Some results for comparison:

    X A m -> sum Q (mod 10^9+7)
    6 4 2 -> 375000357
    6 5 2 -> 214721813
    6 6 2 -> 9027
    7 5 3 -> 886720700
    7 6 3 -> 834194410
    7 7 3 -> 19002
    
    • + 1 comment

      I get the same results for these test cases

      • + 1 comment

        I come up with a solution which only passed few test cases.

        For this test case:
        X A m -> sum Q (mod 10^9+7)
        6 4 2 -> 375000357

        The reasult I got is 354, the process to get this number is:
        For all , we have as:
        (1, 3)
        (2, 2)
        (3, 1)

        According to maximizes , we can get:


        To sum them up I got 354.375, so the output is 354.

        Is there anything wrong here?

        • + 1 comment

          The modular calculation should always stay in the integer world and not introduce floating point numbers. To divide a integer, say 2 in this case, you should first compute its modular inverse, i.e. 500000004 (because 2 * 500000004 % 1000000007 = 1), and then convert division to modular multiplication. The expected result in this case: Q2(6,(1,3)) = 187500138, Q2(6,(2,2)) = 81, Q3(6,(3,1)) = 187500138

  • + 1 comment

    What is the significance of X?

    • + 0 comments

      The numbers x_1, ..., x_m must sum to X