Eat Club

01Newton's Beautiful Sequence

Newton, a curious young mathematician, enjoys exploring the beauty of numerical sequences. Every evening, he sits under his favorite apple tree, contemplating the mathematical elegance hidden within sequences of numbers. To quantify the beauty of a sequence, Newton has created a unique method here’s how he does it: The initial beauty of the sequence is set to 0. For every possible contiguous segment of the sequence, he sorts the segment. He then iterates over the elements of each sorted segment, comparing the current element with the next one, if it exists. If the next element is greater than the current element by more than 1, he adds 1 to the beauty. If the contiguous segment contains only 1 element, then it also increases the beauty by 1. But computing it manually is time-consuming. Therefore, he asks you to write a program to help him in return for those delicious apples. If the beauty value becomes very large, take the modulo with 10⁹ + 7. You need to write bruteforce solution only. There are bonus points for bruteforce solution (Don't panic some test cases will not pass for the brute force solution but you will be awarded points) Input Format First line of input is the integer n denoting the size of the sequence. The next line contains n space separated integers denoting the elements of the sequence. Output Format Return an integer representing the beauty of the sequence modulo 10⁹ + 7 Another question is same as this question, but it asks for the optimal approach and also the constraints are changed. Constraints for the other question that asks for optimal approach - - 1 ≤ N ≤ 10⁵ - 1 ≤ sequence[i] ≤ N

Constraints

1 ≤ N ≤ 10³¹ ≤ sequence[i] ≤ N

Example 1

Input:

sequence = [2, 2, 2, 1, 5]

Output:

Explanation: The contiguous segments-> [2,2,2,1,5], [2,2,1,5], [2,1,5], [1,5], [5], [2,2], [2,1], [1,5], [5], [2], [2], [1], [5] will become [1,2,2,2,5], [1,2,2,5], [1,2,5], [1,5], [5], [2], [2], [1], [5] respectively. The first 4 adds 1 each to the beauty because the difference between 2 and 5 is greater than 1. Rest any pair does not adds to the beauty from these 4 segments. The last 5 mentioned segments also adds 1 each to the beauty since they contain only 1 element. Rest any contiguous segment has 0 contribution to the beauty of the array.

解法

题目允许 N ≤ 10³ 的 brute force：枚举所有 O(n²) 个子段，每个排序后扫描相邻差，累加贡献。单元素段额外贡献 1。整体时间 O(n³ log n)(每段 O(L log L))；n=1000 时约 10⁷ 量级，可过。空间 O(n)。

from typing import List

def calculateSequenceBeauty(sequence: List[int]) -> int:
    MOD = 10**9 + 7
    n = len(sequence)
    beauty = 0
    for i in range(n):
        for j in range(i, n):
            seg = sorted(sequence[i:j + 1])
            if len(seg) == 1:
                beauty = (beauty + 1) % MOD
                continue
            for k in range(len(seg) - 1):
                if seg[k + 1] - seg[k] > 1:
                    beauty = (beauty + 1) % MOD
    return beauty

import java.util.*;

class Solution {
    int calculateSequenceBeauty(int[] sequence) {
        final int MOD = 1_000_000_007;
        int n = sequence.length;
        long beauty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int[] seg = Arrays.copyOfRange(sequence, i, j + 1);
                Arrays.sort(seg);
                if (seg.length == 1) {
                    beauty = (beauty + 1) % MOD;
                    continue;
                }
                for (int k = 0; k < seg.length - 1; k++) {
                    if (seg[k + 1] - seg[k] > 1) beauty = (beauty + 1) % MOD;
                }
            }
        }
        return (int) beauty;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    int calculateSequenceBeauty(std::vector<int>& sequence) {
        const int MOD = 1'000'000'007;
        int n = sequence.size();
        long long beauty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                std::vector<int> seg(sequence.begin() + i, sequence.begin() + j + 1);
                std::sort(seg.begin(), seg.end());
                if (seg.size() == 1) { beauty = (beauty + 1) % MOD; continue; }
                for (size_t k = 0; k + 1 < seg.size(); k++) {
                    if (seg[k + 1] - seg[k] > 1) beauty = (beauty + 1) % MOD;
                }
            }
        }
        return (int) beauty;
    }
};

02Grandmaster's Choice

Sakaar is a trash planet created by the Grandmaster in the Tayo star system, and is surrounded by numerous wormholes that deposit space waste. On the planet Sakaar, the Grandmaster hosts an annual gladiatorial event where each warrior is identified by a unique Warrior Number (w) and a unique Power Level (p). Despite his love for chaos and thrilling battles, the Grandmaster sometimes enjoys a bit of strategy and intrigue. The total chaos score of the event is calculated as the sum of the scores from each fight as long as there are at least two warriors remaining in the arena. In a single fight:

