Traditional Game (Editorial)

Traditional Game#11730

Problem Author:	Maksym Shvedchenko
Prepared by:	Maksym Shvedchenko
Editorial by:	Maksym Shvedchenko

Any player must move only to those cells where the value for the other player is greater than the current value.Note that it doesn't work for the last move. Formally:

Chmyaax can move from cell $i$ only to a cell $j$ such that $b_{j} > a_{i}$ b_j > a_i.
Anton can move from cell $i$ only to a cell $j$ such that $a_{j} > b_{i}$ a_j > b_i.

Group 3: $n \leq 5000$ n \le 5000

Let $d p_{a, i}$ dp_{a,i} be the balance with which the game will end if the current balance is $0$ , it is Chmyaks' turn, and the piece is in position $i$ . Similarly, let $d p_{b, i}$ dp_{b,i} be the balance when it is Anton's turn.

For simplicity, let $a_{n} = \infty$ a_n = \infty and $b_{n} = \infty$ b_n = \infty.

Then $d p_{a, n} = d p_{b, n} = 0$ dp_{a,n} = dp_{b,n} = 0. We will calculate the dynamic programming values in decreasing order from larger indices to smaller ones. Specifically:

d p_{a, i} = i < j \leq n, a_{i} < b_{j} max d p_{b, j} + (j - i) \cdot a_{i}

dp_{a,i} = \max_{i < j \le n, a_i < b_j}{dp_{b,j} + (j-i)\cdot a_i}

and

d p_{b, i} = max (1 \leq j < i, b_{i} < a_{j} max d p_{a, j} + (i - j) \cdot b_{i}, (n - i) * b_{j})

dp_{b,i} = \max \left(\max_{1 \le j < i, b_i < a_j}{dp_{a,j} + (i-j)\cdot b_i}, {(n-i)*b_j}\right)

In the second formula, the term $(n - i) \cdot b_{j}$ {(n-i)\cdot b_j} appears cause Anton can use magic.

We have $2 n$ states in the dynamic programming where each is recalculated in at most $n$ iterations.

Time complexity: $O (n^{2})$ O(n^2)

Memory complexity: $O (n)$

Group 4: $n \leq 1 0^{5}$ n \le 10^5

In this group, there are many different solutions, but since they do not lead to a complete solution, they will not be described in great detail. We will implement CDQ divide and conquer. We will also maintain a Li-Chao tree or any other data structure. The solution will then take the following form:

    void solve(int l,int r){
        int m = (l+r)/2;
        solve(l,m);
        solve(m+1,r);
        CHT::init();
        vec<int> left; <-- put there all values from left segment
        vec<int> right; <-- put there all values from right segment
        sort(left);
        sort(right);
        Now 2 pointers
        CHT::init();
        .....
    }

That is, after updating the answer with its subsegment (recursively), we will update through the neighboring segment by sorting the elements (thus getting rid of the condition that the next cell must be larger) and simply applying CHT (Convex Hull Trick).

Time complexity: $O (n \cdot l o g (n)^{2})$ O(n\cdot log(n)^2)

Memory complexity: $O (n \cdot l o g (n))$ O(n\cdot log(n))

For the full solution we need more observations:

Each game will last a maximum of 2 moves.

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vec<int> a(n);
    for (int &i: a) cin >> i;
    vec<int> b(n);
    for (int &i: b) cin >> i;
    int best = -a[0] * (n - 1);
    int maxA = a[0];
    for (int i = 1; i < n - 1; i++) {
        if (b[i] > maxA)
            chmax(best, -a[0] * i + b[i] * (n - i - 1));
        chmax(maxA, a[i]);
    }
    cout << best << endl;
}