GAMEEZ - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07 and iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

PROBLEM:

You have an array A of length N and an K coins.
Consider the following process:

  • Start with \text{score} = 0 and x = 0.
  • For each i from 1 to N, in order, you can:
    1. Pay zero coins and do nothing.
    2. Pay one coin (if you have it) to increase \text{score} by A_i and x by 1.
    3. Pay two coins (if you have them) to increase \text{score} by A_i+x and x by 1.

For each K from 1 to 2N, find the maximum possible value of \text{score}.
Here, N \leq 2000.

EXPLANATION:

In the easy version of the problem, N \leq 2000 which means \mathcal{O}(N^2) or so is an acceptable complexity.
This means we can for example try to solve for a fixed value of K in linear (or close to linear) time and it’ll be fast enough - so let’s do exactly that.

Let’s call an operation where we pay one coin (and increase the score only by A_i) a type 1 operation, and an operation where we pay two coins (to increase the score by A_i + x) a type 2 operation.

Suppose we choose to perform c_1 operations of type 1, and c_2 operations of type 2.
How should we perform them?

First off, we surely need c_1 + 2c_2 \leq K, since the left side is the total number of coins spent.
If this doesn’t hold we can’t perform any combination of c_1 and c_2 moves, so we can ignore such cases entirely.

Now, we’ll perform c_1 + c_2 operations that increase our score in total.
Each type 1 operation increases \text{score} by the corresponding A_i, while each type 2 operation increases \text{score} by the corresponding A_i as well as by x.
Further, x increases by 1 each time we perform a type 1 or a type 2 operation.

So, it can be seen that:

  1. If we fix the set of (c_1 + c_2) elements we’re adding to the score, it’s then optimal to perform the c_2 operations of type 2 at the very end.
    This will allow the value of x to increase as much as possible before we start adding it to the score.
    Specifically, since we start adding x to the score after the first c_1 moves, the contribution of x to the score will be exactly
    c_1 + (c_1 + 1) + \ldots + (c_1 + c_2 - 1).
  2. From above, we see that the contribution to the score of x is totally independent of which c_1 + c_2 elements were chosen.
    So, we might as well just choose the largest c_1 + c_2 elements to add to the score.

The above analysis immediately gives us a solution in \mathcal{O}(N^2) for a fixed value of K.
Fix the values of c_1 and c_2, then the answer is just the sum of the largest c_1 + c_2 elements of A, plus c_1 + (c_1 + 1) + \ldots + (c_1 + c_2 - 1).

Running this for each K is too slow, so we need to optimize it further.

Instead of fixing the values of c_1 and c_2 separately, let’s fix the value of c_1 + c_2 instead.
Let S now denote the sum of the largest c_1 + c_2 elements of A (which can be found in constant time by sorting A and building its prefix sums).

Observe that if we fix the value of c_1, the final score will now be S + c_1 + (c_1 + 1) + \ldots + (c_1 + c_2 - 1).
Clearly, it’s best if c_1 is as small as possible to maximize this quantity.
Equivalently, we want c_2 to be as large as possible.

Now, recall that we have another constraint: a pair of (c_1, c_2) is only valid if c_1 + 2c_2 \leq K.
This tells us that c_2 \leq K - (c_1 + c_2).
Of course, we must also have c_2 \leq c_1 + c_2 itself, since c_1 cannot be negative.

Since we’ve already fixed both K and the sum (c_1 + c_2), we already know the maximum allowed value of c_2 - it’s exactly \min(c_1 + c_2, K - (c_1 + c_2)).
So, we can just use this value of c_2 to then compute c_1, and hence the sum S + c_1 + (c_1 + 1) + \ldots + (c_1 + c_2 - 1).

We’re now only iterating through all the values of (c_1 + c_2) from 0 to K, and solving for each one in constant time.
This gives us a solution for a fixed value of K in \mathcal{O}(N), which is exactly what we wanted.

To summarize, when solving for a fixed value of K:

  • Fix the value of c_1 + c_2, say i.
    i varies from 0 to K.
  • Let S_i denote the sum of the largest i elements of A.
    This can be found in constant time using prefix sums.
  • Compute c_2 = \min(i, K - i), and then c_1 = i - c_2.
  • The best possible score for this fixed i is then S_i + c_1 + (c_1 + 1) + \ldots + (c_1 + c_2 - 1).
    S_i is already known, and the remaining part is just the sum of several consecutive numbers and so can be computed easily.
  • The answer for K is the maximum score across all i.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    s = [0]
    for x in reversed(sorted(a)):
        s.append(s[-1] + x)
    
    ans = [0]*(2*n + 1)
    for k in range(1, 2*n+1):
        for i in range(min(n, k)+1):
            c2 = min(i, k-i)
            c1 = i - c2
            
            ans[k] = max(ans[k], s[i] + c1*c2 + c2*(c2-1)//2)
    print(*ans[1:])
1 Like
2

ll helper(int i,int j,vector<vector>& dp,vector& a){
if(j<0 or i<0)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
if(i==0)
return dp[i][j]=a[0];
if(j==0)
return dp[i][j]=0;

if(j<i+1)
    return dp[i][j]=helper(i-1,j,dp,a);

ll op1=a[i]+helper(i-1,j-1,dp,a);
ll op2=0;
if(j>=i+2)
    op2=a[i]+helper(i-1,j-2,dp,a)+i;

return dp[i][j]=max(op1,op2);

}
void solve() {
ll n; cin>>n;
vector a(n);
for(int i=0 ; i<n ; ++i)
cin>>a[i];
vector<vector> dp(n,vector (2*n+1,-1));
sort(all(a));
reverse(all(a));

for(int i=1; i <=2*n ; ++i)
    cout << helper(n-1,i,dp,a) << " ";
debug(dp)
cout << nline;
debug(helper(2,3,dp,a))

},
can someone explain me why this dp appraoch is wrong for this question Problem Code - GAMEEZ