BOXGAM97 Editorial

PROBLEM LINK:

Practice
Contest

Author & Editoralist: Jafar Badour
Tester: Teja Reddy

PROBLEM EXPLANATION

There are N boxes on a table, numbered 1 through N from left to right. Each box has a number written on it; let’s denote the number written on box i by A_i.

Two players ― Jafar and Almir ― are playing a game that lasts for K turns. The rules of the game are as follows:

  • Before the game starts, they flip a coin to decide the starting player.
  • In the first turn, the starting player chooses a box and places the ball in it.
  • Afterwards, the players alternate turns (in the second turn, the non-starting player is playing).
  • In each turn, the current player can move the ball one box to the left (unless it is in box 1) or one box to the right (unless it is in box N).
  • The result of the game is the number written on the box containing the ball after K turns.

Jafar plays in such a way that when the game ends, the number on the box which contains the ball is the biggest possible. On the contrary, Almir wants this number to be the smallest possible.

You know which player moves first. Determine the result of the game, assuming that both players play optimally.

DIFFICULTY:

Easy

PREREQUISITES:

None

EXPLANATION:

If K is odd then the starting player has a full control of the game.
If Jafar is starting then answer is the box with maximum value, and for almir it’s box with the smallest value.
The reasoning is simple, the player places the ball in his target box, and the second player wll move it to an adjacent one. What the first player does is simply returning it back.

If K is even, then the second player would make the last move. Let’s assume that Jafar is starting. He must choose a box such that the minimum of his neighbors (box to left\box to right) is maximum possible. After Jafar places the ball, Almir is forced to move it to one of the neighbors. What Jafar does is simply return it back to the starting box, and then Almir would return it to the neighboring box with a smaller value.

If Almir is starting he must choose a box such that the maximum of his neighbors (box to left\box to right) is the minimum possible.

Don’t forget to consider placing the ball at the first box or last box.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = (1<<20);
int T , n , K , p , arr[MX];
int main(){
	cin>>T;
	while(T--){
		cin>>n>>K>>p;

		for(int j = 1 ; j <= n ; j++) cin>>arr[j];

		if(K % 2){
			if(!p) cout<<*max_element(arr+1 , arr+1+n)<<endl;
			else cout<<*min_element(arr+1 , arr+1+n)<<endl;
		}
		else{
			int ans;
			if(!p){
				ans = max(arr[2] , arr[n-1]);
				for(int j = 2 ; j < n ; j++)
					ans = max(ans , min(arr[j-1] , arr[j+1]));
			}
			else{
				ans = min(arr[2] , arr[n-1]);
				for(int j = 2 ; j < n ; j++)
					ans = min(ans , max(arr[j-1] , arr[j+1]));
			}
			cout<<ans<<endl;
		}
	}
}
8 Likes

There is ambiguity in this statement

  • In each turn, the current player can move the ball one box to the left (unless it is in box 1) or one box to the right (unless it is in box N).

Unless my english is really bad, “can” here means that if the player wants to, he can move to left or right or not move at all.
I even asked about this in comments when there was more than a hour left, but no reply.

Check both my solutions
After contest - https://www.codechef.com/viewsolution/27601148
At the time of contest - https://www.codechef.com/viewsolution/27591829

There is very little difference between both of them, I could’ve got an AC if someone replied to the comment, or statement was not this ambiguous.

Why does admin/moderator keep saying to ask queries in comments section when no one there cares to reply to your comments.

Screenshot of asking in comments https://m.imgur.com/a/iF8Mmrl

5 Likes

It is properly stated. Read multiple times.

  • current player can move the ball one box to the left, in which case in all position he can move to a position immediate left to it. But wait…
  • In paranthesis, it is mentioned “Unless it is in box 1” - Which means if the position is box 1, he cannot move left.
    Now read both of the above statement’s. You will conclude “The balls kept in all positions except 1 can be moved left”.

Same for the other one also.

But the thing is, You can always ask the doubt in comments section and the author or admin needs to address it during the contest. It is very bad if they didn’t. In this case, a Big YES.

But TBH, problem statement is clear.

3 Likes

My bad (20 char limit)

1 Like

Brother He used can in different sense…
He can move ball in left box …
He there means not only left he can move in right too…
However i understand your prospect…
U r right too …
Better luck next time…
He used that can for left move n u mistaken it for move…

I just wanna to ask that by question it is not clear that whether they know total number of turns or not.If they know then we will go as the editorial’s way.
If they don’t know total turns ( as I got ) then …let say P=0,means Jafar got first chance then ge will go for max and at last chance Almir will consider only the neighbourhood of max.

I guess there should be the word “should” instead of “can” ,then it is more meaningful.

1 Like

Yes reading the problem statement I also thought can means the ball can stay in same position too and got WA during contest.Instead of ‘can’ they should have used ‘must’.

I did excatly same as said in tutorial but still getting WA …
:frowning:

i also misunderstood,but problem statement is fine.but when you got to knew, you should have submitted for other case too, i didn’t even realized.

I submitted as soon as I got to know after contest :joy::joy:

i also got to know after contest:upside_down_face:

Very helpful editorial but I have a small doubt.
Why you have choose 2nd and last 2nd index for maximum and minimum neighbour in the beginning?

for very left box and very right box,because in second turn it will be moved to second right or second left ,
A[0]–>A[1]
A[n-1]–>A[n-2]

1 Like

please point out where did i go wrong?
I did exactly same thing as that of editorial

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

What if two boxes are containing same value and having different values of their neighboring boxes?

can someone plz explain what is happning when k is odd in the setters solution
why (ans = max(arr[2] , arr[n-1]):wink: this is needed

Hello @udayps055 ,

In the editorial it is given that when k is EVEN then jafar must choose the box such that the minimum of the neighbours is maximum possible, else if almir is starting then he should choose the box such that the maximum of his neighbours is minimum possible

So we have to look for edge cases , that is he chooses the 1st box then the only neighbour is the 2nd box
ans = arr[2]
If he chooses the last box then the its only neighbour is (n-1)th box so it will be
ans = max(ans , arr[n-1])

Instead of writing these two lines … they have written only one line as
ans = max(arr[2] , arr[n-1])

Hope you understand

Sudheera Y S
:slightly_smiling_face::smile:

2 Likes

thank u @sudheerays123

2 Likes

does it mean that on it’s first move jafar will put the ball in the box having biggest no.?