In July Long Challenge Div-1 (LoveMUFFINS).
There is a little confusion in my mind…
-> If any member(Says ‘A’) is offering some other member (Says ‘B’) exactly that amount of Dollar Bills that he(“B”) will surely get after (‘A’) Thrown Off the Roof. Then (‘B’) will Always Reject That Offer??
-> Can Any Member accept 0 Dollar Bill if He knows that He will Thrown Off the Roof if he reject That Offer??
Plz, Don’t Try To Share the Logic.
Just Help me With These Confusions. ( 
If I am not mistaken, I believe the answers to your questions are
-> Yes (“Therefore, during each vote and for each member, this member will vote against the currently proposed plan if they are sure that if this plan is rejected, they will gain at least as much loot as if it was accepted.”)
-> Yes (“We consider those who are thrown off the roof to gain exactly −10100 dollars in loot, since they will not live to see another day.”)
I am not Getting Correct ans for this Logic(Not Even a Single test Case) …
And i m Pretty Sure that it is not wrong…
When trying to work out the logic for a solution to this problem, I could not see how the example with K = 2, N = 5, M = 5 has an answer of 2.
Working backwards, when person 5 is the only 1 left, he obviously gives himself all the money. So he will reject every other proposed plan, as none are better than this.
When only 4 and 5 are left, both need to accept the proposed plan for it to be accepted. 5 will reject the solution whatever, so even if 4 offers himself 0 and 5 all the money, 4 will still be thrown off the roof.
When 3, 4 and 5 are left, 3 knows that 4 will accept anything, even 0, to avoid being thrown off the roof next time, while 5 will reject the proposed plan anyway. So 3 can give all the money to himself. 3 will reject every other proposed plan, as none are better than this.
When 2, 3, 4, 5 are left, at least 3 of them need to accept the solution. As 3 and 5 will reject everything, he cannot win, so will be thrown off the roof.
When all 5 are there, at least 3 of them need to accept the solution. As 3 and 5 will reject everything, he needs to offer a proposed plan acceptable to the others. He can offer 0 to 2 and 1 to 4, better than they receive under other plans, and keep the remaining 4 dollars for himself.
Can anyone please explain what is wrong with this argument, and why the answer is 2 not 4?
When 2,3,4,5 are left then Optimal distribution is (2->3,3->0,4->1,5->1).
When 1,2,3,4,5 are left then Optimal distribution is (1->2->0,3->1,4->2,5->0) or
(1->2->0,3->1,4->0,5->2).
In Both Cases possible distribution is there.
1: 5(+)
2: 5(-) X
3: 0(-) 0(+) 5(+)
4: 1(+) 1(+) 0(-) 3(+)
5: 2(+) 0(-) 1(+) 0(-) 2(+)
but later is more interesting …
consider k = 2, n = 7, m = 4;
1 : 4
2 : * X
3 : 0 0 4
4 : 1 1 0 2
5 : 0 2 1 0 1
6: 1 0 0 1 2 0
7 : 0 1 1 0 0 1 1
can you please tell me, what’s wrong in this ?
this is correct Distribution
1 : 4
2 : * X
3 : 0 0 4
4 : 1 1 0 2
5 : 0 2 1 0 1 or ( 2 0 1 0 1 ) Due to Both possible distribution.Any body can get 0 and other can get 2.
So Both Will Agree to take 1 in next iteration.
6: 1 1 0 1 0 1 (-> Now If you are Offering 2nd member just 1 coin then he will not reject the offer. Because He is not sure that he is the one which will get 2 coin not 0 if this man get rejected.)
7 : 0 0 1 0 1 2 0
Correct. that is the main trick here…
Thanks…
In the problem statement it says
Therefore, during each vote and for each member, this member will vote against the currently proposed plan if they are sure that if this plan is rejected, they will gain at least as much loot as if it was accepted.
I understood this to mean that if someone can gain X dollars in a round, he will never accept X dollars or less in an earlier round. From the examples provided above by tapan_goyal me17b016 and Iboris it appears that each person will reject a proposed plan if he cannot gain more in the next round, rather than ever.
I can try to explain you how 5th one will choose getting amount 1.
Let’s go in reverse way.
If only 5th one is left he will propose 5 and will get 5.
If 4th 5th is left he 4th one will be thrown off the roof and 5th one will get 5.
If 3rd 4th 5th left (now 4th knows he will be thrown if he disagrees to 3rd person)
So 3rd one will propose 5 0 0. And it will definitely get accepted.
Now if 2nd 3rd 4th 5th left. (now 4th and 5th knows they will get nothing if 2nd one is rejected)
So 2nd one will propose 3 0 1 1 and he will get accepted.
Now all 5 are left. (Now 3rd person knows he will get nothing if he rejects 1st person and 4th/5th knows they will get only 1).
So 1st one will propose 2 0 1 0 2 or 2 0 1 2 0 and he will be saved.
This seems correct. Correct me if I missed something.
Basically everyone acts in a way to maximize profit. It’s a deadlock situation. If they act differently, it’s their loss.