AI Translated from Chinese

Preface

Problem link: Codeforces Round 867 (Div. 3)

Best performance since getting into the hobby. Writing this solution to record some insights.

Problem A has complete code, other problems only have core code (templates omitted).

Main Text

A. TubeTube Feed

Problem: Given array a[] (video length in seconds) and b[] (video “entertainment value,” stored in variable fun), and integer t (lunch duration). For a video, you can skip (cost 1s) or decide to watch it, but must ensure the total time consumed plus video length doesn’t exceed t. Find which video to watch (output index of a[]) to maximize fun

Simulate according to the problem statement.

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _all(x) (x).begin(), (x).end()
#define _abs(x) ((x >= 0) ? (x) : (-x))
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PDD pair<double, double>
#define fi first
#define se second

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

using namespace std;

const int N = 50 + 5;
int n, t, a[N], b[N];


void init() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
}

void solve() {
    int ans = -1, fun = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] <= t)
            if (fun < b[i]) {
                ans = i;
                fun = b[i];
            }
        t--;
    }
    cout << ans << "\n";
}

int main() {
    IOS
    int test_case;
    cin >> test_case;
    while (test_case--) {
        init();
        solve();
    }
    return 0;
}

B. Karina and Array

Problem: Given an array, find two numbers such that their product is maximum

Sort and compare the product of the largest and second largest numbers with the product of the smallest and second smallest numbers.

Note to use long long for intermediate variables.

const int N = 2e5 + 20;
int n, a[N];


void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    cout << max(((LL)a[0] * (LL)a[1]), ((LL)a[n-1] * (LL)a[n-2])) << "\n";
}

C. Bun Lover

Problem: Two buns are coiled into a square of side length n (mosquito coil?), each bun is coated with chocolate sauce on both inside and outside. Given any n, find the total length of chocolate sauce lines

Easy to find the pattern: $ ans = 4n + (n - 1) + 2(n - 2) + 2(n - 3) + … + 2 \times 2 + 1 \times 3 = 5n + \frac{(1+n-2)(n-2)}{2} \times 2 = n^2 + 2n + 2 $

LL n;

void solve() {
    cin >> n;
    cout << n*n + 2*n + 2 << "\n";
}

D. Super-Permutation

Problem: Construct an n-permutation such that its prefix sum array’s elements $ (\mod n) + 1 $ is also an n-permutation

Construction problem. Easy to see that prefix sum array elements modulo n are 0 ~ n-1. According to properties of modulo operations: $ (a+b) \mod n = a \mod n + b \mod n $ We can directly perform addition operations on the remainder values.

For example, with $ n = 6 $. Construct 6 5 2 3 4 1, its remainder array is 0 5 2 3 4 1, then prefix sum modulo n array is 0 5 1 4 2 3.

Compare the constructed sequence and prefix sum array modulo n:

6 5 2 3 4 1
0 5 1 4 2 3

Do you see the pattern?

For any n, construct prefix sum modulo n array in pairs:

b = [0, n-1, 1, n-2, 2, n-3, ......]

However, we don’t need to construct this array first to construct the n-permutation; we can compute directly (see code for details).

Analysis of Correctness

First, construct the prefix sum modulo n array. Consider 0 first. 0 must be placed first, otherwise duplicate elements will appear.

Second, n being odd is always unsolvable, while even n is always solvable.

For this array, $ sum = \frac{(1 + n)n}{2} $, let $ k = \frac{1 + n}{2} $, then $ sum = kn $.

When $ n $ is odd, $ k $ is an integer, then $ sum \mod n = 0 $, which contradicts the existing 0.

When $ n $ is even, $ k $ is not an integer, and $ sum \mod n = \frac{n}{2} $, no contradiction.

Code

int n;

void solve() {
    cin >> n;
    if (n == 1) { cout << 1 << "\n"; return; }
    if ((n & 1) == 1) {
        cout << -1 << "\n";
        return;
    }
    cout << n << ' ' << n-1 << ' ';
    for (int i = 1; i < n / 2; i++) {
        cout << i*2 << ' ' << n - i*2 - 1 << ' ';
    }
    cout << "\n";
}

E. Making Anti-Palindromes

F. Gardening Friends

G1. Magic Triples (Easy Version)

G2. Magic Triples (Hard Version)

(To be continued…)