PAT Advanced 1103 Integer Factorization

Overview

PAT advanced 1103 Integer Factorization, use backtracking (dfs) to search the solution space, with pruning and sorting to optimize the performance.

PAT Advenced 1103 Integer Factorization Problem

The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (<=400), K (<=N) and P (1<P<=7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:

N = n1^P + … nK^P

where ni (i=1, … K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122 + 42 + 22 + 22 + 12, or 112 + 62 + 22 + 22 + 22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a1, a2, … aK } is said to be larger than { b1, b2, … bK } if there exists 1<=L<=K such that ai=bi for ibL

If there is no solution, simple output “Impossible”.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

PAT Advenced 1103 Integer Factorization Algorithm

Use backtracking/dfs to search the solution space, while enumerating, try all the possible solutions in decending order, and if there is multiple solutions, check the sum over the factors, pick the one with the maxium sum as required by the problem definition. I use an explicit array to keep the partial sum of n1^P + … ni^P where i < K to optimize the performance further, otherwise the speical case of test data case 5 will be TLE, with my optimization, I can pass this case 5 with about 900 ms. The following source code is accepted by the PAT OJ to pass this Integer Factorization problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>

using std::vector;
using std::min;
using std::sqrt;
using std::pow;

vector<int> ans;
vector<int> sol;
vector<int> tmp; 
int maxS;

int accumulate(int pos, int p) {
    tmp[pos] = tmp[pos - 1] + pow(sol[pos-1], p);
    return tmp[pos];
}

bool accept(int n, int k, int p) {
    return n == (tmp[k - 1] + pow(sol[k-1], p));
}

void gao(int n, int k, int p, int pos) {
    if (k == pos) {
        if(accept(n, k, p)) {
            int s = std::accumulate(sol.begin(), sol.end(), 0);
            if (s > maxS) {
                ans= sol;
                maxS = s;
            }
        }
        return ;
    }

    int r = n - accumulate(pos, p);
    if (r <= 0) {
        return ;
    }

    int c = (int) sqrt(r);
    if (pos > 0) {
        c = min(c, sol[pos-1]);
    }

    for (int i = c; i >= 1; --i) {
        sol[pos] = i;
        gao(n, k, p, pos+1);
    }
}


void print(const vector<int> &ans, int n, int k, int p) {
    printf("%d = %d^%d", n, ans[0], p);

    for (int i = 1; i < k; ++i) {
        printf(" + %d^%d", ans[i], p);
    }
    printf("\n");
}

int main() {
    int n, k, p;
    scanf("%d %d %d", &n, &k, &p);

    maxS = INT_MIN;
    sol.resize(k);
    tmp.resize(k + 1);
    tmp[0] = 0;
    gao(n, k, p, 0);

    if (ans.empty()) {
        printf("Impossible");
    } else {
        print(ans, n, k, p);
    }

    return 0;
}

PAT Advenced 1103 Integer Factorization Test Cases

Be careful about the test case 5 which is the worst case test, it is the easiest one that can be TLE, my testing results:

0	答案正确	1	308	15/15
1	答案正确	1	316	2/2
2	答案正确	1	256	5/5
3	答案正确	1	304	1/1
4	答案正确	1	256	1/1
5	答案正确	933	316	3/3
6	答案正确	1	256	2/2
7	答案正确	1	256	1/1

Summary

PAT advanced 1103 Integer Factorization, use backtracking (dfs) to search the solution space, with pruning and sorting to optimize the performance.

Written on March 31, 2016