DEQMNMXEZ - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an odd-length array A, Alice and Bob will do the following:

  • Start with empty array B.
  • Take turns, Alice going first.
  • On the i-th turn, the player must insert A_i to either the front or back of B.

The score of the final array B is \min(B_1, B_N).
Alice wants to maximize the score, Bob wants to minimize it.
Define f(A) to be the final score when both players try to achieve their goals.

Compute f(A).

EXPLANATION:

There are a couple of different ways to solve the problem.

One of them is to simply be greedy.
Observe that we only really care about the values at the borders of B, i.e. at its beginning or end.
Also, once some value is no longer on the border, it will never be on the border in the future as well.

Further, note that once the first i elements have been processed, the element A_i will certainly be one of the border elements.
So, we only care about what the other border element is.

This lends itself naturally to both Alice and Bob being greedy: if the current border elements are (x, y),

  • Alice wants both border elements to be as large as possible, so she will replace \min(x, y) with A_i.
  • Bob wants both border elements to be as small as possible, so he will replace \max(x, y) with A_i.

Starting with the border elements being (A_1, A_2), simply following this greedy process will result in some final pair of border elements (A_N, x), at which point the answer is \min(A_N, x).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, q; cin >> n >> q;
    
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    int ans = max(a[1], a[2]);
    for (int i = 3; i <= n; i++){
        if (i % 2 == 1) ans = min(ans, a[i]);
        else ans = max(ans, a[i]);
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
1 Like