tag:blogger.com,1999:blog-7656516316687795220.post8799777962266368968..comments2022-04-09T11:55:14.271-07:00Comments on I solved a problem: Maximum Triangle Area (Part 2)Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-7656516316687795220.post-26448343535922594272021-03-07T16:38:46.920-08:002021-03-07T16:38:46.920-08:00Here, dp[oldCount + 1][oldSum + cur] += dp[oldCoun...Here, dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1); because, after having a permutation of oldCount I can add a new person in this permutation in (oldCount + 1) possible positions. So we're multiplying (oldCount + 1), and probability of being selected at (oldCount + 1)th person from (n - oldCount) person is 1 / (n - oldCount). So we're multiplying this also. All f(count, sum) can be counted in O(n * n * p). As we're iterating over all the blockers. So the overall algorithm will be O(n ^3 * p).Anonymoushttps://www.blogger.com/profile/17551253042820969275noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-64932153653608146502021-03-07T16:38:31.247-08:002021-03-07T16:38:31.247-08:00After second part, our algorithm became something ...<br />After second part, our algorithm became something like this -<br />for each 0 <= i < n, initialize A = Pi, B = P(i + 1) % n, C = P(i + 2) % n, then move C counter clockwise until area non-decreasing, move B to its adjacent point counter clockwise, if area non-decreasing, move C again until area non decreasing and so on. You will get the maximum area for each A and output the maximum of these areas. For a given point starting point Pi, if the maximum area is ABC. We can say ABC is 'stable' triangle for A, in other word s(pi, Pi + 1, Pi + 2) = ABC, that means we cannot move B or C any further by not decreasing the area.Anonymoushttps://www.blogger.com/profile/17551253042820969275noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-23377139253737275112012-02-03T05:46:34.420-08:002012-02-03T05:46:34.420-08:00CC'B' was added to the left side of inequa...CC'B' was added to the left side of inequality and CC'B was added to the right one. B and B' are different points. Or am I missing somewhere a proof that these areas are equal?Urbanowiczhttps://www.blogger.com/profile/09641334968422116645noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-35455099849526225752012-02-03T05:05:28.328-08:002012-02-03T05:05:28.328-08:00Adding CC'B to both sides.Adding CC'B to both sides.Arifhttps://www.blogger.com/profile/05427068343601711364noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-86268352227738638732012-02-03T04:06:03.898-08:002012-02-03T04:06:03.898-08:00A question regarding [4]. Could you explain the fi...A question regarding [4]. Could you explain the first step (written below)?<br /><br />> And, AB'C' > AB'C <br />> => AB'C' + CC'B' > AB'C + CC'BUrbanowiczhttps://www.blogger.com/profile/09641334968422116645noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-25066996402047238282011-08-19T18:13:51.248-07:002011-08-19T18:13:51.248-07:00Thanks. I'll tr to post it soon.Thanks. I'll tr to post it soon.Arifhttps://www.blogger.com/profile/05427068343601711364noreply@blogger.comtag:blogger.com,1999:blog-7656516316687795220.post-27403881574706734802011-08-19T09:31:13.376-07:002011-08-19T09:31:13.376-07:00Great analysis! I am loving it so much! Waiting fo...Great analysis! I am loving it so much! Waiting for the part 3.Sabbir Yousuf Sannyhttps://www.blogger.com/profile/06850218318798376482noreply@blogger.com