Some progress for the future me:
- The problem can be reduced to a Combination Sum problem. In particular, we can generate the range of possible primes as the sum of the array (range can be from
ord(a) * <some_value>
toord(z)
* 1020). We can use a DP approach to solve this as we have a lot of incremental sum, however, storage might be an issue. Some trimming can be done to ensure the solution does not exceed the length - How the
array.prod()
fornumpy
works is that it wraps around 64-bit value (Mac/Linux behavior). In particular, the following snippet of code should help you understand what’s going on. Basically the result is modulo $2 ^ 64$. The negative sign can be obtained from casting aunsigned long long
to asigned long long
easily in C.
|
|
- Solution should be in C to enable quick brute forcing. An idea can be to initialize the first characters that must be in the candidate string, e.g
1aA
and try to find a combination that satisfies thearray.sum() == array.prod()
.