Problem Statement
Given an integer \(M\), for any integer set \(S\), the "verification value" is defined as follows:
From the set \(S\), extract \(M\) pairs of numbers (i.e., \(2M\) numbers, without reusing any element from the set; if there aren't enough numbers for \(M\) pairs, take as many as possible). The verification value is the maximum possible sum of the squared differences of these pairs.
Now, given a sequence \(A\) of langth \(N\) and an integer \(K\), we need to divide \(A\) into several segments such that the verification value of each segment does not exceed \(K\). The goal is to find the minimum number of segments required.
Understanding the Verification Value
To maximize the sum of squared differences, we can use a greedy approach: pair the \(k\)-th largest value with the \(k\)-th smallest value. This can be computed by sorting the array and using two pointers to calculate the verification value in \(O(N \log N)\) time.
For a sorted sequence \(a_1, a_2, a_3, \ldots, a_n\), when a new number \(x\) is added, the maximum value can only be updated by a larger \(x\). Therefore, the maximum value doesn't decrease but increases or stays the same.
Similarly, \(a_k\) (the \(k\)-th largest number) can only be updated by numbers greater than \(a_k\), and \(a_{n-k+1}\) (the \(k\)-th smallest number) can only be updated by numbers smaller than \(a_{n-k+1}\). Thus, \(a_k\) doesn't decrease, \(a_{n-k+1}\) doesn't increase, and \(a_k - a_{n-k+1}\) doesn't decrease, meaning \((a_k - a_{n-k+1})^2\) doesn't decrease.
Therefore, when a new number is added to the sequence, the verification value doesn't decrease—it has a non-strict monotonicity property.
80 Points: Brute Force Approach
While ensuring the verification value doesn't exceed \(K\), we continuously expand the segment length. When we can no longer expand, we start a new segment.
Specifically, let the current segment be \([l, r]\). We keep moving \(r\) to the right. If the verification value exceeds \(K\), we set \(l = r\) and increment the segment count, starting a new segment.
Each time \(r\) increases, we extract \(a[l, r]\), sort it, and use two pointers to scan from both ends, accumulating the squared differences to calculate the verification value.
The time complexity of calculating the verification value is \(O(N \log N)\), and we need to calculate it \(N\) times, resulting in an overall time complexity of \(O(N^2 \log N)\).
This approach passes 40% of the data based on time complexity, and another 40% of the data has special properties that significantly reduce the number of judgments and judgment time, allowing for a total of 80 points.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int getValue() {
int x = 0;
bool positive = true;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') positive = false;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return positive ? x : -x;
}
const int MAX_SIZE = 500005;
int testCases, sequenceLength, pairsCount, threshold;
int elements[MAX_SIZE], temporary[MAX_SIZE];
inline bool isValidSegment(const int left, const int right) {
for (int i = left; i <= right; i++)
temporary[i] = elements[i];
sort(temporary + left, temporary + right + 1);
long long sum = 0;
int leftPtr = left, rightPtr = right, formedPairs = 0;
while (leftPtr < rightPtr && sum <= threshold && formedPairs < pairsCount) {
long long diff = temporary[rightPtr] - temporary[leftPtr];
sum += diff * diff;
leftPtr++, rightPtr--, formedPairs++;
}
return sum <= threshold;
}
int main() {
testCases = getValue();
while (testCases--) {
memset(elements, 0, sizeof(elements));
sequenceLength = getValue();
pairsCount = getValue();
threshold = getValue();
for (int i = 1; i <= sequenceLength; i++)
elements[i] = getValue();
int left = 1, segments = 0;
for (int right = 1; right <= sequenceLength; right++)
if (!isValidSegment(left, right)) {
left = right;
segments++;
}
printf("%d\n", segments + 1);
}
return 0;
}
90 Points: Doubling Approach
Since the verification value has monotonicity, we can use a doubling approach for \(r\). Each time, we check if the interval \([l, r + 2^{bin} - 1]\) is valid. If it is, we set \(r = r + 2^{bin} - 1\) and increment \(bin\). Otherwise, we decrement \(bin\) (to avoid unnecessary checks of oversized intervals that would increase runtime).
The time complexity is \(O(N \log^2 N)\).
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int getValue() {
int x = 0;
bool positive = true;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') positive = false;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return positive ? x : -x;
}
const int MAX_SIZE = 500005;
int testCases, sequenceLength, pairsCount;
long long threshold;
int elements[MAX_SIZE], temporary[MAX_SIZE], log2Values[MAX_SIZE];
inline bool isValidSegment(const int left, const int right) {
if (right > sequenceLength) return false;
for (int i = left; i <= right; i++)
temporary[i] = elements[i];
long long sum = 0;
sort(temporary + left, temporary + right + 1);
int leftPtr = left, rightPtr = right, formedPairs = 0;
while (leftPtr < rightPtr && sum <= threshold && ++formedPairs <= pairsCount) {
long long diff = temporary[rightPtr] - temporary[leftPtr];
sum += diff * diff;
leftPtr++, rightPtr--;
}
return sum <= threshold;
}
int main() {
for (int i = 2; i <= 500000; i++)
log2Values[i] = log2Values[i >> 1] + 1;
testCases = getValue();
while (testCases--) {
sequenceLength = getValue();
pairsCount = getValue();
scanf("%lld", &threshold);
for (int i = 1; i <= sequenceLength; i++)
elements[i] = getValue();
int segments = 0;
int left = 1, right = left, bin = 1;
while (right <= sequenceLength) {
if (!bin) {
segments++;
left = right + 1;
right = left;
}
if (isValidSegment(left, right + (1 << bin) - 1)) {
right = right + (1 << bin) - 1;
bin++;
}
else bin--;
}
printf("%d\n", segments);
}
return 0;
}
100 Points: Doubling with Merge Sort Optimizaton
During the isValidSegment check, especially in the bin++ phase, the first half of the sequence is already sorted and doesn't need to be sorted again. When half of the sequence is already sorted, we can use a merge sort-like approach to combine the two halves.
The C++ STL provides a merge function that can conveniently merge two sorted sequences in to one sorted sequence:
Usage: merge(first sequence begin, first sequence end, second sequence begin, second sequence end, target sequence begin). Note that the begin and end are pointers, and the end element is not included (left-closed, right-open), similar to the parameters passed to sort.
For the other half, we can simply use sort, which won't cause a timeout.
The time complexity is \(O(N \log N)\).
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int getValue() {
int x = 0;
bool positive = true;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') positive = false;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return positive ? x : -x;
}
const int MAX_SIZE = 500005;
int testCases, sequenceLength, pairsCount;
long long threshold;
int elements[MAX_SIZE], sortedArray[MAX_SIZE], mergedArray[MAX_SIZE], log2Values[MAX_SIZE];
inline bool isValidSegment(const int left, const int middle, const int right) {
if (right > sequenceLength) return false;
for (register int i = middle; i <= right; i++)
sortedArray[i] = elements[i];
sort(sortedArray + middle, sortedArray + right + 1);
merge(sortedArray + left, sortedArray + middle, sortedArray + middle, sortedArray + right + 1, mergedArray + left);
long long sum = 0;
int leftPtr = left, rightPtr = right, formedPairs = 0;
while (leftPtr < rightPtr && sum <= threshold && ++formedPairs <= pairsCount) {
long long diff = mergedArray[rightPtr] - mergedArray[leftPtr];
sum += diff * diff;
leftPtr++, rightPtr--;
}
if (sum <= threshold) {
for (int i = left; i <= right; i++)
sortedArray[i] = mergedArray[i];
}
return sum <= threshold;
}
int main() {
for (register int i = 2; i <= 500000; i++)
log2Values[i] = log2Values[i >> 1] + 1;
testCases = getValue();
while (testCases--) {
sequenceLength = getValue();
pairsCount = getValue();
scanf("%lld", &threshold);
for (register int i = 1; i <= sequenceLength; i++)
elements[i] = getValue();
int segments = 0;
int left = 1, right = left, bin = 1;
sortedArray[left] = elements[left];
while (right <= sequenceLength) {
if (!bin) {
segments++;
left = right + 1;
right = left;
}
if (isValidSegment(left, right + 1, right + (1 << bin) - 1)) {
right = right + (1 << bin) - 1;
bin++;
}
else bin--;
}
printf("%d\n", segments);
}
return 0;
}
Note: Both \(k\) and \(sum\) should be declared as long long to prevent overflow.