The Grandmaster selects two warriors from the arena, let's call them A and B.
Choose the Power Level (p[A]) of one warrior and the Warrior Number (w[B]) of the other. Multiply these numbers together and add the result to the total chaos score. Alternatively, you can choose p[B] * w[A].
One warrior (say A) returns to the arena, while the other warrior (say B) is thrown outside, or vice versa, meaning B returns and A is thrown outside. In the final fight, both warriors leave the arena. Sometimes, the Grandmaster enjoys a change of pace, focusing on minimizing the chaos score for a twist in the usual chaos-filled battles. He needs your help to determine the smallest possible chaos score for the event, considering all the different ways to pair and organize the warriors. This strategic approach adds an unexpected twist to his love for battles and chaos. Since the chaos score can get very large, find the result modulo 10⁹ + 7. Input Format The first line contains a positive integer n: the number of warriors. The second line contains a list of n positive integers p; the ith of these represents the Power Level of the ith warrior. The third line contains a list of n positive integers w; the ith of these represents the Warrior Number of the ith warrior. Output Format The minimum possible total that can be attained if warriors are selected optimally. Since the result can be very large, output the result modulo 10⁹ + 7.

Constraints

2 ≤ n ≤ 10³
1 ≤ p[i] ≤ 10⁹
1 ≤ w[i] ≤ 10⁵

Example 1

Input:

p = [4, 1, 2]
w = [8, 3, 1]

Output:

Explanation: Let warriors be A, B, and C. Scenario 1: First fight between A and B, chaos score = 8 A is thrown out of arena Second fight between B and C, chaos score = 1 Total chaos score = 8+1 = 9 Scenario 2: First fight between A and B, chaos score = 8 B is thrown out of arena Second fight between A and C, chaos score = 4 Total chaos score = 8+4 = 12 Scenario 3: First fight between A and C, chaos score = 4 A is thrown out of the arena Second fight between B and C, chaos score = 1 Total chaos score = 4+1 = 5 Considering all possible remaining scenarios, we get the minimum chaos score = 5

Example 2

Input:

p = [1, 2, 3, 4]
w = [10, 20, 30, 40]

Output:

Explanation: The optimal strategy is to pair the warriors with the lowest power levels with the highest warrior numbers and vice versa. This minimizes the product of each fight's score. First fight between the 1st and 4th warrior, chaos score = 1 * 40 = 40 Second fight between the 2nd and 3rd warrior, chaos score = 2 * 30 = 60 Total chaos score = 40 + 60 = 100 Since the result can be very large, output the result modulo 10⁹ + 7, which is 100 % (10⁹ + 7) = 90.

解法

贪心 + 排序：每对 fight 贡献 min(p[A]·w[B], p[B]·w[A])。为了最小化总和，把 p 升序排序、w 降序排序后按下标配对：最弱的 power 配最大的 warrior 数。最终累加 min(p[i]·w[i]) 模 10⁹+7。时间 O(n log n)，空间 O(n)。

from typing import List

def grandmastersChoice(n: int, p: List[int], w: List[int]) -> int:
    MOD = 10**9 + 7
    p_sorted = sorted(p)
    w_sorted = sorted(w, reverse=True)
    # In each fight, score = min(p[A]*w[B], p[B]*w[A]).
    # Pair small p with large w → product handled greedily.
    pairs = n // 2
    total = 0
    for i in range(pairs):
        a, b = p_sorted[i], p_sorted[n - 1 - i]
        wa, wb = w_sorted[i], w_sorted[n - 1 - i]
        total = (total + min(a * wa, b * wb)) % MOD
    if n % 2 == 1:
        mid = n // 2
        total = (total + p_sorted[mid] * w_sorted[mid]) % MOD
    return total

import java.util.*;

class Solution {
    int grandmastersChoice(int n, int[] p, int[] w) {
        final int MOD = 1_000_000_007;
        int[] ps = p.clone(), ws = w.clone();
        Arrays.sort(ps);
        Arrays.sort(ws);
        // reverse ws
        for (int i = 0, j = ws.length - 1; i < j; i++, j--) {
            int t = ws[i]; ws[i] = ws[j]; ws[j] = t;
        }
        long total = 0;
        int pairs = n / 2;
        for (int i = 0; i < pairs; i++) {
            long a = ps[i], b = ps[n - 1 - i];
            long wa = ws[i], wb = ws[n - 1 - i];
            total = (total + Math.min(a * wa, b * wb)) % MOD;
        }
        if (n % 2 == 1) {
            int mid = n / 2;
            total = (total + (long) ps[mid] * ws[mid]) % MOD;
        }
        return (int) total;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    int grandmastersChoice(int n, std::vector<int>& p, std::vector<int>& w) {
        const long long MOD = 1'000'000'007;
        std::vector<int> ps = p, ws = w;
        std::sort(ps.begin(), ps.end());
        std::sort(ws.rbegin(), ws.rend());
        long long total = 0;
        int pairs = n / 2;
        for (int i = 0; i < pairs; i++) {
            long long a = ps[i], b = ps[n - 1 - i];
            long long wa = ws[i], wb = ws[n - 1 - i];
            total = (total + std::min(a * wa, b * wb)) % MOD;
        }
        if (n % 2 == 1) {
            int mid = n / 2;
            total = (total + (long long) ps[mid] * ws[mid]) % MOD;
        }
        return (int) total;
    }
};