tag:blogger.com,1999:blog-786333285568106173.post5708362875943163336..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: 3SUM PuzzleMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-786333285568106173.post-24714987006681446812010-12-22T12:26:11.470-05:002010-12-22T12:26:11.470-05:00Hello, I am Andreja Ilic from Serbia. If I underst...Hello, I am Andreja Ilic from Serbia. If I understood right, we can divide number in three groups: zeros, positive and negative. The most complex case is - take two positive numbers and one negative number. <br /><br />We can solve this in the following way: For fixed negative number -z, we are going to check for every positive number x is there -z + x in positive numbers. So if we sort numbers, when we move from x to bigger one, the number -z + x also moves right.Andrejahttps://www.blogger.com/profile/06374286963743369525noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-34013090416382572852010-12-22T12:25:36.714-05:002010-12-22T12:25:36.714-05:00Hello, I am Andreja Ilic from Serbia. If I underst...Hello, I am Andreja Ilic from Serbia. If I understood right, we can divide number in three groups: zeros, positive and negative. The most complex case is - take two positive numbers and one negative number. <br /><br />We can solve this in the following way: For fixed negative number -z, we are going to check for every positive number x is there -z + x in positive numbers. So if we sort numbers, when we move from x to bigger one, the number -z + x also moves right. And this is O(n^2)...Andrejahttps://www.blogger.com/profile/06374286963743369525noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-50516725162956099972010-07-02T12:38:23.784-04:002010-07-02T12:38:23.784-04:00FFT can multiply two polynomials of degree d in ti...FFT can multiply two polynomials of degree d in time O(d lg d). If you have a set S mod p, make a polynomial of degree p, where x^i has coefficient 1 if i is in S mod p, and 0 otherwise.<br /><br />Multiplying the polynomials, you obtain a nonzero coefficient only for values x that can be written as a+b, with a and b in S. You take all nonzero coefficients of the result modulo p, and that precisely (S+S)mod p.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-3873026722784148322010-07-01T19:26:34.504-04:002010-07-01T19:26:34.504-04:00Can someone explain how FFT can be used to compute...Can someone explain how FFT can be used to compute (S+S) mod p?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-80222241838661957702010-06-25T18:16:55.580-04:002010-06-25T18:16:55.580-04:00I don't obtain S+S explicitly. That's actu...I don't obtain S+S explicitly. That's actually a good problem. Does anybody have any idea?<br /><br />The solution I know is what Sariel says. Use linear hashing to a domain of p=2*t (modular hashing works, but multiply-shift is better). Then compute the set (S+S) mod p using FFT in time O(t*lg t).<br /><br />Now you can look up each value in -S in this set (S+S) mod p. If a value is not in, you know it's not part of a solution. Repeat O(lg n) times and only the true solutions remain.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-7204827111364922512010-06-23T11:34:36.048-04:002010-06-23T11:34:36.048-04:00Could you please give a hint? Does your algorithm ...Could you please give a hint? Does your algorithm obtain the set S+S explicitely?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-91785469976249530182010-06-21T23:08:14.550-04:002010-06-21T23:08:14.550-04:00FFT, work module random U = O(t), repeat O( log t ...FFT, work module random U = O(t), repeat O( log t ) times. No?<br /><br />No clue how to improve the running time. --SAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6457811934240579102010-06-21T23:01:02.477-04:002010-06-21T23:01:02.477-04:00Well, you can test membership in O(1) by a hash ta...Well, you can test membership in O(1) by a hash table, but the point is: how do you generate S+S in subquadratic time?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-30828844447954438812010-06-21T22:56:38.411-04:002010-06-21T22:56:38.411-04:00For each element x in S+S, query for the existence...For each element x in S+S, query for the existence of -x in S in O(log n) time for a O(t log n) algorithm.Anonymousnoreply@blogger.com