P1120 Small Wooden Sticks

Understanding the Problem

P1120 Small Wooden Sticks - Luogu | New Ecology of Computer Science Education (luogu.com.cn)

Given $n$ small wooden sticks with lengths $a_i$ , satisfying $1 \leq a_{i} \leq 50$ , $n \leq 650$ , they can be arbitrarily joined together. The goal is to make all joined sticks have the same length, and we need to find the minimum possible value of that equal length.

For example:

1
2

9
5 2 1 5 2 1 5 2 1

The minimum length here is 6, formed by three 5 1 combinations and one 2 2 2 combination.

The problem is labeled as a search problem.

Approach

This problem looks simple and easy to understand, but it’s actually quite tricky to implement. I initially refused to believe it and tried a greedy approach, but that didn’t work, so I had to go back and write a proper search.

First, let’s analyze the hidden mathematical properties: the number of final equal-length sticks is bounded between 1 and n, so the possible stick lengths are actually limited. It’s easy to see that: the total sum of all stick lengths, sum, must be divisible by the target length, and this length must be ≥ the maximum value among the stick lengths $a_i$ .

Therefore, we can first compute all possible candidate answers, then try them in increasing order to see if they can be formed.

As for how to determine whether a length can be formed, my initial greedy idea was to treat the process as “filling”: a stick is considered complete when it’s exactly filled. Each time, start by picking the largest stick that fits into the remaining space. If everything fills up successfully, the condition is satisfied, and we can stop and return this length as the minimum. If no remaining stick can fit, it means this length doesn’t work, and we move on to the next candidate.

However, this greedy algorithm has a flaw: a case that seems impossible might actually have a valid solution.

Counterexample: 3 4 7 8 18 20

Greedy gets 45 points

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
82

#include <bits/stdc++.h>

using namespace std;

int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int bucket[51]{0};  // 统计每个长度的个数
int n;
int sum = 0;

bool is_valid(int p)
{
    cout << p << endl;
    int bucket_copy[51]{0};
    for (int i = 0; i <= max_num; i++)
    {
        bucket_copy[i] = bucket[i];
    }

    for (int i = 0; i < sum / p; i++)
    {
        int max_num_copy = max_num;
        int pp = p;
        while (pp > 0)
        {
            if (bucket_copy[max_num_copy] == 0 ||
                max_num_copy > pp)  // 查找最低能被减的值
            {
                do
                {
                    if (max_num_copy == 0)
                    {
                        cout << "FAILED\n";
                        return false;
                    }
                    max_num_copy--;
                } while (bucket_copy[max_num_copy] == 0 || max_num_copy > pp);
            }
            pp -= max_num_copy;
            bucket_copy[max_num_copy]--;
            cout << max_num_copy << '\n';
        }
    }
    return true;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int ai;
        cin >> ai;
        max_num = max(ai, max_num);
        sum += ai;
        bucket[ai]++;
    }

    // 对sum求因子
    for (int i = max_num; i <= sum; i++)
    {
        if (sum % i == 0)  // 整除
        {
            fac[fac_cnt++] = i;
        }
    }

    for (int i = 0; i < fac_cnt - 1; i++)
    {
        if (is_valid(fac[i]))
        {
            cout << fac[i] << endl;
            system("pause");
            exit(0);
        }
    }
    cout << sum << endl;  // 都不满足则是sum

    system("pause");
    return 0;
}

So I ended up writing a proper search. The search logic isn’t that hard — I used DFS. Each time we form a stick, we loop from the longest to the shortest stick to pick a suitable one, then move to the next state. If all stick lengths have been tried and none work, return false; if all sticks are fully assembled, return true.

The real challenge is pruning the search. Pruning means: when we can already determine the outcome in a certain state, stop recursing and immediately return.

First, we need to understand a key insight: if we need a certain length, say 5, and we still have 2 and 3 available, choosing 5 can be seen as the “superior” choice over choosing 2 and 3, because 2 and 3 together can fully replace 5, but not the other way around. So we should prioritize choosing 5 first, and only later try 2 and 3. This is why we search from larger to smaller.

Here are the most critical optimizations, as for the other trivial ones, 😂👉🤡:

1. Use a bucket (frequency array) to store stick lengths. The advantage is that it lets us retrieve sticks in descending order while also acting as a vis array, “recording” which lengths have already been visited.
2. When searching for an available stick, continue from where the last search left off, rather than starting from the beginning. This is because if a longer stick than the previous one works, it should be preferred — so we shouldn’t go back to smaller sticks.
3. If the remaining length equals the current stick’s length, but filling it in returns false, break out of the loop immediately and mark this branch as false. This is because it’s already the optimal choice — if using a smaller stick to fill this length would definitely be worse.
4. If nothing has been filled yet and it fails, also return false directly. The reasoning is the same as above: if the optimal filling method can’t succeed, worse ones certainly can’t either.

Honestly, optimizations 3 and 4 are quite hard to come up with. Without reading the top solutions, I probably wouldn’t have figured them out. At the time, my best attempt only scored around 50 points. I still have a lot to learn from the experts.

AC Code

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <bits/stdc++.h>

using namespace std;

int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int min_num = 100;
int bucket[51]{0};  // 统计每个长度的个数
int n;
int sum = 0;
int current_fac;
int filled_bucket[50]{0};
int filled_bucket_cnt = 0;

bool dfs(int l, int x, int idx)
{
    // l是当次剩余的长度，x是次数，idx是上次搜到的索引
    if (l == 0)
    {
        if (x == 2)  // 剩一个一定可以拼
        {
            return true;
        }
        else
        {
            return dfs(current_fac, x - 1, 0);
        }
    }

    if (l < min_num)  // 剩下的比最小长度还小
    {
        return false;
    }

    for (int i = idx; i < filled_bucket_cnt; i++)
    {
        if (bucket[filled_bucket[i]] > 0)
        {
            bucket[filled_bucket[i]]--;
            if (dfs(l - filled_bucket[i], x, i))
            {
                // cout << i << '\n';
                bucket[filled_bucket[i]]++;
                return true;
            }
            else if (l == current_fac || l == filled_bucket[i])
            {
                bucket[filled_bucket[i]]++;
                return false;
            }

            bucket[filled_bucket[i]]++;
        }
    }
    return false;
}

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int ai;
        cin >> ai;
        max_num = max(ai, max_num);
        min_num = min(ai, min_num);
        sum += ai;
        if (bucket[ai] == 0)
        {
            filled_bucket[filled_bucket_cnt++] = ai;
        }
        bucket[ai]++;
    }

    sort(filled_bucket, filled_bucket + filled_bucket_cnt, cmp);

    // 对sum求因子
    for (int i = max_num; i <= sum; i++)
    {
        if (sum % i == 0)  // 整除
        {
            fac[fac_cnt++] = i;
        }
    }

    for (int i = 0; i < fac_cnt - 1; i++)
    {
        current_fac = fac[i];
        if (dfs(fac[i], sum / fac[i], 0))
        {
            cout << fac[i] << endl;
            exit(0);
        }
    }
    cout << sum << endl;  // 前几个都不满足则是sum

    return 0;
}