SSL-OI Summer Camp 2020.08.23 Group A

Today's problems were a bit easy, probably because it's the last day and AJ wanted to give us a break. The first three problems were directly taken by AJ from Zhongshan City Selection 2012, and the fourth was an additional problem chosen by Bei Ye. (But I didn't write it) C failed, ending with 100+80+0+0=180 Then in the afternoon, I activated the senior-exclusive skill: fast review, fast off work.

A Is this a tree?

Problem

Given the degrees of n points in a graph, determine if it could be a tree.

Story

Super easy problem. Obviously, a tree has n-1 edges, and each edge added increases the total degree sum by 2. Check if the degree sum is 2n-2, and if n>2, no point's degree can be 0.

#include <stdio.h>

long long n, s;
bool pos = true;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%lld", &n);
    for (long long i = 0, a; i < n; ++i)
        scanf("%lld", &a), pos &= (a > 0), s += a;

    if (s == (n - 1) * 2 && (n == 1 || pos))
        printf("Possible");
    else
        printf("Impossible");

    return 0;
}

B Selection and Arrangement

Problem

Given n numbers, select R groups, each with C numbers. The contribution of each group is the maximum minus the minimum. Find the minimum possible maximum contribution among these R groups.

Story

As the saying goes: those who are not greedy will not be greedy in competitions.

Why do I always doubt the correctness of greedy algorithms? Is it because of an inexplicable fear of things that cannot be proven?

In the end, I wrote an O(n^2) brute force, and because the data is old, I got 80? (This time I didn't add data range checks outside the brute force)

An obvious conclusion: the numbers selected each time are a contiguous segment in the sorted array. If two groups' intervals overlap, we can always swap elements to improve the maximum/minimum.

Let f_{i,j} be the minimum possible maximum contribution when selecting i groups and reaching the j-th number. The transition is:

$$f_{i,j}=min_{k=0}^{k \leq j-C}f_{i-1,k} \ + \ P_j - P_{j-C}$$

#define MXN (500020)

#include <stdio.h>
#include <string.h>

#include <algorithm>

int N, R, C;
int P[MXN];

// Sub1
int a[MXN], f[1024][1024], min, ans = 1e9;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
#endif

    scanf("%d%d%d", &N, &R, &C);
    for (int i = 0; i < N; ++i)
        scanf("%d", &P[i]);

    std::sort(P, P + N);

    for (int i = C - 1; i < N; ++i)
        a[i] = P[i] - P[i - C + 1];

    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i <= N; ++i)
        f[0][i] = 0;
    for (int i = 1, j; i <= R; ++i)
        for (min = 1e9, j = C - 1; j < N; ++j)
            f[i][j] = std::max(min = std::min(min, f[i - 1][j - C]), a[j]);
    for (int i = 0; i < N; ++i)
        ans = std::min(ans, f[R][i]);

    printf("%d", ans);

    return 0;
}

Solution

Binary search the answer + greedy check. Almost the same as the B problem from a few days ago, and I almost didn't know how to do it either.

We binary search the maximum sum for each group, then greedily select as many groups as possible.

C Picking Gold

Didn't think it through during the exam, failed.

Problem

The problem statement doesn't mention Trie, but it's obviously a Trie.

Given M strings, each string increments the weight of its nodes on the Trie. Select n disjoint chains on the Trie, and find the maximum total weight.

M ≤ 50000, N ≤ 10

Solution

The story is that the correct solution failed, so the title stubbornly says solution.

For each node, let f_i be the maximum total weight when selecting i chains in its subtree. Consider merging a subtree S into its parent: we enumerate the parent's f_i to be updated from large to small, then enumerate j ∈ (0,i], and try to update the parent's f_i with f_j + S->f_{i-j}. Finally, connect the parent node into a chain and directly add its weight to f_i. (i ∈ [1,N])

D Magic (Additional Problem)

One hour after the start, this sentence appeared in the problem description:

Since today's problems are too easy, we now prepare an additional problem for students who have AK'd or are about to AK. It is recommended to do this after completing all previous problems. It's not very hard, please enjoy.

Z Ye disdained problems A and B, and directly solved C and D QwQ. I only managed A, B, and C, and ended up at Rank 10.

Rambling

I didn't read the problem carefully, but it's probably about generating edge weights in a special way and finding single-source shortest paths.