Problem: sum_41_ch2 (2023 round1)

*This problem shares some similarities with B1, with key differences in bold.*

Given a positive integer \(P\), please find an array of at most \(100\) positive integers which have a sum of \(41\) and a product of \(P\), or output \(-1\) if no such array exists.

If multiple such arrays exist, **print one with the fewest number of elements**. If there are multiple with the fewest number of elements, you may print any one of them.

# Constraints
\(1 \leq T \leq 960\)
\(1 \leq P \leq 10^9\)

# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is one line containing a single integer \(P\).

# Output Format

For the \(i\)th test case, if there is no such array, print "`Case #i: -1`". Otherwise, print "`Case #i:` " followed by the integer \(N\), the size of your array, followed by the array itself as \(N\) more space-separated positive integers.

# Sample Explanation
In the first sample, we must find an array with product \(2023\), and sum \(41\). One possible answer is \([7, 17, 17]\).



Sample input:
7
2023
114
41
175
434
666
1872


Sample output:
Case #1: 3 7 17 17
Case #2: 2 3 38
Case #3: 1 41
Case #4: 3 1 5 35
Case #5: 4 1 2 7 31
Case #6: -1
Case #7: 4 2 4 9 26


Solution: We can use a recursive backtracking algorithm to generate all possible values of \(f_{1..k}\). At each step, we consider every possible candidate of \(f_i \in [2, 41]\). Since \(f_i\) has to be a divisor of \(P\) within \([2,41]\), we can just precompute these. We start the backtracking with \(P\), and at each step, divide by each choice of \(f_i\) until either \(P\) becomes \(1\), or the sum of factors used so far exceeds \(41\).

Will this backtracking be efficient enough? First, note that the deepest we can go is \(k=20\) by choosing each \(f_i=2\) (since minimizing each factor maximizes the array length). This mean \(P \le 2^k \approx 10^6\). It's somewhat difficult to prove an upper bound on this recurrence, but intuitively, the larger the factor we pick at each step, the fewer remaining branching factors there will be. Emprically, the model solution passes the full test set in under \(10\) seconds on a modest system, taking no more than \(20\) million recursive steps on any test case.

Another approach is to enumerate all [partitions](https://en.wikipedia.org/wiki/Partition\_(number\_theory)) of \(41\), of which there are [under 45000](https://www.wolframalpha.com/input?i=number+of+partitions+of+41). There are many known [algorithms](https://code.activestate.com/recipes/218332/) to do so, taking linear or constant steps per partition. Even exponential ones will likely work in our submission window. After generating each partition of size \(k\), we can check whether the product equals \(P\) in \(\mathcal{O}(k)\), for an overall time complexity of \(\mathcal{O}(45000*k)\).


Code: #include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int curr_sum, best_len;
vector<int> divisors, curr, best_ans;

int maxsteps = 0;
int steps = 0;

void rec(int P) {
  steps++;
  if (P == 1) {
    int len = curr.size() + (41 - curr_sum);
    if (len < best_len) {
      best_len = len;
      best_ans = curr;
    }
    return;
  }
  for (int d : divisors) {
    if (P % d == 0 && curr_sum + d <= 41) {
      curr.push_back(d);
      curr_sum += d;
      rec(P / d);
      curr_sum -= d;
      curr.pop_back();
    }
  }
}

void solve() {
  int P;
  cin >> P;
  if (P == 1) {
    best_ans.assign(41, 1);
  } else {
    divisors.clear();
    // Precompute all divisors.
    for (int i = 2; i <= 41; i++) {
      if (P % i == 0) {
        divisors.push_back(i);
      }
    }
    curr.clear();
    steps = 0;
    curr_sum = 0;
    best_ans.clear();
    best_len = (int)1e9;
    rec(P);
    if (steps > maxsteps) {
      maxsteps = steps;
      cerr << P << endl;
    }
  }
  if (!best_ans.empty()) {
    int best_sum = accumulate(best_ans.begin(), best_ans.end(), 0);
    for (; best_sum < 41; best_sum++) {
      best_ans.push_back(1);
    }
    cout << " " << best_ans.size();
    for (int f : best_ans) {
      cout << " " << f;
    }
  } else {
    cout << " -1";
  }
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ":";
    solve();
    cout << endl;
  }
  cerr << maxsteps;
  return 0;
}