tag:blogger.com,1999:blog-29632375.post7515430297163050962..comments2023-06-19T19:45:40.281-07:00Comments on vexorian's blog: SRM 594: More slownessUnknownnoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-29632375.post-61983427520103563802013-10-15T11:24:47.989-07:002013-10-15T11:24:47.989-07:00I understand it needs to be 64 bits, but the gcd n...I understand it needs to be 64 bits, but the gcd normalization in fix is unnecessary. vector A(_A.begin(), _A.end()); would have worked instead of fix. Not trying to nitpick, if it works it works. Just enjoy trimming algorithms!JOmegaCVnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-80641317506611440192013-10-15T11:11:05.596-07:002013-10-15T11:11:05.596-07:00Sure, but I didn't have time to make the chang...Sure, but I didn't have time to make the changes before submitting my quick blog post.<br /><br /><br />Something like fix is needed so that the vector is of 64 bits integers. As long as you want the LCS to be independent code from the original problem. You can do the LCS and the multiplication at the same time.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-28662058194343935812013-10-15T11:09:45.029-07:002013-10-15T11:09:45.029-07:00I've been there.I've been there.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-76565832046716839122013-10-15T11:09:41.638-07:002013-10-15T11:09:41.638-07:00You don't need gcd or fix correct? You can ju...You don't need gcd or fix correct? You can just scale A by B[j] and B by A[i] without dividing by g?JOmegaCVnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-60040208832214636522013-10-15T11:09:37.530-07:002013-10-15T11:09:37.530-07:00No idea but it is probably slower. tie and make_tu...No idea but it is probably slower. tie and make_tuple() have 1-step recursion, so it probably cancels out the advantage over recursive gcd(). But maybe the optimizer turns it into int x=a, y=b; a = y; b = x%y; If that happens then it would be faster. Benchmarker needed.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-45050446137473335362013-10-15T10:58:52.176-07:002013-10-15T10:58:52.176-07:00Why don't you practice more 250 until your spe...Why don't you practice more 250 until your speed becomes good enough? ;)qwertynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-33692253364967744842013-10-15T10:54:27.011-07:002013-10-15T10:54:27.011-07:00Is your tie/make_tuple version of gcd faster than ...Is your tie/make_tuple version of gcd faster than "return b == 0 ? a : gcd(b, a % b)" ?2rfnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-79329430553473668732013-10-15T10:17:24.366-07:002013-10-15T10:17:24.366-07:00I too thought (more deliberately) of max-flow, but...I too thought (more deliberately) of max-flow, but it didn't come more naturally. What is a right direction to think and see it reduce to max-flow easily ?Vijaynoreply@blogger.com