Codeforces 442C - Artem and Array

Problem Statement:
442C - Artem and Array

Solution:
As per normal, greedy problem is difficult to fathom, but always a nice exercise for this lazy mind such as mine.

First and foremost, we should use a random access linked list to solve this problem. You can create a random access linked list by using an array representing the nodes, and use the array indexes to point to each other. So by representing linked list in an array, we can have the best of both worlds (at least for this problem).



Next, we need a greedy strategy to choose amongst the elements such that we can obtain a maximum score. Let's define \(c_i = \min \{ a_{\text{left}}, a_{\text{right}}\} \) where left and right is the current neighbours of a[i]. Here we employ several observations:
1. Suppose we have a list of elements such that the smallest of them all, \(a_i\), is not on the end points of the list. Furthermore, suppose that a[left] \(\geq\) a[i] and a[right] \(\geq\) a[i] (i.e. a[i] is not bigger than both of its neighbours). If we remove this \(a_i\), c[left] and c[right] can only increase in value. This suggest that we would want to remove such \(a_i\) as early as possible.

2. So we come up with a greedy strategy: In each iteration, we would like to remove a smallest \(a_i\) such that \(a_i\) is not bigger than both of its neighbours, until there is no such \(a_i\) left. Now we want to prove that doing so will lead to an optimal score. Let's call O be the strategy described above. Define Q as an optimal strategy such that the orders of removal is different. We want to transform Q to O. Suppose s[i] is the sorted a[i], hence in O, s[i] is removed at iteration i. For each s[i], we do:

2.1. Suppose currently Q and O agrees in their order of removal only up to step i-1. Hence at step i, s[i] is removed in O at step i, while it is removed in Q at step j, such that i < j.

2.2. In Q, we will do a swapping operations one by one, from j to i. Let's w is removed right before s[i] is removed (i.e. at j-1 -th step). If w is not a neighbour of s[i] currently, then we can swap the order of removal of s[i] and w without affecting the final outcome, since removal of an element only affects the c[i] of its neighbours.

2.3. Now if w and s[i] are neighbours, we claim that if we swap the order and remove s[i] first, we will end up with at least equal or more optimal score. This is because if we remove s[i] first, then c[w] will definitely increase because it will have neighbours with value higher than or equal to s[i]. However by assumption the swap must not lead to a higher score obtained since Q is already optimal. Hence the optimality of Q is maintained by doing this swap.

Hence in the end Q will be equal to O, and hence O is optimal.

3. Now we will reach a point where we can't find such a[i] that is not bigger than both of its neighbours. At this point, we will greedily remove the ones with highest c[i] each time. Removal of such element would maintain the c[left] and c[right] of that element (can be quite easily shown by breaking down the claim into cases) and hence in the end we will be essentially adding up the c[i]s of all the remaining elements.

My implementation used priority queue which resulted in an \(O(N\lg{N})\) complexity with pretty large constant. There is actually a better way which only requires one sorting operation, but I can't prove the correctness of the approach with this brain.

#include <iostream>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int linklist[500003][2];
int a[500003];
int mark[500003];
priority_queue<pair<int,int> > pq;
int N;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<N;++i){
        if(i > 0) {
            linklist[i][0] = i-1;
        } else {
            linklist[i][0] = -1;
        }
        if(i+1 < N) {
            linklist[i][1] = i+1;
        } else {
            linklist[i][1] = -1;
        }
    }
    for(int i=1;i<N-1;++i){
        if(a[i-1] >= a[i] && a[i] <= a[i+1]) {
            pq.push(make_pair(-a[i], i));
            mark[i] = 1;
        }
    }
    long long ans = 0;
    while(!pq.empty()) {
        int i = pq.top().second;
        pq.pop();
        ans += min(a[linklist[i][0]], a[linklist[i][1]]);
        int left = linklist[i][0];
        int right = linklist[i][1];
        if(left != -1) linklist[left][1] = right;
        if(right != -1) linklist[right][0] = left;
        if(left != 0 && linklist[left][0] != -1 && linklist[left][1] != -1){
            if(a[linklist[left][0]] >= a[left] && a[left] <= a[linklist[left][1]]) {
                if(!mark[left]){
                    mark[left] = 1;
                    pq.push(make_pair(-a[left], left));
                }
            }
        }
        if(right != N-1 && linklist[right][0] != -1 && linklist[right][1] != -1) {
            if(a[linklist[right][0]] >= a[right] && a[right] <= a[linklist[right][1]]) {
                if(!mark[right]){
                    mark[right] = 1;
                    pq.push(make_pair(-a[right], right));
                }
            }
        }
    }
    int cur = linklist[0][1];
    while(cur != -1 && cur != N-1) {
        ans += min(a[linklist[cur][0]], a[linklist[cur][1]]);
        cur = linklist[cur][1];
    }
    cout << ans << endl;
    return 0;
}