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

×

BANROB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kirill
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh

DIFFICULTY:

Easy

PREREQUISITES:

Math, Binary Exponentiation, Sum of Geometric Progression

PROBLEM:

Given that two thieves have $1$ billion to divide amongst them according to a particular method, report the amounts both the thieves will receive upon division. The particular method here is that after a certain amount of time $t$, only (1 Billion * $p^t$) amount of money can be taken, where $0 \leq p \leq 1$. Also, there are only $M$ minutes to divide the stolen money and escape.

EXPLANATION:

Subtask 1
Let us start by taking an example. Let $p$ = 0.5 and $t$ = 4. We not proceed minute by minute.

  • First minute
    Money left to take = $10^9$.
    Thief 1 to propose a plan.

  • Second minute
    Money left to take = $10^9 * 0.5$.
    Thief 2 to propose a plan.

  • Third minute
    Money left to take = $10^9 * 0.5^2$.
    Thief 1 to propose a plan.

  • Fourth minute
    Money left to take = $10^9 * 0.5^3$.
    Thief 2 to propose a plan.

After the fourth minute, both the thieves will lose all the money. So, let's go back in time minute by minute and see what the optimal division would be.

  • If in the fourth minute, Thief 2 proposes a division of $0$ and $10^9 * 0.5^3$ respectively, Thief 1 will accept it.
  • If in the third minute, Thief 1 proposes a division of $10^9 * 0.5^2 - (10^9 * 0.5^3)$ and $10^9 * 0.5^3$ respectively, Thief 2 will accept it.
  • If in the second minute, Thief 2 proposes a division of $10^9 * 0.5 - (10^9 * 0.5^2) + (10^9 * 0.5^3)$ and $(10^9 * 0.5^2) - (10^9 * 0.5^3)$ respectively, Thief 1 will accept it.
  • Finally, if in the second minute, Thief 1 proposes a division of $10^9 - (10^9 * 0.5) + (10^9 * 0.5^2) - (10^9 * 0.5^3)$ and $(10^9 * 0.5) - (10^9 * 0.5^2) + (10^9 * 0.5^3)$ respectively, Thief 2 will accept it.

The acceptances will be because the theif accepting the plan can in no way gain more money in the future than being offered at that point in time. Please note this point in the question:
"Each thief wants to maximize his earnings, but if there are two plans with the same amounts for him, he would choose the one which leads to a larger total amount of stolen dollars."

We can make a very important observation here. The amount that Thief 1 will gain is given by:
$val$ = $10^9(p^0 - p^1 + p^2 - p^3 \dots p^{M-1})$. Thus, the amount that Thief 2 gets is $10^9 - val$.

Subtask 2
If we observe the terms inside the bracket in the expression we got for $val$ in subtask 1, we can see that it is basically the summation of terms of a Geometric Progression (GP).
The GP is: $1$, $-p$, $p^2$, $-p^3$, $\dots$

We common ratio $r$ = $-p$ and the first term of GP $a$ = $1$. The formula to calculate the sum of first $n$ terms of a GP is well known:
$S = \frac{a(r^n - 1)}{r-1}$

Thus, in this case, $S = \frac{((-p)^M - 1)}{(-p)-1}$.
This will work in $\mathcal{O}(M)$ with linear exponentiation.

Subtask 3
The solution of subtask 2 can be optimised by using binary exponentiation to calculate $(-p)^M$. This will allow us to compute the sum of the GP in $\mathcal{O}(\log M)$.

COMPLEXITY:

$\mathcal{O}(\log M)$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 05 Sep '15, 17:34

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 03 Oct '15, 11:03

kevinsogo's gravatar image

7★kevinsogo
1.7k586142


link

answered 14 Sep '15, 17:21

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

For those who couldn't understand the question, I'll explain it with a test case. Suppose p=0.6, M = 5.

t=0 -> money -> 1 billion. Here Chef will decide(make a decision).

t=1-> money -> 0.6 billion. Here other will decide.

t=2 -> money -> 0.36 billion. Here Chef will decide.

t=3 -> money -> 0.216 billion. Here other will decide.

t=4 -> money -> 0.1296 billion. Here Chef will decide.

If the situation comes to t=4, it is obvious that chef will take all the 0.1296 billion, and other thief will agree.

So, before this time (at t=3), the other thief will decide to give Chef 0.1296 billion, so that he will accept because in any case that is the maximum amount chef can get. So other thief will get (0.216-0.1296) = 0.0864 billion.

