MYSSLIME - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N slimes in a row, the i-th of which has power A_i. You must do the following N-1 times:

  • Choose two adjacent slimes and make one of them eat the other.
    If a slime with power x eats a slime with power y, its new power is \max(0, x-y).

There will be a single slime remaining in the end. Find the maximum possible power of this slime.

EXPLANATION:

Suppose slime i is the one remaining in the end.
Note that it’s impossible to increase the power of slime i: if it ever eats another slime, its strength can only either decrease or remain the same.

Now, since slime i is remaining, it must eat at least one slime to its left (i.e. with index \lt i) and one slime to its right (with index \gt i).
This is because slimes can only eat adjacent slimes, so it’s impossible for any slime that’s \lt i to eat something that’s \gt i by “crossing” i.

Ideally, slime i shouldn’t eat another slime with a high power, so that its own power doesn’t decrease much.
The best we can do is, of course, to try and make slime i eat another slime with power 0.
In fact, this is almost always possible!

In particular, it can be seen that:

  • If i \geq 3, we can always ensure that slime i eats exactly one slime with power 0 to its left.
  • If i \leq N-2, we can always ensure that slime i eats exactly one slime with power 0 to its right.
Proof

This is quite simple to prove.

Suppose i \geq 3 (the i \leq N-2 case is analogous).
Let m be the index of the smallest value among [A_1, A_2, \ldots, A_{i-1}].

First, make slime m eat one of its neighbors (other than i, of course).
Note that after this, slime m will have a power of 0.
Now, simply make slime m eat all the other slimes, and its power will remain 0. At the end of this, slime i can eat slime m and A_i won’t decrease, as desired.

This leaves only i = 1, 2 and i = N-1, N as edgecases (the left side for the former two, the right side for the latter).
However, it’s obvious what to do in these cases:

  • If i = 1, there’s nothing to eat to the left anyway. i = N with the right is similar.
  • If i = 2, the slime is forced to eat slime 1 (with power A_1). The same applies to i = N-1 being forced to eat slime N.

With these observations, we can now easily check for each slime i what its maximum power can be if it’s the last slime remaining.

  • If i = 2, set A_i to \max(0, A_i - A_1), otherwise nothing needs to be done for the left side.
  • If i = N-1, set A_i to \max(0, A_i - A_N), otherwise nothing needs to be done for the right side.

Print the maximum of all of these.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        l, r = 0, 0
        if i == 1: l = a[0]
        if i == n-2: r = a[-1]
        ans = max(ans, max(0, a[i] - l - r))
    print(ans)
1 Like
2

include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here

int t;
cin>>t;

while(t--){
    int n;
    cin>>n;
    
    vector<int> arr(n);
    
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    int mxe = arr[0];
    int index = 0;
    
    for(int i=1;i<n;i++){
        if(arr[i]>mxe){
            mxe=arr[i];
            index=i;
        }
    }
    
    int a = index;
    int b = n-index-1;
    long long int ans = mxe;
    
    if(a==1){
        ans = ans - arr[index-1];
    }
    
    if(b==1){
        if(ans>arr[index+1]){
            ans = ans - arr[index+1];
        }
        else{
            ans = arr[index+1] - ans;
        }
    }
    
    cout<<ans<<endl;
    
    
}

}

can any one tell any one example of input which is giving wrong ans for this code pls ?

3

Check for this testcase

1
3
90 100 3

Expected: 90

4

include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;
while(t–) {
int n;
cin >> n;
vectorarr(n,0);
for(int i=0; i<n; i++) {
cin >> arr[i];
}
for(int i=1; i<n-1; i++) {
int diff = abs(arr[i] - arr[i-1]);
if(abs(diff-arr[i+1]) > arr[i+1]) arr[i] = diff;
else arr[i] = 0;
}
cout << abs(arr[n-1] - arr[n-2]) << endl;
}
return 0;
}

why this can’t be accepted?
can anyone pls tell me hidden test case that will not satisfied by my code ??

1 Like
5

I tried this approach:

  1. Identified all max-value indices in the array.
  2. Checked the number of neighbors for each max-value index.
  3. Considered only max-value instances with exactly one neighbor, since others can be reduced to zero by optimal pairing (always selecting i as the smaller/equal value and j as the larger/equal value).
  4. Among these, found the least affected max-value instance as the final answer.

I focused only on the max value to maximize the last remaining slime’s power.

Here’s my submission: link

Could someone correct my approach?

1 Like
7

It’s not that deep bro :ribbon::heartpulse::pray:t2:

8

n = 7
1 99 50 92 60 100 20

It will fail on this test case.

9

got it

it doesn’t work for

Input

1
5
3 89 88 2 3

Answer

88

Output

86

as i’m only considering the max values, i’m neglecting others which could possibly result in a bigger value in the end!

1 Like
10

Good problem.
I wrote a O(N^3) DP solution for this problem in the contest… :sweat_smile:

12

Hey ladymaria , can you explain your dp solution please ? , what is the transition and defination of dp state ?