Submission #623433

#	Time	Username	Problem	Language	Result	Execution time	Memory
623433		jophyyjh	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	713 ms	84984 KiB

tickets

/**
 * Another problem from tinjyu's training, though we didn't directly go through the
 * full solution. The "minimum sum of dist. to a point" is classic; we know that
 * point b is the median, i.e. any val in [(n/2)-th_num, #(n/2+1)-th_num]. The obs.
 * here is that the actual val we take is irrelevant. Since n is even, the val would
 * be cancelled out so the 
 * prize = #sum_of_the_(n/2)_larger_num - #sum_of_the_(n/2)_smaller_num.
 * 
 * This means in each round, we maximize #sum_of_(n/2)_num - #sum_of_remaining
 * because this naturally finds the larger n numbers to minus the n smaller ones
 * In k=1, we know that if we wanna find a num to be part of the smaller numbers,
 * this num has to be the smallest in its row. Similarly, the largest num in the row
 * shall be picked if it's a "larger" element. With some greedy arguments, the n rows
 * with a larger #min + #max shall pick its maximum, while the remaining rows/colors
 * should pick its minimum.
 * 
 * Sadly, this greedy approach isn't correct for other values of k, but the thing we
 * know (and can prove) using our experience with k=1 is:
 *      Each time a "plus" element is picked, it must be largest value of that
 *      color. Each time when a "minus" element is picked, it must be the
 *      smallest value in the row.
 * Yep, this is valid, though we don't know what colors should be picked as "plus" or
 * "minus" (yet).
 * 
 * I then looked at [S3], which i didn't finish. After this, I went to [S4], i.e.
 * k=n. In this scenario, every num in x[][] is either added to or subtracted from
 * the final ans. Naturally, we want the largest nm/2 values to be "plus", while the
 * nm/2 smallest ones to be "minus". It turns out that we can always give a
 * construction that achieves this. Imagine that we've decided which elements are
 * "plus" & which ones are "minus"; as long as the num of rows with all "plus" <= n/2
 * and num of rows with all "minus" <= n/2, we can always find a round of tickets
 * with n/2 "plus" & n/2 "minus". If the contrary happens, either "plus" or "minus"
 * elements have a num >nm/2, which is impossible. This means we can always induct
 * downwards.
 * 
 * Wow, [S4] is really inspiring. Now, for each row of values a prefix is chosen for
 * "minus" and a suffix is chosen for "plus". We can use dp to find exactly nk/2
 * "minus" and exactly nk/2 "plus" with maximum profit, and give a construction since
 * this is just [S4] with m -> k. Well, at least I thought so, but this results in a
 * O((nm)^2) dp (assuming k is close to m). This implies that we can only score 12
 * pts in [S5], AND we'll have to code tons more code to score previous subtasks.
 *      (I admit that this is sth I hate about IOI)
 * Define r[i][j] to be the difference in color i when we pick j "plus". In other
 * words, r[i][j] = #sum_of_suffix_with_len_j - #sum_of_prefix_with_len_(k-j). It's
 * easy to see that r[i][] is increasing, but after carefully examining this, the
 * difference between adjacent terms in r[i][] is decreasing. Therefore, we can just
 * greedily find the nk/2 "plus". Finally, I've finished this problem!
 * 
 * Time Complexity: O(mn * log(mn))
 * Implementation 1             (Full solution, greedy + sorting + construction)
*/

#include <bits/stdc++.h>
#include "tickets.h"

typedef long long   ll;
typedef std::vector<int>    vec;


struct pair_t {
    ll diff;
    int color;
    int plus;   // num of plus
};

ll find_maximum(int k, std::vector<vec> x) {
    int n = x.size(), m = x[0].size();

    std::vector<pair_t> pairs;
    ll price = 0;
    for (int i = 0; i < n; i++) {
        std::vector<ll> prefix(m + 1);
        prefix[0] = 0;
        for (int j = 0; j < m; j++)
            prefix[j + 1] = prefix[j] + x[i][j];
        std::vector<ll> r(k + 1);
        for (int j = 0; j <= k; j++)
            r[j] = -prefix[k - j] + (prefix[m] - prefix[m - j]);
        price += r[0];
        for (int j = 1; j <= k; j++) {
            assert(r[j] >= r[j - 1]);
            pairs.push_back(pair_t{r[j] - r[j - 1], i, j});
        }
        for (int j = 1; j < k; j++)
            assert(r[j] - r[j - 1] >= r[j + 1] - r[j]);
    }
    std::sort(pairs.begin(), pairs.end(),
              [](const pair_t& p1, const pair_t& p2) {
                  return p1.diff > p2.diff || (p1.diff == p2.diff && p1.plus < p2.plus);
              });
    vec plus(n, 0);
    for (int l = 0; l < n * k / 2; l++)
        price += pairs[l].diff, plus[pairs[l].color] = pairs[l].plus;
    
    vec minus(n);
    for (int i = 0; i < n; i++) {
        minus[i] = k - plus[i];
        assert(plus[i] >= 0 && minus[i] >= 0);
    }
    vec left(n, 0), right(n, m - 1);
    std::vector<vec> tickets(n, vec(m, -1));
    for (int r = 0; r < k; r++) {
        int m_count = 0, p_count = 0;
        std::vector<bool> must(n, false);   // if i must be minus or must be plus
        for (int i = 0; i < n; i++) {
            if (plus[i] == 0) {
                tickets[i][left[i]] = r, left[i]++;
                minus[i]--, m_count++, must[i] = true;
            } else if (minus[i] == 0) {
                tickets[i][right[i]] = r, right[i]--;
                plus[i]--, p_count++, must[i] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!must[i]) {
                if (m_count < n / 2)
                    tickets[i][left[i]] = r, left[i]++, m_count++, minus[i]--;
                else if (p_count < n / 2)
                    tickets[i][right[i]] = r, right[i]--, p_count++, plus[i]--;
                else
                    std::abort();   // absurd
            }
        }
    }
    allocate_tickets(tickets);
    return price;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10