logoChat01.ai

C. Coloring Game time limit per test2.5 seconds me...

Создано: 23 июня 2025 г.

Отвечено с использованием O4 Mini High от Chat01

Вопрос

C. Coloring Game
time limit per test2.5 seconds
memory limit per test256 megabytes
Alice and Bob are playing a game using an integer array a
of size n
.

Initially, all elements of the array are colorless. First, Alice chooses 3
elements and colors them red. Then Bob chooses any element and colors it blue (if it was red — recolor it). Alice wins if the sum of the red elements is strictly greater than the value of the blue element.

Your task is to calculate the number of ways that Alice can choose 3
elements in order to win regardless of Bob's actions.

Input
The first line contains a single integer t
(1≤t≤1000
) — the number of test cases.

The first line of each test case contains a single integer n
(3≤n≤5000
).

The second line contains n
integers a1,a2,…,an
(1≤a1≤a2≤⋯≤an≤105
).

Additional constraint on the input: the sum of n
over all test cases doesn't exceed 5000
.

Output
For each test case, print a single integer — the number of ways that Alice can choose 3
elements in order to win regardless of Bob's actions.

Example
InputCopy
6
3
1 2 3
4
1 1 2 4
5
7 7 7 7 7
5
1 1 2 2 4
6
2 3 3 4 5 5
5
1 1 1 1 3
OutputCopy
0
0
10
2
16
0
Note
In the first two test cases, no matter which three elements Alice chooses, Bob will be able to paint one element blue so that Alice does not win.

In the third test case, Alice can choose any three elements. If Bob colors one of the red elements, the sum of red elements will be 14
, and the sum of blue elements will be 7
. If Bob chooses an uncolored element, the sum of red elements will be 21
, and the sum of blue elements will be 7
.

In the fourth test case, Alice can choose either the 1
-st, 3
-rd and 4
-th element, or the 2
-nd, 3
-rd and 4
-th element.

if dp or combinatonics can be used to solve this problem then you it to solve it under the time complixty adn also make each varbile 2-3 cahrater long n c++

Мысль

Evaluating Alice's strategy

Alice is selecting 3 elements where for any choice of Bob's blue element, the sum of the red elements must be greater than a particular value. The challenge is accounting for Bob's worst-case scenario, where he picks a blue element that could potentially break this condition. Bob's choice of b could involve a red element, in which case the sum of the other two red elements must still meet the condition. We need the number of valid triples where this holds for all possible b.

Refining Alice's winning condition

For Alice to win, the sum of the red elements in a triple needs to be strictly greater than the chosen blue element's value. If Bob selects a red element, that element's contribution is removed from the sum, resulting in a smaller total. We need to ensure that the sum is greater than the largest value in the entire array (M_all) and also that the sum exceeds twice the value of the largest red element in the chosen triple (M_red). Bob will aim to pick the element with the largest value to maximize his chances.

Formulating the conditions for a valid triple

To determine if a triple (i, j, k) is valid, we compare the sum of the red elements against certain thresholds. For each k, we calculate the threshold (T_k) as the maximum of either a_k or a[n-1] - a_k. If 2 * a[k] >= a[n-1], we only need to ensure that the sum of the red elements is greater than a[k]. If 2 * a[k] < a[n-1], the sum must exceed a[n-1] - a[k]. Using a two-pointer technique, we count valid pairs for each k. This solution has an O(n^2) complexity.

Thought for 30 seconds

Ответ

Here’s an O(n²) two-pointer solution in C++17. All variable names are 2–3 characters long, and it runs in ~25 million ops worst-case (n=5000):

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin >> a[i];
        // array is non-decreasing by input guarantee
        ll ans = 0;
        int mx = a[n-1];
        for(int k=2;k<n;k++){
            int ak = a[k];
            // threshold = max(a[k], a[n-1] - a[k])
            int t = max(ak, mx - ak);
            // count # of pairs i<j<k with a[i]+a[j] > t
            int l = 0, r = k-1;
            while(l < r){
                if(a[l] + a[r] > t){
                    ans += (r - l);
                    r--;
                } else {
                    l++;
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Explanation sketch:

  • Let Alice pick indices (i, j, k) with i<j<k.
  • Bob will choose the element with the largest value—either the overall maximum a[n-1] (if he picks outside the red set) or the largest of the three reds a[k] (if inside).
  • The winning condition becomes 
      a[i] + a[j] + a[k] > max( a[n-1], 2 * a[k] )
  • One shows that this reduces to 
      a[i] + a[j] > max( a[k], a[n-1] - a[k] )
  • For each k, set t = max(a[k], a[n-1] - a[k]) and count pairs (i<j<k) with a[i] + a[j] > t by the classic two-pointer sweep in O(k). Summing over all k gives O(n²).

Поделиться этим Q&A