Submission #622473

#	Time	Username	Problem	Language	Result	Execution time	Memory
622473		jophyyjh	Lottery (CEOI18_lot)	C++14	100 / 100	1110 ms	8708 KiB

lot

/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like a dp, and the score distribution is interesting too.. Sort the machines
 * and orders by their clock speed. By greedy arguments, if we've seletected the
 * subset of orders & machines, we sort the clock speed in order and assign them.
 * [S3] is the one that gave me the idea: we first sort orders & machines, then use
 * O(nm) dp on prefixes. Note that cores can be shared across orders, so we need an
 * additional val in our dp state, which is the num of cores left. This val can at
 * most be 50. Note that one should take a close look at the memory limit too: our dp
 * sequence shouldn't take up too much memory.
 * 
 * P.S. When about 1.5 hours were left, I left home. Technically I didn't finish the
 *      virtual contest.
 * 
 * ------ B ------
 * I think i've seen sth similar on luogu. First, let's assume that d >= 0 and i'll
 * use the words "increase" & "decrease". If we wanna increase an interval by d, we
 * can greedily increase a suffix (instead of just an interval in the middle). If we
 * are to decrease an interval by d, we can greedily decrease a prefix. The two cases
 * are symmetric, so we can assume that one always increase a suffix by 0 <= d <= x.
 * And, if we're increasing a suffix, why don't we just do d=x? The rest is quite
 * straight-forward.
 * 
 * ------ C ------
 * For k_j = 0, we have to find the num of times each interval appeared. This can be
 * effectively done with str hashing. [S3] solved. [S1] is just brute-force: we can
 * do a O(n^2) for loop, iterating over all pairs of starting pos, naively comparing
 * the dist. of 2 substr. [S2] is a O(n^2) comparison between pairs of VALUES and
 * apply a difference array.
 * We're only looking for the num of mismatches. Let's compress the values (a_i:
 * 10^9 -> 10^4).
 * [After contest]
 * I was so shocked after reading the solution. (Most people thought it was the
 * easiest problem, yet it was the only problem on the 1st day that i couldn't finish
 * myself!) Anyway, let dist[i][j] = dist. between the substr starting at i and the
 * one starting at j. It turns out that a O(n^2) (time comp.) solution can pass! But
 * we must optimize memory usage (O(n^2) memory is too much). The key is to not store
 * dist[][].
 * I computed dist[i][j] by iterating through j-i (from small to large). One may find
 * that a lot of comparisons can be removed, e.g. we have:
 *                  dist[i+1][j+1] = dist[i][j] + (sth) - (sth).
 * Each time, a row of dist[][] is maintained, so we can answer all queries related
 * to that pos. The impl looks kinda neat too~
 * 
 * PS1  Sadly, CSES didn't let me pass impl2 since the last few testcases TLEd. I
 *      then optimized the condition of my for loops to speed it up. I believe that
 *      on oj.uz impl2 would already be enough~ The slight downside is that the
 *      starting points & endpoing
 * 
 * Time Complexity 1: O(nm * c_max + n * log(n) + m * log(m))
 * Time Complexity 2: O(n * log(n))
 * Time Complexity 3: O(n^2 + qn)
 * Mem. Compleixty 3: O(nq)
 * Implementation 2.1           (Full solution, memory optimized)
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int>    vec;
 
const int INF = 0x3f3f3f3f;
 
 
struct query_t {
    int q, original_idx;
};
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int n, l, q;
    std::cin >> n >> l;
    vec values(n);
    for (int_t k = 0; k < n; k++)
        std::cin >> values[k];
    std::cin >> q;
    vec queries(q);
    for (int_t i = 0; i < q; i++)
        std::cin >> queries[i];
 
 
    std::vector<vec> ans(n, vec(q));
    // Some 0s in dist[] isn't valid. This is because they don't repr real substrs.
    // But anyway, they may become "real" with other pos k, so we keep those as 
    // "partial comparisons".
    vec dist(2 * n - 1, 0);
    // compare substr starting at 0 at 0+k, skip out of bound positions.
    for (int k = -n + 1; k <= n - 1; k++) {
        for (int i = std::max(-k, 0); i < std::min(n - k, l); i++)
            dist[k + (n - 1)] += (values[i] != values[i + k]);
    }
    for (int k = 0; k + l <= n; k++) {
        // ans query for pos k
        vec prefix_sum(l + 1, 0);
        for (int i = -k; i < n - (l - 1) - k; i++)
            prefix_sum[dist[i + (n - 1)]]++;
        for (int t = 1; t <= l; t++)
            prefix_sum[t] += prefix_sum[t - 1];
        for (int i = 0; i < q; i++)
            ans[k][i] = prefix_sum[queries[i]] - 1;
        // re-calculate dist[] for the next k
        if (k + l < n) {
            // dist_new[i] = dist[i] + (values[k+i+l] != values[k+l])
            //                        - (values[k+i] != values[k])
            for (int i = -(k + l); i < n - l - k; i++)
                dist[i + (n - 1)] += (values[k + i + l] != values[k + l]);
            for (int i = -k; i < n - k; i++)
                dist[i + (n - 1)] -= (values[k + i] != values[k]);
        }
    }
    for (int i = 0; i < q; i++) {
        for (int j = 0; j + l <= n; j++)
            std::cout << ans[j][i] << ' ';
        std::cout << '\n';
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20