We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #190: Maximising a weighted product
Project Euler #190: Maximising a weighted product
Sort by
recency
|
9 Discussions
|
Please Login in order to post a comment
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.
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
We have the composition of into parts with parts in :
A member of the composition set can be viewed as the result of filling the intermediate gaps ("")
Having a composition of into parts with parts in we could extend it by adding as new component.
This leads to
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?
Hint: What values can the vectors take?
Pretty much unlimited.
So what mathematics theorem applies here?
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
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:
I get the same results for these test cases
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?
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
What is the significance of X?
The numbers x_1, ..., x_m must sum to X