CodeJam 2021: Prime Time

I enjoyed trying the problem Prime Time from CodeJam 2021 and wanted to share my approach. Here is the problem statement.

You are given primes $p_1 \leq p_2 \leq ... \leq p_N$. A partition of the cards into two disjoint sets $S$ and $P$ is called good iff 

$$\sum_{p\in S}{p} = \prod_{p\in P}{p}$$

The score of a good partition is defined as the sum of the primes in $S$ (which is equal to the product of the primes in $P$) . What is your maximum possible score?

We are given three test sets:

• Test set $1$: $2\leq N\leq10$
• Test set $2$: $2\leq N\leq100$
• Test set $3$: $2\leq N\leq10^{15}$

Notation: Let $\text{sum}(S)=\sum_{p\in S}{p}$ and $\text{prod}(P)=\prod_{p\in P}{p}$.

Initial Observations:

1. We can pass test set $1$ using the brute-force approach requiring $O(N\cdot2^N)$ time: $2^N$ possible partitions, each needing $O(N)$ time to verify goodness.
2. Since each prime is at most $499$, we have the upper bound $\text{sum}(S)<499N$.
3. Since multiplication grows much faster than addition, it makes sense for $|P|\ll|S|$. We know, $2^{|P|} < 499N$, hence $|P| < \log_{2}{499N}$.
4. From $(3)$, for test set $2$, we have $|P|<16$.
5. From $(3)$, for test set $3$, we have $|P|<55$.
6. From the fundamental theorem of arithmetic we know for each set $P\subseteq\{p_1, p_2, ..., p_N\}$, $\text{prod}(P)$ is each time a unique number.

From $(2)$, we know that $\text{prod}(P)$ can take at most $499N$ distinct values, where each value maps to a unique set $P$. 

Fix the value of $\text{prod}(P)$ to some $2\leq x\leq499N$, and suppose we have its prime factorization $x=p_1^{k_1}p_2^{k_2}...p_N^{k_N}$. It is only possible to achieve $x$ with $P$ if we have at least $k_i$ instances of $p_i$. If $x$ is possible, then we check in $O(N)$ if the remaining primes sum to $x$.

This approach takes time $O(499N\cdot T(499N) \cdot N)$ where $T(x)$ is the time needed to compute the prime factorization of $x$.

It is known that $T(x) \in O(\sqrt{x})$. However, we only need to check for prime factors of $x$ up to $499$ since $p_i \leq 499$. So we have $T(x) = O(1)$ meaning our solution takes time $O(499N^2)$.

This solves test set $2$. However, this is as far as I got. It seems as though $(5)$ was not used and I feel like it could be very useful to make my solution more efficient for test set $3$.