- A+

Category：Languages

There are three integers `x`

, `y`

and `z`

(each of them >= 1) and a given upper bound integer `n`

< 10^6. Also, `n = x + y + z`

and `output = cos(x) + cos(y) + cos(z)`

.

The exercise is to maximize `output`

.

I wrote a simple script for this, but the time complexity is O(n^3). Is there any way to simplify this?

`from math import cos n = 50 x = 1 y = 1 z = 1 total = cos(x) + cos(y) + cos(z) for x in xrange(n): for y in xrange(n): for z in xrange(n): if x + y + z == n: temp = cos(x) + cos(y) + cos(z) if temp > total: total = temp print round(total, 9) `

As pointed out by Jean-François Fabre in the comments, there are plenty of tricks you could apply to improve performance, but by first of all

- noting that the values of
`a`

and`b`

determine the value of`c`

, - noting that at least one of the three variables, WLOG
`a`

, is less than or equal to`N/3`

, - using the remaining symmetry in
`b`

and`c`

to bound`b`

between 1 and`(N - a)//2 + 1`

- precomputing all relevant values of cos,
- using Numba to JIT-compile the code and get some performance for free (about a factor of 400 for
`N = 500`

),

then the otherwise bruteforcy solution terminates relatively quickly for `N = 1000000`

(thus also for any given `N < 1000000`

):

`import numpy as np from numba import jit @jit def maximize(N): cos = np.cos(np.arange(N)) m = -3 for a in range(1, N//3 + 1): for b in range(1, (N - a)//2 + 1): c = N - a - b res = cos[a] + cos[b] + cos[c] if res > m: m = res bestabc = (a, b, c) return m, bestabc maximize(1000000) # (2.9787165245899025, (159775, 263768, 576457)) `