How to Solve 'A Simple Game' from Nov challenge 2019

general
,
#1

Now that this problem is removed from Long challenge, Can someone tell me, how to solve this problem?

I spent like an entire day and couldn’t crack it (I lack GameTheory a lot). If possible please explain me the logic in simple terms, as I find Game theory to be hardest (for me :frowning: ) to understand.

#2

Btw, why was it removed ?

#3

Turned out to be the same as one from Codeforces: Copied Problem in November Long Challenge

3 Likes
#4

Oh :face_with_hand_over_mouth:

2 Likes
#5


Just sort the rows with odd no of coins by middle coin value

#6

https://codeforces.com/blog/entry/10629

#8

https://codeforces.com/problemset/problem/388/C
This was the question.

#9

can you please elaborate ??

#12

The solution is quiet simple
Look if a row is even then in that row chef can eat from starting to n/2
ex- n=6 ,1 3 4 5 6 8 in any case chef can eat only 1 3 4
the question stucks on the part when n is odd
if n=5 ,1 3 4 5 6 then chef can eat 1 3 and ramsay 5 and 6 but the one who will eat 5 will have max value so the one who start first will eat more.
now solution part
consider three rows
n=4 1,4,5,2
n=5,1,2,7,3,4
n=3,1,3,4
for first row chef can eat n/2 part and ramsay will eat n/2 so chef=1+4
for second row chef will eat 1+2 and ramsay 3+4 for sure but who will eat 7?(leave it for now)
for third row chef can eat 1 and ramsay 4 but who will eat 3?(leave it for now)
now
you want to maximise for chef so have a vector put 7 and 3 in it.
now sort it in descending order since both of them are trying to maximise there value hence if chef takes 7 because its his chance first then ramsey will take 3 .
if sorted vector contain 7 6 5 4
then if chef start take 7 ramsey takes 6 after that chef takes 5 ramsey 4
conclusion
the logic is straight forward if row is even they cant do anything both of them can eat n/2 part
if row is odd then among multiple odd rows chef will try to eat the row in which the middle element is having higher value.
If you are still having doubt you can ask :smiley:

7 Likes
#13

Thanks :slight_smile: [10 char limit] Got it. Nice problem, TBH.

1 Like
#14

hope u got it ?

1 Like
#15

I didnt understand the odd part .can you explain it again.And why cant you sort at even part to get maximum value.

#16

It’s so sad they had to remove this problem :frowning:

I really enjoyed cracking this problem

Btw, Why was it removed?

1 Like
#17

i also solved that they said a similar problem is there in codeforces. but dont worry learning is important

2 Likes
#18

very nicely explained… :slight_smile:

1 Like
#19

thanks …

#20

in such case where odd coins in row, then chef have to take the last(middle) coin and after that in another row rasmi take the last(middle) coin. chef have to look for bigger value of middle coin so ,he must choose that rows where middle coins are of bigger value.you have to take a vactor push_back middle coins in it an short in then reverse it after add (n+1)/2 part of your reversed vector in your total sum.

i think now you got it:slightly_smiling_face::slightly_smiling_face:

#21

what does it mean [10 char limit] . I have seen it earlier many times.

1 Like
#22

discuss doesn’t allow comment of less than 10 char. don’t know why @mnithinkk did this.

#23

Can you please prove that this is the optimal strategy ? Like why shouldn’t Ramsey choose from other pile ? Why the same pile ?

1 Like