You are not logged in. Please login at www.codechef.com to post your questions!

×

BUDDYNIM - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Greedy and Game Theory.

PROBLEM:

Given $N$ piles on table 1 and $M$ piles on table 2, Three players Alice, Bob, and Charlie play a game, with moves in order Charlie, Alice, and Bob respectively.

Charlie assign both of them to one table exactly, Alice first removes a stone from one or more stones from one of the pile at her table, then Bob removes one or more stones from one pile on his table.

The player unable to make a move loses.

SUPER QUICK EXPLANATION

  • Bob can only win, if, after removing empty piles from the input, both tables have exactly the same composition of piles.

EXPLANATION

First of all, remove the empty piles from both tables. (Constraints mention $A_i, B_i \geq 0$, which may include piles of size 0)

Suppose Only Alice and Bob are playing this game, with Alice removing stones from the first table while Bob removing stones from the second table. We can see, that the winning strategy is to remove exactly one stone at every turn. Winner will be Alice if she has strictly more stones than Bob Since Alice plays first.

But, with Charlie, the strategies change.

See, if at any point of Charlie's turn, if one table contains more stones than the other, Charlie will always assign Alice to that table, and Alice will always remove only one stone, thereby, can play moves equal to the number of stones at the table having more stones. Due to lack of stones, Bob loses, since his table always contain fewer stones than that of Alice.

So, Initial observation is that Bob can win only when both tables have the same number of stones.

Since Bob plays second, He will always remove the same number of stones as Alice removes in the same turn. But the question is, can he always remove the same number of stones as Alice. There's still a catch. What happens, even if both tables have the same number of stones but in the different composition.

It turns out, Alice can win in that case too.

Consider an example, Table 1 has 1,2,4 piles while table 2 has piles 2,5 Total number of stones is same, yet Alice can win. Charlie can assign Alice to the second table and Alice removes all stones from the pile with size 5. But Bob cannot remove 5 stones in any way. The number of coins at table 1 will be greater than that at table 2, hence, Alice will be assigned the first table after that always, and thus, will win.

So, in order to be able to remove the same number of coins as Alice, Bob needs all the piles to be exactly the same.

The proof is, that if tables have different compositions, the Charlie will repetitively assign Alice to the table having largest pile and Alice will remove the largest pile, till the number of stones at both tables is equal, or there is only one pile left on both tables.

Hence, If after removing all empty piles from the input, all remaining piles are same, the Bob can repeat the same moves as Alice, irrespective of Charlie's superpowers, and will win.

This can be easily checked using multiset or even an array or frequency array or whatever idea you may think of.

Time Complexity

Time complexity is $O(N*logN+M*logM)$ per test case. Log factors due to multiset operations.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 03 Nov, 16:35

taran_1407's gravatar image

6★taran_1407
3.7k2172
accept rate: 23%

edited 05 Nov, 01:10

admin's gravatar image

0★admin ♦♦
19.6k349497539


The second test case is wrong, Bob will win no matter how chalie and Alice play.

link

answered 07 Nov, 12:32

ujjk29's gravatar image

3★ujjk29
0
accept rate: 0%

1

Charlie will always assign Alice to 2nd table, while Alice will remove one stone at each step.

How can Bob win then?

(07 Nov, 21:11) taran_14076★
1

I'll play Charlie and Alice, you play Bob. Here goes:

Initial state: A:(1,2,4); B:(7)

Charlie: "Switch!"
state: A:(7); B:(1,2,4)
Alice: "So many stones, they're gone"
state: A:(); B:(1,2,4)

Your turn, Bob. Warning: Charlie's going to call out "Switch" again.

(08 Nov, 00:56) joffan5★

Random observation about the test data: I misread statement (and thought that Charlie only acts for first time after first round of moves by Alice and Bob) and because of that the problem became somewhat more tricky.

Here are some interesting cases:

  1. Initially Alice has no move at all - she loses.
  2. Alice only has one stone to remove, and Bob has single non-zero pile, so after first round there are no more stones and Charlie can't save Alice.

My solution has a few more "if X then Bob wins" compared to the model solution, yet it passes :)

link

answered 15 Nov, 21:25

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

Lucky I guess. xD

I believe it is simply not possible for the tester to anticipate every unique solution coming up in the contest, so that might be the reason for not getting WA.

Like, Assuming Charlie can assign table only at first move, He will not assign Alice the table with the lesser number of stones, so, Alice shall lose if and only if Number of stones on both tables is same.

Even if we assume that Charlie can assign table only at first move, Your solution https://www.codechef.com/viewsolution/21410139 fails on the case

1
1 1
0
1

(17 Nov, 07:53) taran_14076★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,677
×970
×572
×304
×52
×13

question asked: 03 Nov, 16:35

question was seen: 798 times

last updated: 17 Nov, 07:53