During the contest a contestant (I will not say who : ) makes the following clarification request:
Can we borrow more than 1 bottle at a time? And is it true that we are allowed to borrow bottle(s) only in the beginning?
I shall not put my answers here. Those who get Accepted should be able to answer the two questions quite easily. For those who don't know how to solve this task, thinking about the two questions above may help~
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
i got the solution by
1-1
2-3
3-4
4-6
5-7
6-9
7-10
etc
this is pretty trivial
Can someone tell me the DP solution or the recurrence relation.
f0(n) = n + f0(n/3); if 0 bottles borrowed
f1(n-1) = n-1 + f1(n/3); if 1 bottles borrowed
f2(n-1) = n-2 + f2(n/3); if 2 bottles borrowed
f(n)=max(f0(n),f1(n),f2(n));
is that correct or is there some simpler recurrence or DP
Last edited by temper_3243 on Mon Jan 01, 2007 1:39 pm, edited 1 time in total.
temper_3243 wrote:is there some simpler recurrence or DP
If you think about the two questions I posted above, then you shall get an easy relation. Thinking more deeply will even give you a very very fast method. (Don't post it here because it is a big spoiler!!!)
About your recurrence: what is "n"? If it is the number of cola you've bought, then where does the "n-1", "n-2" come from?
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
During the contest a contestant (I will not say who : ) makes the following clarification request:
Quote:
Can we borrow more than 1 bottle at a time? And is it true that we are allowed to borrow bottle(s) only in the beginning?
I shall not put my answers here. Those who get Accepted should be able to answer the two questions quite easily. For those who don't know how to solve this task, thinking about the two questions above may help~
Btw, it's me who sent those questions... Thx for the answers... AC already...
temper_3243 wrote:Hints needed , do we have a recurrence relation for this problem ?
Yes. And that's not hard.
A (maybe) silly hint: Even if you decide to borrow k bottles, it doesn't mean that you have to use all of them!!! You may actually borrow many bottles, use none of them at all, and then return them all finally.
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
if you think about the two questions I posted above, then you shall get an easy relation.
1. You are allowed to borrow bottles --- you can borrow at any stage. But since each state is dependent only on its previous state, it makes sense to get all the bottles you need as early as possible. Having more bottles at one stage means you can get more colas in the succeeding stages.
2. How many bottles might you need? More importantly, how many bottles will you be able to give back? You will always have at least one bottle that you can return at the end. You migth also have two bottles. But you will never have three or more bottles to return. If you had three or more, you would be able to use them to get more colas until you had less than three.
Once I realized these facts, the solution was clear. Hope this helps.
It's been almost a month since this task is available here. I shall say a bit more about this task.
MAK wrote:you can borrow at any stage
That's right~ And as I have said, you do NOT need to use all borrowed bottles. You may also want to borrow bottles only when you are "trading in bottles for colas". But that's basically the same as borrowing all bottles you need at the beginning. (Why?)
Also,
MAK wrote:You migth also have (to borrow) two bottles.
Please name one such situation.
There is actually a direct formula (without any simulation) to this task. And that is rather obvious. But please don't post the formula here!!!
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
MAK wrote:
You migth also have (to borrow) two bottles.
I actually wrote
You migth also have two bottles.
(sorry for the typo )
What I meant was that at the end of the simulation you can have either one or two empty bottles left, but never three. So you can either borrow one or two bottles and still be able to return them at the end. If you borrow three or more, you will never be able to return any more than two. In my solution I just simulated the process for three cases. The first case is where we don't borrow any extra bottles. The second is where we borrow only one bottle (we can be sure that there will be at least one bottle left so we will be able to return it). The third case is where we try with two extra bottles. Here we also have to check whether we actually have two empty bottles at the end that we can return. The maximum yield of colas from all three cases is the answer.
This was the first solution that occurred to me from reading the problem statement, and it got accepted during the contest. I truly don't know whether there are any cases where you actually need to borrow two empty bottles, but from the problem statement it seems possible that you can borrow two and still be able to give them back, so handled that case too. If there are no cases like that, no harm done.