So, before this time (at t=2), the Chef will decide to give other thief 0.0864 billion, so that he will accept because in any case that is the maximum amount other thief can get. So chef will get (0.36-0.0864) = 0.2736 billion.

So, before this time (at t=1), the other thief will decide to give Chef 0.0.2736 billion, so that he will accept because in any case that is the maximum amount chef can get. So other thief will get (0.6-0.2736) = 0.3264 billion.

So, before this time (at t=0), the Chef will decide to give other thief 0.3264 billion, so that he will accept because in any case that is the maximum amount other thief can get. So chef will get (1-0.3264) = 0.6736 billion.

Finally, you will get a G.P. and then it can be solved easily.

Code https://www.codechef.com/viewsolution/8032865

link

answered 14 Sep '15, 18:56

rishivikram's gravatar image

5★rishivikram
492110
accept rate: 14%

Well, for the fourth test case:

t = 0 -> p = $1000\cdot10^6$

t = 1 -> p = $500\cdot10^6$

t = 2 -> p = $250\cdot10^6$

t = 3 -> p = $125\cdot10^6$

I started backwards. At the third minute it is the second thief turn, right. Then the gold that is left is 125000000. Which means that if the second thief offers 0 125000000, the Chef should accept it. Otherwise. at the fourth minute, the Chef will take 0 as well. And we know that - "Each thief wants to maximize his earnings, but if there are two plans with the same amounts for him, he would choose the one which leads to a larger total amount of stolen dollars.".

So at the third minute the Chef would accept the plan 0 125000000.

Then, at the second minute, if the Chef offered the plan 125000000 125000000, the second thief would accept it, because the total amount of stolen dollars is more. If the Chef tried to offer more to himself and less for the second thief, the second thief would reject the offer, and receive more at the next turn.

Then again, at the first minute, if the second thief offered the plan 125000000 375000000, the Chef would accept it, because of the total-amount-rule.

At last, at the beginning the Chef will propose the plan 625000000 375000000, and the second thief will accept it, because of the total-amount-rule.

link

answered 14 Sep '15, 18:29

aragar's gravatar image

4★aragar
995
accept rate: 7%

edited 14 Sep '15, 18:32

Check this video and subscribe to the channel for more video editorials.. https://www.youtube.com/watch?v=KaucPRyejis Hope this helps..

link

answered 14 Sep '15, 22:23

ankit15's gravatar image

2★ankit15
412
accept rate: 0%

This is really a great step. Video editorials are always useful! :)

