tag:blogger.com,1999:blog-4115025577315673827.post2093791889205526302..comments2020-05-25T11:14:44.467+05:30Comments on CSE Blog - quant, math, computer science puzzles: Original Problem : ATM Money Withdrawal PuzzlePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-4115025577315673827.post-71608019846580173112016-06-12T19:20:56.909+05:302016-06-12T19:20:56.909+05:30The difference will appear when the number N is la...The difference will appear when the number N is large. You should make the table longer and it will be clear.Anonymoushttps://www.blogger.com/profile/14657606750531452223noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-14381355720950558652012-10-21T08:50:43.998+05:302012-10-21T08:50:43.998+05:30I did not understand the question. How do you comp...I did not understand the question. How do you compare two strategies? For eg. N=2, strat1: Just withdraw 1 rupee. strat2: Try withdrawing 2 rupee, if yes then done, otherwise withdraw 1 rupee from next day.<br /><br />So we have the comparison<br /><br />---------- Strat 1 Strat 2 <br />limit =1 days = 2 days = 3<br />limit =2 days = 2 days = 1<br /><br />So which strategy is better? Strat 1 is better if we want the worst case scenario to be the best. Both strats are equal if we assume uniform probability distribution on limit and want minimum expected time. The situation becomes more complicated if we increase N, coz the number of strategies increases exponentially and how to compare two strategies is not so obvious at all.sidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55192558594804657722012-07-19T17:17:30.354+05:302012-07-19T17:17:30.354+05:30Let limit be l, amount to be withdrawn be N, N/l i...Let limit be l, amount to be withdrawn be N, N/l is say x and as it happens in most cases, l is greater than sqrt(N) <br /><br />My solution: N - l + ceiling(x) -1<br /><br />Solution by Nick: <br />log2(N) + ceiling(x-1)<br />[Nick's solution: using binary search algorithm to find the limit. So we can find the limit in log2(N). After finding the limit we can withdraw the sum in ceiling((N-limit)/limit) additional days. So altogether we will require log2(N) + ceiling((N-limit)/limit) days]<br /><br />Solution by bose's diary: <br />log2(limit) +2*x-3<br />[Check 1, Check 2, Check 4, and so on, till you are refused by ATM Machine. So, in the worst case, you would have drawn "limit" amount and you would take log2 (limit/2) days.<br />The rest would be withdrawn in the worst case at limit/2. So, number of days: log2 (limit/2) +(N-limit)*2/limit = log2(limit) +2*x-3. There is a small error in the solution given by bose's diary]Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3145996551749843572012-07-19T17:00:53.847+05:302012-07-19T17:00:53.847+05:30Interesting solutions. Thanks for providing better...Interesting solutions. Thanks for providing better than mine. Can we prove which one is the optimal?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-76044095922579514302012-02-21T12:24:09.773+05:302012-02-21T12:24:09.773+05:30I really appreciate the kind of topics you post he...I really appreciate the kind of topics you post here. Thanks for sharing information that is actually helpful for me.eclipsehttps://www.blogger.com/profile/00412591950031213219noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-77451228205762279452012-02-18T11:14:07.480+05:302012-02-18T11:14:07.480+05:30I think the first task is to find the limit which ...I think the first task is to find the limit which can be found in log2(N) trials. It is also true that after this many trial I will already have at least limit money already with me.<br />For an example let N=100<br />limit = 10<br />1st try = 50(NS - No Success)<br />2nd - 25(NS)<br />3rd - 12(NS)<br />4th - 6(S- Success)<br />5th - 9(S)<br />6th - 11(NS) <br />7th - 10(S)<br />In 7 trials I know the limit and also I have 25/- already.<br />(100-25)/10 ~ 8 trials.<br />So, 15 trials.<br />No. of trials = log2(N)+ (N-limit)/limit.<br />Also, let a is the no of trials required, then a(a+1)/2 = N is the equation to be solved for the solution. a = (sqrt(1+8N)-1)/2Rakeshhttps://www.blogger.com/profile/07043855126262381716noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9823700192696642232012-02-07T17:34:54.578+05:302012-02-07T17:34:54.578+05:30For the other way with 1,a,a^2 etc.:
check N/1,N/...For the other way with 1,a,a^2 etc.:<br /><br />check N/1,N/a,N/a^2, etc. until you reach a point where the withdrawal works.<br /><br />let N/a^(k+1) <= l < N/a^k.<br /><br />Once you get this N/a^(k+1) (call this l'), just use this instead of finding out l exactly.<br /><br />Days required, D = (k + 1) + N/l' - 1 = k + N/l'.<br /><br />l/l' <= a. So N/l' <= Na/l = ax.<br /><br />So D <= logx/loga + ax.<br /><br />a can be taken as any arbitrarily small constant (strictly more than 1 of course, say 1 + epsilon), for constant a the second term clearly dominates.<br /><br />So we can come arbitrarily close to a factor of 1 in x.wonderwicehttps://www.blogger.com/profile/11745210084404197781noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55465314396152245732012-02-07T14:58:53.534+05:302012-02-07T14:58:53.534+05:30Call the limit 'l'. Call N/l as x. Obvious...Call the limit 'l'. Call N/l as x. Obviously, x is the best we can do, so the question really is how well we can approach x in the worst case. In the case of checking 1, 2, 4, etc. it is hard to get good constant factors over x without finding out l pretty well (eg. if we find only highest power of 2 that does not exceed l, we can at best get a factor of 2x), so the binary search to find the limit seems to make more sense. In this case, suppose we find l completely first. Worst case is that l = N/(2^a) + 1 for some a. Here we will find the value of l after a (to find first power of 2 after dividing by which we can withdraw) + log (N/2^a)) (to query values between this and its double to find where l lies) queries = logN queries, and will only have removed 2l-1 from N after doing all this. Time taken here would be logN + (N-2l+1)/l, which is roughly logN + x - 2. This is quite good in terms of x, when log N is much smaller than x. Only problem is where log N is much more than x. However, this is easily dealt with. For log N to be more than x, l would have to exceed N/logN. While doing the binary search, if the first point where we are actually able to withdraw is more than this, then don't waste time trying to find exact value of l. Instead, use what we have already found and withdraw all the money using that limit. Of course, total number of days is limited by logN here, but even in terms of x, we have a limit of 2x for even these 'bad' cases.wonderwicehttps://www.blogger.com/profile/11745210084404197781noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-8979617070428480172012-02-07T13:08:26.901+05:302012-02-07T13:08:26.901+05:30first day i withdraw n/2 rupees.if i get it then i...first day i withdraw n/2 rupees.if i get it then i will increase the amount by n/4 else decrease it by n/4.basically i will use binary search technique.anonymous456https://www.blogger.com/profile/14397089236763273973noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30435030235321126192012-02-07T00:15:01.917+05:302012-02-07T00:15:01.917+05:30One of the ways, in which the number of trials can...One of the ways, in which the number of trials can be reduced is to use binary search for the limit, instead of linear search, i.e., In 1st attempt, try to take out N/2, if it fails, try N/4, otherwise try N/2 again and you are done. This method will give better result than the two methods described in the problem.AgMayhttps://www.blogger.com/profile/17281780473315418149noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-44088026524880740902012-02-06T23:57:21.052+05:302012-02-06T23:57:21.052+05:30I could think of a strategy that looks slightly be...I could think of a strategy that looks slightly better than the ones described in your post:<br />1. check 1, check 2, check 4,...., till you are refused by the ATM machine. Note that you can do it for (log limit +1) days. By that time you would have accumulated 2*limit - 1 rupees. For the remaining rupees N-2*limit + 1, draw at the rate last accepted by the ATM. That'll take you at the most 2*(N-2*limit+1)/limit days. So in total it takes you (log limit +1) + 2*(N-2*limit+1)/limit days. logarithms are to the base 2. For moderate value of limit, this seems to be a little better...The idea is to use binary search to know the limit. From there on you can draw money at the rate of limit per day.bose's diaryhttps://www.blogger.com/profile/11297317890280319075noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-28594361899135243562012-02-06T23:56:59.076+05:302012-02-06T23:56:59.076+05:30I could think of a strategy that looks slightly be...I could think of a strategy that looks slightly better than the ones described in your post:<br />1. check 1, check 2, check 4,...., till you are refused by the ATM machine. Note that you can do it for (log limit +1) days. By that time you would have accumulated 2*limit - 1 rupees. For the remaining rupees N-2*limit + 1, draw at the rate last accepted by the ATM. That'll take you at the most 2*(N-2*limit+1)/limit days. So in total it takes you (log limit +1) + 2*(N-2*limit+1)/limit days. logarithms are to the base 2. For moderate value of limit, this seems to be a little better...The idea is to use binary search to know the limit. From there on you can draw money at the rate of limit per day.bose's diaryhttps://www.blogger.com/profile/11297317890280319075noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-42050626951451216612012-02-06T18:09:18.353+05:302012-02-06T18:09:18.353+05:30using binary search algorithm to find the limit .....using binary search algorithm to find the limit ........ so we can find the limit in log2(n) ......... after finding the limit we can withdraw the sum in ceiling((n-limit)/limit) additional days ...........so altogether we will require log2(n)+ceiling((n-limit)/limit) days............nickhttps://www.blogger.com/profile/13638852514996115837noreply@blogger.com