MAXIMSCORE - Editorial

PROBLEM LINK:

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

Author: munch_01
Preparer: satyam_343
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

1390

PREREQUISITES:

None

PROBLEM:

There’s an array with N elements.

Alice will pick an index i, with 1 \leq i \leq N.
Bob will then pick an index j such that 1 \leq j \leq N and |i-j| = 1.
The score of this choice is |A_i - A_j|.

Alice wants to minimize this score while Bob wants to maximize it.
What is Alice’s optimal final score?

EXPLANATION:

Suppose Alice picks an index i. Then, Bob will can only pick index i+1 or i-1 (provided the index exists, of course).

So, once i is fixed, Bob will pick whichever one of those will maximize his score.
That is, the score is \max(|A_i - A_{i-1}|, |A_i - A_{i+1}|).
This can be easily computed for every index in \mathcal{O}(N).

Alice wants to minimize the score, so she will choose i that minimizes this.
So, once all the score above is computed for every index, simply take the minimum of them all.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 10 ** 9
    for i in range(n):
        cur = 0
        if i > 0: cur = max(cur, abs(a[i] - a[i-1]))
        if i+1 < n: cur = max(cur, abs(a[i] - a[i+1]))
        ans = min(ans, cur)
    print(ans)
1 Like

The question never mentioned to print the minimum score, it has unappropriated description and inadequate details

Alice wants to minimize the score while Bob wants to maximize the score . Determine the optimal score if they both play optimally.

The statement states, either maximizing or minimizing and the question never mentioned which one to choose. Never mentioned minimizing, now the editorial says minimum of all.
This contradicts.

Simply waste of time

3 Likes

@iceknight1093

can someone explain why my logic doesn’t work?

https://www.codechef.com/viewsolution/94808462

https://www.codechef.com/viewsolution/94770418
You Can Refer This as It is very Easily Implemented for understanding

Please tell on which test case this code fails. CodeChef: Practical coding for everyone

The statement clearly says

Alice wants to minimize the score while Bob wants to maximize the score.

The statement also clearly says

First, Alice picks any index i (1≤i≤N).
Then, Bob has to pick an index j such that …

Logical conclusions from here:

  • Alice moves first, and wants to minimize the score.
  • Bob moves after Alice, and wants to maximize the score.

This part is unambiguous.

I understand that the ‘optimal strategy’ part might be confusing if you’re seeing it for the first time, here’s how you can think about it.

Bob wants to maximize the score, and moves after Alice. He knows what she’s picked, of course he’s going to pick whichever option works best for him, i.e, \max(|A_i - A_{i-1}|, |A_i - A_{i+1}|).
This is Bob’s optimal play.

Alice wants to minimize the score, and knows that Bob will move after her.
This means she knows, if she picks A_i, which of A_{i-1} and A_{i+1} Bob will choose.
Bob’s choice is not something she can influence after she has chosen A_i.

Her only optimal play is to thus pick whichever A_i minimizes \max(|A_i - A_{i-1}|, |A_i - A_{i+1}|), because that’s the best she can do.


This is generally what ‘optimal play’ means in game theory. Each player will make a move to the best of their ability, and has perfect information about what their opponents will do in response to their move (which is the information they use to decide their move in the first place).

Also, if you’re confused about a statement during a contest, you can always ask a clarification! The setter or an admin will usually reply reasonably quickly.

1 Like

I totally ok with the description

But tell me what does the question want?
Neither minimum nor maximum, nothing is asked.
Also in TC:
-10 10 40 -50 30

if Alice Takes 10 that is minimum, and bob will automatically take 40 as max,
so the difference becomes 30

Now the question never mentioned to return minimum of all, so how can this be ambiguous please explain,
Being this as an optimal choice too, this contradicts.

Simply waste of time

1 Like

@iceknight1093 please look in here too…

I think you’ve misread the statement.

Alice wants to minimize the score, Bob wants to maximize the score.
The score is the difference between array elements.

The statement doesn’t say Alice will pick the minimum array element, or that Bob will pick the maximum adjacent element.

In your example: as you said, if Alice picks 10, Bob can pick 40 and get a difference of 30.
What if Alice picks -10? Then Bob is forced to pick 10, yes?
In that case the difference is 20, which is clearly better for Alice.

Alice knows this, so she will never pick 10 on her move.

1
7
-7300 -1175 6461 8058 -6917 3293 -4211

Answer is 6125 by choosing the first element.

1 Like

@iceknight1093 Please have a look at this, I don’t see WA failed test cases available for this problem…

1
5
4 -4 -3 -5 9

Answer is 2 by picking -3.

2 Likes

why this is not working?

#include
using namespace std;

int main()
{
ios_base::sync_with_stdio(false) ;
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–)
{
int a,c,d=1000000;
cin>>a;
int b[a] ;
for(int i=0;i<a;i++)
cin>>b[i] ;
if(a>2){
for(int i=1;i<a-1;i++)
{
c=max(abs(b[i]-b[i+1]),abs(b[i]-b[i-1]));
d=min(c,d);
}
c=min(abs(b[0]-b[1]),c);
c=min(abs(b[a-1]-b[a-2]),c);
cout<<c<<endl;
}
else
cout<<abs(b[0]-b[1]) <<endl ;
}
return 0;
}

c=min(abs(b[0]-b[1]),c);
c=min(abs(b[a-1]-b[a-2]),c);
cout<<c<<endl;

the variable here should be d, not c.