Codeforces Round 919 (Div. 2)

I’m currently indulging in the planning and executing our Hostel Day. Due to that, I was too exhausted by 7 PM. However, as I registered for the contest earlier, I decided to try solving at least one problem. I got the Accepted verdict for the first problem but, as I expected, got a TLE for the second.

A. Satisfying Constraints

To do: Guess the number of values k, which satisfy the given three types (>=, <=, and !=) of n constraints.

It was a simple brute-force problem. First, find the lower and upper limits of k, then subtract the number of values that satisfy type 3, which lie between those limits.

int n;
cin >> n;
vector<pair<int, int>> v;
int minMax = INT_MIN, maxMin = INT_MAX, excluded = 0;
for (int i = 0; i < n; i++)
{
    int a, x;
    cin >> a >> x;
    v.push_back({a, x});
    if (a == 1)
    {
        minMax = max(minMax, x);
    }
    else if (a == 2)
    {
        maxMin = min(maxMin, x);
    }
}
for (int i = 0; i < n; i++)
{
    if (v[i].first == 3 && v[i].second >= minMax && v[i].second <= maxMin)
    {
        excluded++;
    }
}
cout << ((maxMin - minMax - excluded + 1) > 0 ? (maxMin - minMax - excluded + 1) : 0) << endl;

B. Summation Game

To do: Given an array a, two players (A and B) play optimally to win the game (A wants to maximize the sum of the array, and B wants to minimize it). First, A removes at most k elements from the array and then B multiplies at most x elements of the array with -1.

First, I sorted the array in descending order. Then, A can remove 0 to k elements. For all of those cases, we calculate the sum of the array after subtracting x largest available elements of the array. But, per the constraints, the solution shouldn’t exceed nlogn time complexity.

int n, k, x;
cin >> n >> k >> x;
vector<int> a;
for (int i = 0; i < n; i++)
{
    int y;
    cin >> y;
    a.push_back(y);
}
long long sum = accumulate(a.begin(), a.end(), 0);
sort(a.begin(), a.end(), greater<int>());
long long maxi = INT_MIN, rem = 0, subtract = 0;
for (int i = 0; i <= k; i++)
{
    if (i + x > n)
    {
        x--;
    }
    rem = accumulate(a.begin(), a.begin() + i, 0);
    subtract = accumulate(a.begin() + i, a.begin() + i + x, 0);
    maxi = max(maxi, sum - rem - (subtract * 2));
}
cout << maxi << endl;