https://leetcode.com/problems/stone-game-vi/ from APT Portfolio

Thinking process:

First thing is to check the constraints. Since the size of the input is at most 10^5, we can’t consider any thing with a time complexity more than nlogn, so the solution is likely related to sorting/heap/binary search/linear solution.

Now, let’s observe the question a little bit more. If we pick one position, we not only gain the value but also prevent our opponent taking the value from that position. We can consider this as something like below.

Let’s say we are A, and our opponent is B. Our total value will be the sum of valueA from all position we pick. On the other hand, the total value of B will be the the sum of all valueB - the sum of valueB from all position we pick, e.g, in this graph, the total value of B is sum(valueB) - valueB[i].

In this way, we consider gaining the value and preventing our opponent taking the value from that position at the same time. As you can see in the graph, whenever we pick a position i, our diff reduces by valueA[i] + valueB[i]. So, we always want to pick a position where valueA[i] + valueB[i] is the maximum.

Here is the code.

 1class Solution {
 2public:
 3    int stoneGameVI(vector<int>& avs, vector<int>& bvs) {
 4        vector<vector<int>> a;
 5        int N = avs.size();
 6        for (int i=0; i<N; i++) {
 7            a.push_back({avs[i] + bvs[i], i});
 8        }
 9        sort(a.rbegin(), a.rend());
10        int av = 0, bv = 0;
11        for (int i=0; i<N; i++) {
12            if ((i%2) == 0) {
13                av += avs[a[i][1]];
14            } else {
15                bv += bvs[a[i][1]];
16            }
17        }
18        if (av > bv) return 1;
19        else if (av < bv) return -1;
20        return 0;
21    }
22};