SSL-OI Summer Camp 2020.08.18

Today, all the big shots went to participate in the NOI online synchronous competition, and I was the only one who didn't sign up QwQ.

So there was only one division, and the problems seemed pretty easy. (Not really)

Then I got completely crushed by a first-year middle school student /doge

T1 Dividing Ham

Problem

Given $n$ hams, they need to be cut into $m$ equal-sized portions. Find the minimum number of cuts.

Story

Obviously this is a water problem for elementary school students. For each $(n,m)$ hams, we can save one cut. So just output $(m-1)-((n,m)-1)$, which is $m-(n,m)$.

#include <stdio.h>

int T;

int gcd(int a, int b) { return (b == 0) ? (a) : gcd(b, a % b); }

signed main() {
    freopen("A.in", "r", stdin);

    scanf("%d", &T);

    for (int i, n, m; T-- > 0;)
        scanf("%d%d", &n, &m), printf("%d\n", m - gcd(n, m));

    return 0;
}

Actually, this is also the correct solution.

T2 Salary

Problem

Given an array $arr$, divide it into at most $m$ blocks. Sum each block, and minimize the maximum sum.

Story

I didn't know how to do T2 QwQ.

Problems of minimizing the maximum value are usually solved with binary search on the answer, right? So for the maximum value $lim$ from binary search, greedily traverse $arr$, and start a new segment once the sum exceeds $lim$. I always feel something is off with the greedy approach, but I can't prove it, nor think of a better method.

#define MXN (100020)

#include <stdio.h>

#include <algorithm>

int n, m;
long long a[MXN];

int check(int lim) {
    int res = 0, cnt = 0;
    for (int i = 0; i < n; ++i)
        if ((cnt += a[i]) > lim)
            cnt = a[i], ++res;
        else if (cnt == lim)
            cnt = 0, ++res;
    return res + (cnt > 0);
}

long long l, r = MXN * MXN, md;

signed main() {
    freopen("B.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &a[i]), l = std::max(l, a[i]);

    while (l < r) {
        if (check(md = (l + r) / 2) <= m)
            r = md;
        else
            l = md + 1;
    }

    printf("%d", r);

    return 0;
}

Result WA90? Weird. After slightly modifying the greedy function, it passed.

I'll study why the greedy is correct later.

T3 Annoying CD

Problem

Given $n$ numbers, choose $k$ of them to maximize their $gcd$.

Story

I had no idea how to do T3 at all, and felt the problem statement was a bit strange? So there's no story...

Correct Solution

It seems it was indeed a problem with reading the statement; if I read it a few more times, I might understand it. As expected, this problem is also very easy.

We create an array of size $500000$ to record the frequency of each value. Then enumerate the answer $ans$ from largest to smallest, and count the sum of frequencies of all its multiples; if it's greater than or equal to $k$, that's the answer. Yes, the correct solution is very brute-force.

The complexity is $O(\sum_{i=1}^{N}\frac{i}{N})$, which is roughly $O(N\log{N})$. (I don't know why either)

#define MXN (500020)

#include <stdio.h>

#include <algorithm>

int n, k, top;
int cnt[MXN];
long long ans;

signed main() {
    freopen("C.in", "r", stdin);

    scanf("%d%d", &n, &k);

    for (int i = 0, x; i < n; ++i)
        scanf("%d", &x), ++cnt[x], top = std::max(top, x);

    for (int i = top, j, res; i > 0; --i) {
        for (j = i, res = 0; j <= top; j += i)
            res += cnt[j];
        if (res >= k) {
            ans = i;
            break;
        }
    }

    printf("%lld", ans * k);

    return 0;
}

I finished correcting all the problems by noon; today's problems were indeed easy.

In the afternoon, I'll correct yesterday's problems.

Then take a look at the NOI they're participating in today?