tag:blogger.com,1999:blog-6314876008291942531.post4895786391131402328..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: maximize coinsUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-30533128389680454972011-08-24T11:46:28.751-07:002011-08-24T11:46:28.751-07:00The solution you presented looks like an O(n^2). H...The solution you presented looks like an O(n^2). However, this problem can be done in O(n log n).<br /><br />1. Observe that whenever the coin of highest value is available at one of the ends of the line, it is always optimal to take this coin. This can be easily proven by induction.<br /><br />2. Observe that it suffices to compute the optimum value of a situation i.e. the maximum amount of (money you get minus money your opponent gets). There are easy formulas converting ROI to value and back.<br /><br />3. Consider the following O(n log n) that reduces the computation of the value V of a situation to a computation of the a value V' of a similar smaller situation. The are two following cases.<br /><br />a) The coin of highest value v is available at one of the ends. Then V=v-V', where V' is obtained from V by removing the available coin.<br /><br />b) The coin of highest value v is between two coins of values a and b, respectively. The V=V', where V' is obtained from V by replacing the subsequence (a,v,b) by (a+b-v).<br /><br />4. The computation ends after at most n steps (we reach an empty situation with value 0).Anonymoushttps://www.blogger.com/profile/16234740155371832738noreply@blogger.com