Elegant solution to BOXGAM97

general
, ,
1

TL;DR: Here’s my solution: CodeChef: Practical coding for everyone to BOXGAM97 Problem - CodeChef

Since the Editorial is not out as I write this here’s how it works,

def compare(a, b, P):
    if P:    return a if a < b else b
    return a if a > b else b

The compare function takes three arguments a, b and P. It returns what P would pick out of a and b.

After the input taking part comes the three cases tagged with comments in the solution.

Case 1:

 target = min(A) if P else max(A)
 if A[1] == target or A[-2] == target:
     return target

If a player gets the first chance he can always force the minimum or maximum if it is second or second last irrespective of whether he gets the last turn. Whether the number of turns, K is even or odd i.e. whether the starting player gets the last turn, the second and second last values can always be forced, keeping the ball in the desired box if odd or the first or the last box respectively if even.

Case 2:

if K % 2 == 1:
    return target

If the number of turns, K is odd the starting player gets the last chance and thus get what he wants, as he can always redo what the other player did.

Case 3:

val = compare(A[1], A[-2], P)
for i in range(1, len(A)-1):
    comp = compare(A[i-1], A[i+1], not P)
    val = compare(val, comp, P)
return val

If the number of turns, K is even the other person gets the last chance thus the ball will land one box away from where the first player starts. This box can be predicted as the actions of the other player can be predicted. Since the second and the second last box can be forced we check if any of the possible landing boxes is better than what can be forced.

I know there are very few people who do competitive in python, I too am planning the move to C++ before graduating to Div_1 but are there any improvements I can make to my code? (Coding style or just simple logic changes?)

I messed it up during the competition case on line 19, I put N instead of K.

3 Likes
2

Can u check whats wrong in my solution, I kept a window size of 2/3 to find local minima/ maxima and then global maxima /minima accordingly
https://www.codechef.com/viewsolution/27591829

3

Sorry but you might have to wait for the editorial…
Not only am I bad at C++ but also new to this. i only posted this cause I thought my solution was cool.

4

In the question statement, it was given

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)

Now it implies that player can stay at the same box during his turn or go one place to left/ right this completely changes the solving method

5

Please read the question statement properly.

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)

This means the player has 2 options unless the ball is out of bounds

  1. Move the ball to the left (i.e. a[i - 1])
  2. Move the ball to the right (i.e. a[i + 1])

Thus it can’t be in the same place.

1 Like
6

When will he choose to stay at same box ?
You have any case when staying at same box will be better ?
Basically how can it affect final answer ?
I think they will always move to get optimal solution.

7

i misunderstood the problem and also considered, Arr[i] with A[i-1] and A[i+1],instead of just A[i-1] and A[i+1].

8

But logically I think none of then will keep ball at the same position even though its allowed.
Do you have a case when keeping ball at same position will help them ?
Moving it will be optimal even though no moving is allowed. Won’t it be like that ?

9

even if it can be at same place then too answer will be same. They will always move it to get optimal answer. Correct me if I am wrong.

10

when choosen i ,is already at min ,then second player will not execute its move.

11

How will it be at minimum position when second player is taking his turn?
The other person will have already moved it to some other place before in first person’s turn.

12

I assumed that you can’t not move. That is you can only move. That’s why you can always force the second and the second last place.

13

Same here but what I am saying is solution will be same in both case. It doesn’t matter whether its compulsory to move or not.

14

I guess we need to modify the answer a bit.

When p = 0, and k is even,
Then we are taking the min of only the two elements adjacent to i for each i from 1 to n(i.e a[i - 1], a[i + 1])
When the staying feature is added, we need to take the min of all three elements, i.e(a[i - 1], a[i], a[i + 1])

The same happens when p is 1 and k is even.

This is what I think according to my logic, correct me if I am worng

16

Okay I got one case when it fails. You are right. Solution will be modified in case we are allowed to keep ball at the same position.
1
9 2 0
1 1 1 2 1 3 1 1 1

17

The correct logic:-
Case 1:-

When p is 0 (Jafar) and k is odd
Answer always the answer will be the box containing maximum number

Case :2-

When p is 1 and k is odd

Answer will always be minimum numbered box

Case :3-

When p is 0 and k is even
Answer is maximum of (minimum of adjacent boxes of every box)
ans=max(ans,min(A[i-1],A([I+1]))

Last case

when P is 1 and k is even
Answer is minimum of(maximum of adjacent boxes for every box)
ans=min(ans,max(A[i-1],A[i+1]))

Solution link
Solution link

1 Like
18

If array is 2 3 8 1 9
If k is even and suppose we want maximum box no…
We would put in box 1 at stating…
Now next will not move then answer will be 1
Which is wrong…
We have selected 1 so where ever does the other player move we will get max
Optimally he will move to box 8
So we will pull it back to 1 since k is even it will be his last turn so it will end on 8…
Suppose k is 2
We will put ball in box 1…
He will not make any move
So ans will be 1…
So it will definately affect…

1 Like
19

My answers does give AC and I think Is the same as yours

20

Instead of making two cases everytime I have used the compare function and target to make it into one case

21

Cool…you are also right brother