(14 Sep '15, 23:41) kay_kay4★

Let $a(M)$,$b(M)$ be the proportions of the money the first and second thief obtain given $M$ minutes to decide.

Clearly $a(1)=1$,$b(1)=0$ as with no time left the second thief will agree to anything to avoid arrest.

For general M, the first thief thinks:

If the other guy rejects my offer, I will get $pb(M−1)$ and he $pa(M−1)$ since we play the same game with less money, less time, and roles switched.

He will reject especially if I offer him less than $pa(M−1)$.

He will greedily accept if I offer more than $pa(M−1)$ but that would not be optimal for me; he will also accept by the tie-breaking rule if I offer exactly $pa(M−1)$, which will leave $1−pa(M−1)$ for me, certainly at least as much as $pb(M−1)$.


We obtain the recursion

$$\large a(1)=1,a(M)=1−pa(M-1)$$ $$\large a(M)=1-p(1-pa(M-2))=1-p+p^2a(M-2)$$ $$\large a(M)=1-p+p^2-p^3+...+(-p)^Ma(1)$$ But Since $a(1)=1$, $$\large a(M)=1-p+p^2-p^3+...+(-p)^M$$ $$\large a(M)=\dfrac{1-(-p)^M}{1-(-p)}$$


$$\large b(M)=1-a(M)$$ $$\large b(M)=1-\dfrac{1-(-p)^M}{1+p}=\frac{p+(-p)^M}{1+p}.$$

So, After multiply with $10^9$ we get our final $a(M)$ and $b(M)$.

Link to the solution:https://www.codechef.com/viewsolution/8037182

link

answered 16 Sep '15, 16:57

vidhan13j07's gravatar image

4★vidhan13j07
313
accept rate: 0%

edited 16 Sep '15, 17:00

Can anyone help me out? suppose the test cases are:

4

1 0.5

2 0.5

3 0.5

4 0.5

for 1 0.5 output --> 10^9 0.0 ... ok .

2 0.5 output--> 510^8 510^8 ... ok

3 0.5 output --> 750000000.0000 250000000.0000 --> why???? .. see chef has 750000000.0 i.e decision is made at t=1 . And chef offer other thief 250000000.0 because at the beginning of 3rd min other thief will be able to stole only 250000000.0 money .BUT why other thief agreed to chef ? I mean if other thief would not have agreed to chef then he will offer 500000000.0 to chef after the beginning of the 2nd minute and able to keep 500000000.0 with himself . And in that case chef also would not able declined to other thief because after 2nd min both of them will have reduce amount of money .

same problem with 4 0.5 --> output--> 625000000.0000 375000000.0000 ??? again decision made at beginning of 1st minute. Why other thief always agreed to chef ?. I doing something wrong . Please correct me

link

answered 14 Sep '15, 17:53

mra1709's gravatar image

1★mra1709
11
accept rate: 0%

edited 14 Sep '15, 17:57

1

@aragar .. Thanks a lot . I was thinking after t time both can (10^9 X p^t) amount of money . But actually total money both can take away is (10^9 X p^t) .

(14 Sep '15, 18:44) mra17091★

I am little bit confuse in this problem, in the problem statement it is written that:
"Each thief wants to maximize his earnings, but if there are two plans with the same amounts for him, he would choose the one which leads to a larger total amount of stolen dollars"
Also chef has opportunity to propose plan first that means he must take advantage of his turn
Now lets suppose M is odd:
then last turn is of chef and other has to accept his plan, correct ?
lets say : M=7,p,B,(x,y) where (0<=p<=1),B=>Bllion,x=amt amassed by chef and y= amt amassed by other
at t=0 chef proposes (B,0)
at t=1 other proposes (0,Bp)
at t=2 chef proposes (B
p^2,0)
at t=3 other proposes (0,Bp^3)
at t=4 chef proposes (B
p^4,0)
at t=5 other proposes (0,Bp^5)
at t=6 chef proposes (B
p^6,0)
at t=7 they have (0,0)
if other accept his plan then chef will get (B,0) (Maximum amt. stolen){because other have same amt. in all plans i.e 0} right ? but why he should accept his plan this question arises, because chef rejects all his plans bcoz he knew that at last he is going to propose last plan and other have to accept it then amt amassed by chef should be 1 Billion.
If M is even now chef knew that at last other is going to prposes plan and he(chef) have to accept it so chef will propose him plan (B-Bp,Bp).. can any body tell me am i wrong if yes then why ?

link

answered 14 Sep '15, 19:56

yugrockz's gravatar image

3★yugrockz
1
accept rate: 0%

Here is a simple solution.

At time t-1, the thief(thief 1) who has the chance would divide the money in his favor. That is the division would be {max*p^(t-1),0}.

Keeping this in mind the other thief(thief2) will divide the money as {maxp^(t-2)-maxp^(t-1), (max*p^(t-1)} in the previous chance as the sum of money will be more and thief 1 will be getting the amount he wants in the last chance.

The same logic goes on every chance and the chef would hence choose the division as ( max –maxp+maxp^2-maxp^3…… maxp^(t-1), maxp-maxp^2+maxp^3…… maxp^(t-1))

This forms a simple geometric progression which can be calculated using G.P.formula. https://www.codechef.com/viewsolution/8165228

link

answered 14 Sep '15, 21:09

nik_iit007's gravatar image

3★nik_iit007
1
accept rate: 0%

edited 14 Sep '15, 21:15

What is O(logM)

link

answered 15 Sep '15, 14:15

h4cktivist's gravatar image

3★h4cktivist
1
accept rate: 0%

I think there is some problem with the Editorialist's solution. I was thinking on the same grounds but I don't know why it's showing such output.

link

answered 18 Oct '15, 22:17

vae_victis's gravatar image

2★vae_victis
1
accept rate: 0%

https://www.codechef.com/viewsolution/10856885 Can anybody tell me why is this not working?

link

answered 19 Jul '16, 20:31

username_foo's gravatar image

2★username_foo
1
accept rate: 0%

in printf use precision upto 6 decimal place ,i.e., %0.6lf.. Here's your corrected code https://www.codechef.com/viewsolution/10857144

(19 Jul '16, 21:20) an26093★
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:

×15,852
×3,820
×890
×166
×158

question asked: 05 Sep '15, 17:34

question was seen: 5,704 times

last updated: 19 Jul '16, 21:21