1212:
The correctness of the algorithm can be seen as follows. Suppose we have a solution a + b + c = 0. Since the pointers only move in one direction, we can run the algorithm until the leftmost pointer points to a. Run the algorithm until either one of the remaining pointers points to b or c, whichever
1089:
a, b, c; // Continue search for all triplet combinations summing to zero. // We need to update both end and start together since the array values are distinct. start = start + 1; end = end - 1;
1983:
3768:
Given a set of non-intersecting axis-parallel line segment obstacles in the plane, can a given rod be moved by translations and rotations between a start and finish positions without colliding with the
1788:
522:
365:
223:
2494:
426:
1845:
1416:
2661:
624:
3554:
66:
3481:
2879:
573:
3408:
3190:
2945:
270:
92:
1691:
1631:
1571:
712:
3336:. Then the probability of finding a solution (if a solution exists) is the probability that the random selection will select the correct element from each cell, which is
3375:
2696:
1292:
3713:
1053:
876:
173:
2236:
1492:
3591:
1002:
3402:
3324:
3289:
3254:
3131:
3045:
2787:
2755:
2560:
2324:
2160:
2085:
3673:
2994:
762:
1015:, for which hashing is not allowed. The algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to
3629:
1428:
Instead of searching for the 3 numbers in a single array, we can search for them in 3 different arrays. I.e., given three arrays X, Y and Z, find three numbers
949:
929:
905:
836:
790:
732:
129:
668:
272:
time. In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in
4436:
97:
1857:
3743:
are 3SUM-hard, including the following ones. (The authors acknowledge that many of these problems are contributed by other researchers.)
4126:
Chan, Timothy M. (2018), "More
Logarithmic-Factor Speedups for 3SUM, (Median,+)-Convolution, and Some Geometric 3SUM-Hard Problems",
4271:
1499:
Given a solver for 3SUM×1, the 3SUM×3 problem can be solved in the following way (assuming all elements are integers):
1213:
occurs first. Then the algorithm will run until the last pointer points to the remaining term, giving the affirmative solution.
431:
4189:
4145:
275:
3750:
Given a set of non-intersecting axis-parallel line segments, is there a line that separates them into two non-empty subsets?
4081:
Kane, Daniel M.; Lovett, Shachar; Moran, Shay (2018). "Near-optimal linear decision trees for k-SUM and related problems".
4319:
4431:
4108:
4032:
3968:
1008:
178:
4372:
3775:
By now there are a multitude of other problems that fall into this category. An example is the decision version of
2329:
4426:
1722:
104:
374:
4315:
1323:
575:. The latter bound is tight (up to a logarithmic factor). It is still conjectured that 3SUM is unsolvable in
525:
368:
1226:
Instead of looking for numbers whose sum is 0, it is possible to look for numbers whose sum is any constant
2565:
578:
3765:
Given a set of horizontal triangles in space, can a particular triangle be seen from a particular point?
3488:
29:
3958:
3219:
This idealized solution doesn't work, because any hash function might map several distinct elements of
3421:
2819:
1230:. The simplest way would be to modify the original algorithm to search the hash table for the integer
531:
3136:
2921:
239:
71:
1640:
1580:
1520:
1114:
The following example shows this algorithm's execution on a small sorted array. Current values of
673:
3921:
Kopelowitz, Tsvi; Pettie, Seth; Porat, Ely (2014). "3SUM Hardness in (Dynamic) Data
Structures".
1797:
3740:
3339:
2666:
1235:
769:
3984:
3682:
1022:
845:
142:
4345:
4311:
2185:
1459:
428:. These bounds were subsequently improved. The current best known algorithm for 3SUM runs in
226:
3570:
1318:=4, then subtract 4/3 from all the elements of A, and solve it in the usual 3sum way, i.e.,
954:
4169:
3946:
3380:
3302:
3267:
3232:
3050:
3018:
2760:
2701:
2506:
2264:
2100:
2031:
765:
8:
3634:
2955:
741:
4173:
4019:. Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10. p. 603.
2809:. As a first approximation, assume that we have a linear hash function, i.e. a function
4295:
4255:
4216:
4159:
4114:
4086:
3922:
3835:
3596:
934:
914:
881:
803:
775:
717:
114:
632:
4404:
4385:
4220:
4185:
4141:
4104:
4028:
3964:
3728:
4323:
4118:
4389:
4381:
4299:
4287:
4275:
4245:
4208:
4177:
4158:. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. p. 621.
4131:
4096:
4020:
3942:
3753:
Given a set of infinite strips in the plane, do they fully cover a given rectangle?
4259:
2802:
Given a solver for Conv3SUM, the 3SUM problem can be solved in the following way.
2170:
Given a solver for 3SUM, the Conv3SUM problem can be solved in the following way.
4128:
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
Discrete Algorithms
4250:
4136:
3954:
3776:
131:
real numbers contains three elements that sum to zero. A generalized version,
4291:
4212:
4420:
4363:
4329:
4052:
2806:
1016:
4100:
4024:
1496:. Call the 1-array variant 3SUM×1 and the 3-array variant 3SUM×3.
18:
4307:
4267:
4229:
4048:
3407:
Unfortunately, we do not have linear perfect hashing, so we have to use an
4083:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of
Computing
236:
It was conjectured that any deterministic algorithm for the 3SUM requires
4181:
3747:
Given a set of lines in the plane, are there three that meet in a point?
3997:
3950:
908:
4394:
2242:
is the number of elements in the array, and the indices run from 0 to
1978:{\displaystyle a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10}
3732:
2892:
maps each element to an element in the smaller range of indices: 0...
735:
3759:
Given a set of triangles in the plane, does their union have a hole?
3293:. If a solution is found, then it is a correct solution for 3SUM on
4091:
2999:
Initially, suppose that the mappings are unique (i.e. each cell in
1012:
839:
4164:
3927:
2025:
Instead of looking for arbitrary elements of the array such that:
1007:
It is also possible to solve the problem in the same time in a
3756:
Given a set of triangles in the plane, compute their measure.
2094:
problem (Conv3SUM) looks for elements in specific locations:
139:
elements, rather than simply 3. 3SUM can be easily solved in
1991:
By the way we transformed the arrays, it is guaranteed that
4306:
4238:
In Proc. 25th Annual
European Symposium on Algorithms (ESA)
4047:
3762:
A number of visibility and motion planning problems, e.g.,
3404:
times, the solution will be found with a high probability.
3192:, so this solution will be found by the Conv3SUM solver on
3941:
3899:
3735:
for 3SUM. The concept of 3SUM-hardness was introduced by
3297:. If no solution is found, then create a different random
367:
time. Additionally, Grønlund and Pettie showed that the 4-
3848:
2884:
Suppose that all elements are integers in the range: 0...
1314:
For example, if A= and if you are asked to find 3SUM for
517:{\displaystyle O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})}
26:
Is there an algorithm to solve the 3SUM problem in time
3258:
by selecting a single random element from each cell of
2503:
Conversely, if in the new array there is a triple with
1019:
for the pairs in the sorted list, achieving worst-case
951:, checking whether the hash table contains the integer
360:{\displaystyle O(n^{2}/({\log n}/{\log \log n})^{2/3})}
3203:, then obviously it corresponds to a 3SUM solution on
1310:
In the modified array, find 3 elements whose sum is 0.
4051:; Erickson, Jeff; O'Rourke, Joseph (20 August 2006).
3920:
3872:
3685:
3637:
3599:
3573:
3491:
3424:
3383:
3342:
3305:
3270:
3235:
3139:
3053:
3021:
2958:
2924:
2822:
2763:
2704:
2669:
2568:
2509:
2332:
2267:
2188:
2103:
2034:
1860:
1800:
1725:
1643:
1583:
1523:
1462:
1326:
1238:
1025:
957:
937:
917:
884:
848:
806:
778:
744:
720:
676:
635:
581:
534:
434:
377:
278:
242:
181:
145:
117:
74:
32:
4265:
4017:
Towards polynomial lower bounds for dynamic problems
20:
4199:Freund, Ari (2017), "Improved Subquadratic 3SUM",
3889:
3887:
3707:
3667:
3623:
3585:
3548:
3475:
3396:
3369:
3318:
3283:
3248:
3184:
3125:
3039:
2988:
2939:
2873:
2797:
2781:
2749:
2690:
2655:
2554:
2488:
2318:
2230:
2165:
2154:
2079:
1977:
1839:
1782:
1717:Use the 3SUM×1 oracle to find three elements
1685:
1625:
1565:
1486:
1410:
1286:
1047:
996:
943:
923:
899:
870:
830:
784:
756:
726:
706:
662:
618:
567:
516:
420:
359:
264:
217:
167:
123:
86:
60:
4361:
4346:"Lower bounds for linear satisfiability problems"
3860:
3736:
4418:
3739:. They proved that a large class of problems in
2261:If in the original array there is a triple with
524:time. Kane, Lovett, and Moran showed that the 6-
4373:Computational Geometry: Theory and Applications
4350:Chicago Journal of Theoretical Computer Science
4080:
3905:
3884:
1070:a = S; start = i + 1; end = n - 1;
4153:
3854:
2789:, so this is a valid solution for Conv3SUM on
218:{\displaystyle \Omega (n^{\lceil k/2\rceil })}
4010:
4008:
4006:
2489:{\displaystyle T=2nS+i+j=(2nS+i)+(2nS+j)=T+T}
842:) models of computing, 3SUM can be solved in
3996:For a reduction in the other direction, see
2496:, so this solution will be found by 3SUM on
629:When the elements are integers in the range
207:
193:
98:(more unsolved problems in computer science)
4156:Threesomes, Degenerates, and Love Triangles
4053:"Problem 41: Sorting X + Y (Pairwise Sums)"
3963:(3rd ed.). MIT Press and McGraw-Hill.
3679:elements, and we will have to run Conv3SUM
3559:This requires to duplicate the elements of
1783:{\displaystyle a'\in S,\ b'\in S,\ c'\in S}
225:lower bounds are known in some specialized
4227:
4003:
3878:
421:{\displaystyle O(n^{3/2}{\sqrt {\log n}})}
16:Problem in computational complexity theory
4393:
4249:
4163:
4135:
4090:
3926:
3328:and try again. Suppose there are at most
1423:
1411:{\displaystyle (a-C/3)+(b-C/3)+(c-C/3)=0}
878:time on average by inserting each number
4343:
4014:
1307:/3 from all elements of the input array.
230:
4370:) problems in computational geometry",
3916:
3914:
4419:
4198:
3866:
3199:Conversely, if a Conv3SUM is found on
795:
4437:Unsolved problems in computer science
4402:
4125:
3911:
3893:
772:, and finally comparing this set to
21:Unsolved problem in computer science
4232:(2017), "Improved Bounds for 3SUM,
3003:accepts only a single element from
2656:{\displaystyle 2nS+k=2n(S+S)+(i+j)}
714:time by representing the input set
619:{\displaystyle O(n^{2-\Omega (1)})}
13:
4276:"Subquadratic algorithms for 3SUM"
3549:{\displaystyle h(x+y)=h(x)+h(y)+1}
3227:. The trick is to create an array
2925:
2020:
599:
243:
182:
61:{\displaystyle O(n^{2-\epsilon })}
14:
4448:
4154:Grønlund, A.; Pettie, S. (2014).
3015:If there is a solution for 3SUM:
1702:be a concatenation of the arrays
4320:"Problem 11: 3SUM Hard Problems"
3718:
3476:{\displaystyle h(x+y)=h(x)+h(y)}
2874:{\displaystyle h(x+y)=h(x)+h(y)}
568:{\displaystyle O(n{\log ^{2}n})}
135:-SUM, asks the same question on
4041:
3737:Gajentaan & Overmars (1995)
2798:Reduction from 3SUM to Conv3SUM
2166:Reduction from Conv3SUM to 3SUM
1221:
111:problem asks if a given set of
105:computational complexity theory
4406:A survey of 3SUM-hard problems
4236:-SUM, and Linear Degeneracy",
3990:
3978:
3935:
3696:
3686:
3656:
3653:
3647:
3641:
3618:
3615:
3609:
3603:
3537:
3531:
3522:
3516:
3507:
3495:
3470:
3464:
3455:
3449:
3440:
3428:
3358:
3343:
3185:{\displaystyle h(z)=h(x)+h(y)}
3179:
3173:
3164:
3158:
3149:
3143:
3120:
3117:
3111:
3105:
3096:
3093:
3087:
3081:
3072:
3069:
3063:
3057:
2977:
2974:
2968:
2962:
2940:{\displaystyle \forall x\in S}
2868:
2862:
2853:
2847:
2838:
2826:
2744:
2738:
2729:
2723:
2714:
2708:
2650:
2638:
2632:
2629:
2623:
2614:
2608:
2602:
2584:
2578:
2549:
2543:
2534:
2528:
2519:
2513:
2483:
2477:
2468:
2462:
2453:
2444:
2438:
2426:
2420:
2411:
2405:
2393:
2375:
2363:
2348:
2336:
2313:
2307:
2298:
2292:
2283:
2271:
2219:
2213:
2198:
2192:
2149:
2143:
2134:
2128:
2119:
2107:
2074:
2068:
2059:
2053:
2044:
2038:
1964:
1947:
1944:
1924:
1907:
1904:
1884:
1867:
1864:
1668:
1662:
1656:
1653:
1647:
1608:
1602:
1596:
1593:
1587:
1548:
1542:
1536:
1533:
1527:
1399:
1379:
1373:
1353:
1347:
1327:
1281:
1278:
1275:
1269:
1260:
1254:
1248:
1239:
1042:
1029:
991:
988:
982:
973:
967:
961:
894:
888:
865:
852:
825:
810:
701:
680:
657:
636:
613:
608:
602:
585:
562:
538:
511:
483:
477:
470:
451:
438:
415:
381:
354:
337:
300:
282:
265:{\displaystyle \Omega (n^{2})}
259:
246:
212:
185:
162:
149:
87:{\displaystyle \epsilon >0}
55:
36:
1:
4074:
3998:Variants of the 3-sum problem
3906:Kane, Lovett & Moran 2018
1686:{\displaystyle Z\gets Z*10-3}
1626:{\displaystyle Y\gets Y*10+2}
1566:{\displaystyle X\gets X*10+1}
1078:b = S c = S;
1011:-based model of computing or
4386:10.1016/0925-7721(95)00022-2
3731:implies a subquadratic-time
2178:, such that for every index
1118:are shown in red, values of
707:{\displaystyle O(n+N\log N)}
7:
3985:Visibility Graphs and 3-Sum
3829:
3409:almost linear hash function
1216:
911:, and then, for each index
800:Suppose the input array is
10:
4453:
4251:10.4230/LIPIcs.ESA.2017.42
4137:10.1137/1.9781611975031.57
3960:Introduction to Algorithms
3855:Grønlund & Pettie 2014
3675:. So each cell will have 2
3567:, i.e., put every element
2888:-1, and that the function
1840:{\displaystyle a'+b'+c'=0}
764:of all pairwise sums as a
4366:(1995), "On a class of O(
4325:The Open Problems Project
4292:10.1007/s00453-007-9036-3
4213:10.1007/s00453-015-0079-6
4057:The Open Problems Project
3791:elements each, are there
3370:{\displaystyle (1/R)^{3}}
3332:elements in each cell of
3211:is just a permutation of
2900:and send each element of
2691:{\displaystyle i+j<2n}
1287:{\displaystyle (C-(S+S))}
4432:Polynomial-time problems
3975:Ex. 30.1–7, p. 906.
3841:
3779:: given sets of numbers
3708:{\displaystyle (2R)^{3}}
2249:Solve 3SUM on the array
1048:{\displaystyle O(n^{2})}
871:{\displaystyle O(n^{2})}
670:, 3SUM can be solved in
168:{\displaystyle O(n^{2})}
4344:Erickson, Jeff (1999),
4101:10.1145/3188745.3188770
4025:10.1145/1806689.1806772
3563:when copying them into
2896:-1. Create a new array
2231:{\displaystyle T=2nS+i}
1487:{\displaystyle a+b+c=0}
1105:start = start + 1;
1101:end = end - 1;
4427:Computational geometry
4312:Mitchell, Joseph S. B.
3879:Gold & Sharir 2017
3741:computational geometry
3709:
3669:
3625:
3587:
3586:{\displaystyle x\in S}
3550:
3477:
3398:
3377:. By running Conv3SUM
3371:
3320:
3285:
3262:, and run Conv3SUM on
3250:
3186:
3127:
3041:
2990:
2941:
2875:
2783:
2751:
2692:
2657:
2556:
2490:
2320:
2232:
2156:
2081:
1979:
1841:
1784:
1687:
1627:
1567:
1488:
1424:Three different arrays
1412:
1288:
1126:are shown in magenta.
1049:
998:
997:{\displaystyle -(S+S)}
945:
925:
901:
872:
832:
786:
770:fast Fourier transform
758:
728:
708:
664:
620:
569:
528:complexity of 3SUM is
518:
422:
371:complexity of 3SUM is
361:
266:
219:
169:
125:
88:
62:
4015:Patrascu, M. (2010).
3947:Leiserson, Charles E.
3710:
3670:
3626:
3588:
3551:
3478:
3399:
3397:{\displaystyle R^{3}}
3372:
3321:
3319:{\displaystyle T^{*}}
3286:
3284:{\displaystyle T^{*}}
3251:
3249:{\displaystyle T^{*}}
3187:
3128:
3126:{\displaystyle T=T+T}
3042:
3040:{\displaystyle z=x+y}
3007:). Solve Conv3SUM on
2991:
2942:
2904:to its hash value in
2876:
2805:The reduction uses a
2784:
2782:{\displaystyle k=i+j}
2752:
2750:{\displaystyle S=S+S}
2693:
2658:
2557:
2555:{\displaystyle T=T+T}
2491:
2321:
2319:{\displaystyle S=S+S}
2233:
2157:
2155:{\displaystyle S=S+S}
2082:
2080:{\displaystyle S=S+S}
1980:
1842:
1785:
1688:
1628:
1568:
1503:For every element in
1489:
1413:
1289:
1151:(a+b+c==-22) . . .
1050:
999:
946:
926:
902:
873:
833:
787:
759:
729:
709:
665:
621:
570:
519:
423:
362:
267:
227:models of computation
220:
170:
126:
89:
63:
4403:King, James (2004),
4182:10.1109/FOCS.2014.72
4130:, pp. 881–897,
4085:. pp. 554–563.
3723:A problem is called
3683:
3635:
3597:
3571:
3489:
3422:
3381:
3340:
3303:
3268:
3233:
3223:to the same cell of
3137:
3051:
3019:
2956:
2922:
2820:
2761:
2702:
2667:
2566:
2507:
2330:
2265:
2186:
2101:
2032:
1858:
1798:
1723:
1641:
1581:
1521:
1460:
1324:
1236:
1023:
955:
935:
915:
882:
846:
804:
776:
766:discrete convolution
742:
738:, computing the set
718:
674:
633:
579:
532:
526:linear decision tree
432:
375:
369:linear decision tree
276:
240:
179:
143:
115:
72:
30:
4174:2014arXiv1404.0799G
3987:by Michael Hoffmann
3668:{\displaystyle T-1}
3631:(as before) and in
2989:{\displaystyle T=x}
2257:Correctness proof:
2174:Define a new array
1097:(a + b + c > 0)
796:Quadratic algorithm
757:{\displaystyle S+S}
175:time, and matching
3836:Subset sum problem
3705:
3665:
3621:
3583:
3546:
3473:
3411:, i.e. a function
3394:
3367:
3316:
3281:
3246:
3182:
3123:
3037:
2986:
2937:
2908:, i.e., for every
2871:
2779:
2747:
2688:
2653:
2552:
2486:
2316:
2228:
2152:
2077:
1975:
1837:
1780:
1683:
1623:
1563:
1484:
1408:
1284:
1055:time, as follows.
1045:
994:
941:
921:
897:
868:
828:
782:
754:
724:
704:
660:
616:
565:
514:
418:
357:
262:
215:
165:
121:
84:
58:
4364:Overmars, Mark H.
4362:Gajentaan, Anka;
4191:978-1-4799-6517-5
4147:978-1-61197-503-1
3951:Rivest, Ronald L.
3943:Cormen, Thomas H.
3729:subquadratic time
3727:if solving it in
3624:{\displaystyle T}
1940:
1900:
1765:
1745:
1185:(a+b+c==-3) -25
1173:(a+b+c==-7) -25
1162:(a+b+c==-7) -25
1082:(a + b + c == 0)
1074:(start < end)
944:{\displaystyle j}
924:{\displaystyle i}
900:{\displaystyle S}
831:{\displaystyle S}
785:{\displaystyle S}
727:{\displaystyle S}
413:
124:{\displaystyle n}
4444:
4412:
4411:
4398:
4397:
4357:
4339:
4338:
4337:
4328:, archived from
4316:O'Rourke, Joseph
4308:Demaine, Erik D.
4302:
4268:Demaine, Erik D.
4262:
4253:
4235:
4223:
4195:
4167:
4150:
4139:
4122:
4094:
4068:
4067:
4065:
4063:
4045:
4039:
4038:
4012:
4001:
3994:
3988:
3982:
3976:
3974:
3939:
3933:
3932:
3930:
3918:
3909:
3903:
3897:
3891:
3882:
3876:
3870:
3864:
3858:
3852:
3825:
3807:
3797:
3790:
3786:
3782:
3714:
3712:
3711:
3706:
3704:
3703:
3674:
3672:
3671:
3666:
3630:
3628:
3627:
3622:
3592:
3590:
3589:
3584:
3555:
3553:
3552:
3547:
3482:
3480:
3479:
3474:
3403:
3401:
3400:
3395:
3393:
3392:
3376:
3374:
3373:
3368:
3366:
3365:
3353:
3327:
3325:
3323:
3322:
3317:
3315:
3314:
3292:
3290:
3288:
3287:
3282:
3280:
3279:
3257:
3255:
3253:
3252:
3247:
3245:
3244:
3191:
3189:
3188:
3183:
3132:
3130:
3129:
3124:
3046:
3044:
3043:
3038:
2995:
2993:
2992:
2987:
2948:
2946:
2944:
2943:
2938:
2880:
2878:
2877:
2872:
2788:
2786:
2785:
2780:
2756:
2754:
2753:
2748:
2697:
2695:
2694:
2689:
2662:
2660:
2659:
2654:
2561:
2559:
2558:
2553:
2495:
2493:
2492:
2487:
2325:
2323:
2322:
2317:
2237:
2235:
2234:
2229:
2161:
2159:
2158:
2153:
2092:convolution 3sum
2086:
2084:
2083:
2078:
2016:
1986:
1984:
1982:
1981:
1976:
1971:
1957:
1938:
1931:
1917:
1898:
1891:
1877:
1848:
1846:
1844:
1843:
1838:
1830:
1819:
1808:
1791:
1789:
1787:
1786:
1781:
1773:
1763:
1753:
1743:
1733:
1694:
1692:
1690:
1689:
1684:
1634:
1632:
1630:
1629:
1624:
1574:
1572:
1570:
1569:
1564:
1495:
1493:
1491:
1490:
1485:
1453:
1419:
1417:
1415:
1414:
1409:
1395:
1369:
1343:
1299:Another method:
1295:
1293:
1291:
1290:
1285:
1208:
1204:
1200:
1197:(a+b+c==2) -25
1196:
1192:
1188:
1184:
1180:
1176:
1172:
1168:
1165:
1161:
1158:
1154:
1150:
1146:
1142:
1138:
1134:
1131:
1054:
1052:
1051:
1046:
1041:
1040:
1003:
1001:
1000:
995:
950:
948:
947:
942:
930:
928:
927:
922:
906:
904:
903:
898:
877:
875:
874:
869:
864:
863:
837:
835:
834:
829:
791:
789:
788:
783:
763:
761:
760:
755:
733:
731:
730:
725:
713:
711:
710:
705:
669:
667:
666:
663:{\displaystyle }
661:
625:
623:
622:
617:
612:
611:
574:
572:
571:
566:
561:
554:
553:
523:
521:
520:
515:
510:
503:
502:
492:
487:
486:
450:
449:
427:
425:
424:
419:
414:
403:
401:
400:
396:
366:
364:
363:
358:
353:
352:
348:
335:
318:
313:
299:
294:
293:
271:
269:
268:
263:
258:
257:
224:
222:
221:
216:
211:
210:
203:
174:
172:
171:
166:
161:
160:
130:
128:
127:
122:
93:
91:
90:
85:
67:
65:
64:
59:
54:
53:
22:
4452:
4451:
4447:
4446:
4445:
4443:
4442:
4441:
4417:
4416:
4409:
4335:
4333:
4272:Pătraşcu, Mihai
4233:
4192:
4148:
4111:
4077:
4072:
4071:
4061:
4059:
4046:
4042:
4035:
4013:
4004:
3995:
3991:
3983:
3979:
3971:
3955:Stein, Clifford
3940:
3936:
3919:
3912:
3904:
3900:
3892:
3885:
3877:
3873:
3865:
3861:
3853:
3849:
3844:
3832:
3809:
3799:
3792:
3788:
3784:
3780:
3721:
3699:
3695:
3684:
3681:
3680:
3636:
3633:
3632:
3598:
3595:
3594:
3572:
3569:
3568:
3490:
3487:
3486:
3423:
3420:
3419:
3388:
3384:
3382:
3379:
3378:
3361:
3357:
3349:
3341:
3338:
3337:
3310:
3306:
3304:
3301:
3300:
3298:
3275:
3271:
3269:
3266:
3265:
3263:
3240:
3236:
3234:
3231:
3230:
3228:
3138:
3135:
3134:
3052:
3049:
3048:
3020:
3017:
3016:
2957:
2954:
2953:
2923:
2920:
2919:
2917:
2821:
2818:
2817:
2800:
2762:
2759:
2758:
2703:
2700:
2699:
2668:
2665:
2664:
2567:
2564:
2563:
2508:
2505:
2504:
2331:
2328:
2327:
2266:
2263:
2262:
2187:
2184:
2183:
2168:
2102:
2099:
2098:
2033:
2030:
2029:
2023:
2021:Convolution sum
1992:
1967:
1950:
1927:
1910:
1887:
1870:
1859:
1856:
1855:
1853:
1823:
1812:
1801:
1799:
1796:
1795:
1793:
1766:
1746:
1726:
1724:
1721:
1720:
1718:
1642:
1639:
1638:
1636:
1582:
1579:
1578:
1576:
1522:
1519:
1518:
1516:
1461:
1458:
1457:
1455:
1429:
1426:
1391:
1365:
1339:
1325:
1322:
1321:
1319:
1237:
1234:
1233:
1231:
1224:
1219:
1210:
1209:10 (a+b+c==0)
1206:
1202:
1198:
1194:
1190:
1186:
1182:
1178:
1174:
1170:
1166:
1163:
1159:
1156:
1152:
1148:
1144:
1140:
1136:
1132:
1129:
1112:
1036:
1032:
1024:
1021:
1020:
956:
953:
952:
936:
933:
932:
916:
913:
912:
883:
880:
879:
859:
855:
847:
844:
843:
838:. In integer (
805:
802:
801:
798:
777:
774:
773:
743:
740:
739:
719:
716:
715:
675:
672:
671:
634:
631:
630:
626:expected time.
592:
588:
580:
577:
576:
549:
545:
544:
533:
530:
529:
498:
494:
493:
488:
473:
469:
445:
441:
433:
430:
429:
402:
392:
388:
384:
376:
373:
372:
344:
340:
336:
319:
314:
303:
295:
289:
285:
277:
274:
273:
253:
249:
241:
238:
237:
199:
192:
188:
180:
177:
176:
156:
152:
144:
141:
140:
116:
113:
112:
101:
100:
95:
73:
70:
69:
43:
39:
31:
28:
27:
24:
17:
12:
11:
5:
4450:
4440:
4439:
4434:
4429:
4415:
4414:
4400:
4380:(3): 165–185,
4359:
4341:
4304:
4286:(4): 584–596,
4263:
4244:: 42:1–42:13,
4225:
4207:(2): 440–458,
4196:
4190:
4151:
4146:
4123:
4109:
4076:
4073:
4070:
4069:
4040:
4033:
4002:
3989:
3977:
3969:
3934:
3910:
3898:
3883:
3871:
3859:
3846:
3845:
3843:
3840:
3839:
3838:
3831:
3828:
3773:
3772:
3771:
3770:
3766:
3760:
3757:
3754:
3751:
3748:
3720:
3717:
3702:
3698:
3694:
3691:
3688:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3582:
3579:
3576:
3557:
3556:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3497:
3494:
3484:
3472:
3469:
3466:
3463:
3460:
3457:
3454:
3451:
3448:
3445:
3442:
3439:
3436:
3433:
3430:
3427:
3391:
3387:
3364:
3360:
3356:
3352:
3348:
3345:
3313:
3309:
3278:
3274:
3243:
3239:
3217:
3216:
3197:
3181:
3178:
3175:
3172:
3169:
3166:
3163:
3160:
3157:
3154:
3151:
3148:
3145:
3142:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3036:
3033:
3030:
3027:
3024:
2997:
2996:
2985:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2936:
2933:
2930:
2927:
2882:
2881:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2799:
2796:
2795:
2794:
2778:
2775:
2772:
2769:
2766:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2707:
2698:, necessarily
2687:
2684:
2681:
2678:
2675:
2672:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2501:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2255:
2254:
2247:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2167:
2164:
2163:
2162:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2088:
2087:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2022:
2019:
1989:
1988:
1974:
1970:
1966:
1963:
1960:
1956:
1953:
1949:
1946:
1943:
1937:
1934:
1930:
1926:
1923:
1920:
1916:
1913:
1909:
1906:
1903:
1897:
1894:
1890:
1886:
1883:
1880:
1876:
1873:
1869:
1866:
1863:
1850:
1836:
1833:
1829:
1826:
1822:
1818:
1815:
1811:
1807:
1804:
1779:
1776:
1772:
1769:
1762:
1759:
1756:
1752:
1749:
1742:
1739:
1736:
1732:
1729:
1715:
1696:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1425:
1422:
1407:
1404:
1401:
1398:
1394:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1368:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1342:
1338:
1335:
1332:
1329:
1312:
1311:
1308:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1223:
1220:
1218:
1215:
1155:-10 -7 -3 2 4
1139:(a+b+c==-25)
1128:
1057:
1044:
1039:
1035:
1031:
1028:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
940:
920:
896:
893:
890:
887:
867:
862:
858:
854:
851:
827:
824:
821:
818:
815:
812:
809:
797:
794:
781:
753:
750:
747:
723:
703:
700:
697:
694:
691:
688:
685:
682:
679:
659:
656:
653:
650:
647:
644:
641:
638:
615:
610:
607:
604:
601:
598:
595:
591:
587:
584:
564:
560:
557:
552:
548:
543:
540:
537:
513:
509:
506:
501:
497:
491:
485:
482:
479:
476:
472:
468:
465:
462:
459:
456:
453:
448:
444:
440:
437:
417:
412:
409:
406:
399:
395:
391:
387:
383:
380:
356:
351:
347:
343:
339:
334:
331:
328:
325:
322:
317:
312:
309:
306:
302:
298:
292:
288:
284:
281:
261:
256:
252:
248:
245:
214:
209:
206:
202:
198:
195:
191:
187:
184:
164:
159:
155:
151:
148:
120:
96:
83:
80:
77:
57:
52:
49:
46:
42:
38:
35:
25:
19:
15:
9:
6:
4:
3:
2:
4449:
4438:
4435:
4433:
4430:
4428:
4425:
4424:
4422:
4408:
4407:
4401:
4396:
4391:
4387:
4383:
4379:
4375:
4374:
4369:
4365:
4360:
4355:
4351:
4347:
4342:
4332:on 2012-12-15
4331:
4327:
4326:
4321:
4318:(July 2005),
4317:
4313:
4309:
4305:
4301:
4297:
4293:
4289:
4285:
4281:
4277:
4273:
4269:
4266:Baran, Ilya;
4264:
4261:
4257:
4252:
4247:
4243:
4239:
4231:
4230:Sharir, Micha
4226:
4222:
4218:
4214:
4210:
4206:
4202:
4197:
4193:
4187:
4183:
4179:
4175:
4171:
4166:
4161:
4157:
4152:
4149:
4143:
4138:
4133:
4129:
4124:
4120:
4116:
4112:
4110:9781450355599
4106:
4102:
4098:
4093:
4088:
4084:
4079:
4078:
4058:
4054:
4050:
4049:Demaine, Erik
4044:
4036:
4034:9781450300506
4030:
4026:
4022:
4018:
4011:
4009:
4007:
3999:
3993:
3986:
3981:
3972:
3970:0-262-03384-4
3966:
3962:
3961:
3956:
3952:
3948:
3944:
3938:
3929:
3924:
3917:
3915:
3907:
3902:
3895:
3890:
3888:
3880:
3875:
3868:
3863:
3856:
3851:
3847:
3837:
3834:
3833:
3827:
3824:
3820:
3816:
3812:
3806:
3802:
3795:
3778:
3777:X + Y sorting
3767:
3764:
3763:
3761:
3758:
3755:
3752:
3749:
3746:
3745:
3744:
3742:
3738:
3734:
3730:
3726:
3719:3SUM-hardness
3716:
3700:
3692:
3689:
3678:
3662:
3659:
3650:
3644:
3638:
3612:
3606:
3600:
3580:
3577:
3574:
3566:
3562:
3543:
3540:
3534:
3528:
3525:
3519:
3513:
3510:
3504:
3501:
3498:
3492:
3485:
3467:
3461:
3458:
3452:
3446:
3443:
3437:
3434:
3431:
3425:
3418:
3417:
3416:
3414:
3410:
3405:
3389:
3385:
3362:
3354:
3350:
3346:
3335:
3331:
3311:
3307:
3296:
3276:
3272:
3261:
3241:
3237:
3226:
3222:
3214:
3210:
3206:
3202:
3198:
3195:
3176:
3170:
3167:
3161:
3155:
3152:
3146:
3140:
3114:
3108:
3102:
3099:
3090:
3084:
3078:
3075:
3066:
3060:
3054:
3034:
3031:
3028:
3025:
3022:
3014:
3013:
3012:
3010:
3006:
3002:
2983:
2980:
2971:
2965:
2959:
2952:
2951:
2950:
2934:
2931:
2928:
2915:
2911:
2907:
2903:
2899:
2895:
2891:
2887:
2865:
2859:
2856:
2850:
2844:
2841:
2835:
2832:
2829:
2823:
2816:
2815:
2814:
2812:
2808:
2807:hash function
2803:
2792:
2776:
2773:
2770:
2767:
2764:
2741:
2735:
2732:
2726:
2720:
2717:
2711:
2705:
2685:
2682:
2679:
2676:
2673:
2670:
2647:
2644:
2641:
2635:
2626:
2620:
2617:
2611:
2605:
2599:
2596:
2593:
2590:
2587:
2581:
2575:
2572:
2569:
2546:
2540:
2537:
2531:
2525:
2522:
2516:
2510:
2502:
2499:
2480:
2474:
2471:
2465:
2459:
2456:
2450:
2447:
2441:
2435:
2432:
2429:
2423:
2417:
2414:
2408:
2402:
2399:
2396:
2390:
2387:
2384:
2381:
2378:
2372:
2369:
2366:
2360:
2357:
2354:
2351:
2345:
2342:
2339:
2333:
2310:
2304:
2301:
2295:
2289:
2286:
2280:
2277:
2274:
2268:
2260:
2259:
2258:
2252:
2248:
2245:
2241:
2225:
2222:
2216:
2210:
2207:
2204:
2201:
2195:
2189:
2181:
2177:
2173:
2172:
2171:
2146:
2140:
2137:
2131:
2125:
2122:
2116:
2113:
2110:
2104:
2097:
2096:
2095:
2093:
2071:
2065:
2062:
2056:
2050:
2047:
2041:
2035:
2028:
2027:
2026:
2018:
2015:
2011:
2007:
2003:
1999:
1995:
1972:
1968:
1961:
1958:
1954:
1951:
1941:
1935:
1932:
1928:
1921:
1918:
1914:
1911:
1901:
1895:
1892:
1888:
1881:
1878:
1874:
1871:
1861:
1851:
1834:
1831:
1827:
1824:
1820:
1816:
1813:
1809:
1805:
1802:
1777:
1774:
1770:
1767:
1760:
1757:
1754:
1750:
1747:
1740:
1737:
1734:
1730:
1727:
1716:
1713:
1709:
1705:
1701:
1697:
1680:
1677:
1674:
1671:
1665:
1659:
1650:
1644:
1620:
1617:
1614:
1611:
1605:
1599:
1590:
1584:
1560:
1557:
1554:
1551:
1545:
1539:
1530:
1524:
1514:
1510:
1506:
1502:
1501:
1500:
1497:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1452:
1448:
1444:
1440:
1436:
1432:
1421:
1405:
1402:
1396:
1392:
1388:
1385:
1382:
1376:
1370:
1366:
1362:
1359:
1356:
1350:
1344:
1340:
1336:
1333:
1330:
1317:
1309:
1306:
1302:
1301:
1300:
1297:
1272:
1266:
1263:
1257:
1251:
1245:
1242:
1229:
1214:
1127:
1125:
1121:
1117:
1111:
1108:
1104:
1100:
1096:
1093:
1088:
1085:
1081:
1077:
1073:
1069:
1065:
1061:
1056:
1037:
1033:
1026:
1018:
1017:binary search
1014:
1010:
1005:
985:
979:
976:
970:
964:
958:
938:
918:
910:
891:
885:
860:
856:
849:
841:
822:
819:
816:
813:
807:
793:
779:
771:
767:
751:
748:
745:
737:
721:
698:
695:
692:
689:
686:
683:
677:
654:
651:
648:
645:
642:
639:
627:
605:
596:
593:
589:
582:
558:
555:
550:
546:
541:
535:
527:
507:
504:
499:
495:
489:
480:
474:
466:
463:
460:
457:
454:
446:
442:
435:
410:
407:
404:
397:
393:
389:
385:
378:
370:
349:
345:
341:
332:
329:
326:
323:
320:
315:
310:
307:
304:
296:
290:
286:
279:
254:
250:
234:
232:
231:Erickson 1999
228:
204:
200:
196:
189:
157:
153:
146:
138:
134:
118:
110:
106:
99:
81:
78:
75:
50:
47:
44:
40:
33:
4405:
4377:
4371:
4367:
4353:
4349:
4334:, retrieved
4330:the original
4324:
4283:
4280:Algorithmica
4279:
4241:
4237:
4228:Gold, Omer;
4204:
4201:Algorithmica
4200:
4155:
4127:
4082:
4062:23 September
4060:. Retrieved
4056:
4043:
4016:
3992:
3980:
3959:
3937:
3901:
3874:
3862:
3850:
3822:
3818:
3814:
3810:
3804:
3800:
3793:
3774:
3724:
3722:
3676:
3564:
3560:
3558:
3412:
3406:
3333:
3329:
3294:
3259:
3224:
3220:
3218:
3212:
3208:
3204:
3200:
3193:
3008:
3004:
3000:
2998:
2913:
2909:
2905:
2901:
2897:
2893:
2889:
2885:
2883:
2810:
2804:
2801:
2790:
2497:
2256:
2250:
2243:
2239:
2179:
2175:
2169:
2091:
2089:
2024:
2013:
2009:
2005:
2001:
1997:
1993:
1990:
1711:
1707:
1703:
1699:
1512:
1508:
1504:
1498:
1454:, such that
1450:
1446:
1442:
1438:
1434:
1430:
1427:
1315:
1313:
1304:
1298:
1227:
1225:
1222:Non-zero sum
1211:
1135:-7 -3 2 4 8
1123:
1119:
1115:
1113:
1109:
1106:
1102:
1098:
1094:
1091:
1086:
1083:
1079:
1075:
1071:
1067:
1063:
1059:
1006:
799:
628:
235:
136:
132:
108:
102:
4356:, MIT Press
3867:Freund 2017
3415:such that:
2813:such that:
68:, for some
4421:Categories
4395:1874/17058
4336:2008-09-02
4240:, LIPIcs,
4092:1705.01720
4075:References
3769:obstacles?
2663:. Because
1792:such that
1009:comparison
909:hash table
768:using the
736:bit vector
4221:253979651
4165:1404.0799
3957:(2009) .
3928:1407.6756
3894:Chan 2018
3798:distinct
3733:algorithm
3725:3SUM-hard
3660:−
3578:∈
3312:∗
3277:∗
3242:∗
2932:∈
2926:∀
1945:←
1919:−
1905:←
1879:−
1865:←
1775:∈
1755:∈
1735:∈
1678:−
1672:∗
1657:←
1612:∗
1597:←
1552:∗
1537:←
1386:−
1360:−
1334:−
1303:Subtract
1246:−
1169:-3 2 4 8
1147:-3 2 4 8
1058:sort(S);
959:−
820:−
696:
649:…
640:−
600:Ω
597:−
556:
505:
464:
458:
408:
330:
324:
308:
244:Ω
208:⌉
194:⌈
183:Ω
76:ϵ
51:ϵ
48:−
4274:(2008),
4119:30368541
3830:See also
3593:both in
3047:, then:
1955:′
1915:′
1875:′
1828:′
1817:′
1806:′
1771:′
1751:′
1731:′
1217:Variants
1013:real RAM
840:word RAM
4300:9855995
4170:Bibcode
3715:times.
3326:
3299:
3291:
3264:
3256:
3229:
3011:. Now:
2947:
2918:
2562:, then
2326:, then
2238:(where
1985:
1854:
1852:Return
1847:
1794:
1790:
1719:
1693:
1637:
1633:
1577:
1573:
1517:
1515:, set:
1494:
1456:
1418:
1320:
1294:
1232:
907:into a
4298:
4260:691387
4258:
4219:
4188:
4144:
4117:
4107:
4031:
3967:
3207:since
1939:
1899:
1764:
1744:
1201:-7 -3
1189:-7 -3
1181:2 4 8
1087:output
1066:n - 2
1062:i = 0
107:, the
4410:(PDF)
4296:S2CID
4256:S2CID
4217:S2CID
4160:arXiv
4115:S2CID
4087:arXiv
3923:arXiv
3842:Notes
1072:while
734:as a
4354:1999
4186:ISBN
4142:ISBN
4105:ISBN
4064:2014
4029:ISBN
3965:ISBN
3808:for
3783:and
3133:and
2757:and
2680:<
2246:-1).
2090:the
1710:and
1698:Let
1511:and
1193:4 8
1143:-10
1122:and
1103:else
1099:then
1092:else
1084:then
931:and
109:3SUM
79:>
4390:hdl
4382:doi
4288:doi
4246:doi
4209:doi
4178:doi
4132:doi
4097:doi
4021:doi
3787:of
2949:):
2912:in
1199:-10
1187:-10
1177:-7
1175:-10
1164:-10
1153:-25
1141:-25
1133:-10
1130:-25
1110:end
1107:end
1060:for
814:0..
693:log
547:log
496:log
461:log
455:log
405:log
327:log
321:log
305:log
233:).
103:In
4423::
4388:,
4376:,
4352:,
4348:,
4322:,
4314:;
4310:;
4294:,
4284:50
4282:,
4278:,
4270:;
4254:,
4242:87
4215:,
4205:44
4203:,
4184:.
4176:.
4168:.
4140:,
4113:.
4103:.
4095:.
4055:.
4027:.
4005:^
3953:;
3949:;
3945:;
3913:^
3886:^
3826:?
3821:∈
3817:,
3813:∈
3803:+
3483:or
2182::
2017:.
2008:,
2000:,
1973:10
1933:10
1893:10
1706:,
1675:10
1635:,
1615:10
1575:,
1555:10
1507:,
1445:,
1437:,
1420:.
1296:.
1205:4
1195:10
1183:10
1179:-3
1171:10
1167:-7
1160:10
1149:10
1145:-7
1137:10
1095:if
1080:if
1076:do
1068:do
1064:to
1004:.
792:.
4413:.
4399:.
4392::
4384::
4378:5
4368:n
4358:.
4340:.
4303:.
4290::
4248::
4234:k
4224:.
4211::
4194:.
4180::
4172::
4162::
4134::
4121:.
4099::
4089::
4066:.
4037:.
4023::
4000:.
3973:.
3931:.
3925::
3908:.
3896:.
3881:.
3869:.
3857:.
3823:Y
3819:y
3815:X
3811:x
3805:y
3801:x
3796:²
3794:n
3789:n
3785:Y
3781:X
3701:3
3697:)
3693:R
3690:2
3687:(
3677:R
3663:1
3657:]
3654:)
3651:x
3648:(
3645:h
3642:[
3639:T
3619:]
3616:)
3613:x
3610:(
3607:h
3604:[
3601:T
3581:S
3575:x
3565:T
3561:S
3544:1
3541:+
3538:)
3535:y
3532:(
3529:h
3526:+
3523:)
3520:x
3517:(
3514:h
3511:=
3508:)
3505:y
3502:+
3499:x
3496:(
3493:h
3471:)
3468:y
3465:(
3462:h
3459:+
3456:)
3453:x
3450:(
3447:h
3444:=
3441:)
3438:y
3435:+
3432:x
3429:(
3426:h
3413:h
3390:3
3386:R
3363:3
3359:)
3355:R
3351:/
3347:1
3344:(
3334:T
3330:R
3308:T
3295:S
3273:T
3260:T
3238:T
3225:T
3221:S
3215:.
3213:S
3209:T
3205:S
3201:T
3196:.
3194:T
3180:)
3177:y
3174:(
3171:h
3168:+
3165:)
3162:x
3159:(
3156:h
3153:=
3150:)
3147:z
3144:(
3141:h
3121:]
3118:)
3115:y
3112:(
3109:h
3106:[
3103:T
3100:+
3097:]
3094:)
3091:x
3088:(
3085:h
3082:[
3079:T
3076:=
3073:]
3070:)
3067:z
3064:(
3061:h
3058:[
3055:T
3035:y
3032:+
3029:x
3026:=
3023:z
3009:T
3005:S
3001:T
2984:x
2981:=
2978:]
2975:)
2972:x
2969:(
2966:h
2963:[
2960:T
2935:S
2929:x
2916:(
2914:S
2910:x
2906:T
2902:S
2898:T
2894:n
2890:h
2886:N
2869:)
2866:y
2863:(
2860:h
2857:+
2854:)
2851:x
2848:(
2845:h
2842:=
2839:)
2836:y
2833:+
2830:x
2827:(
2824:h
2811:h
2793:.
2791:S
2777:j
2774:+
2771:i
2768:=
2765:k
2745:]
2742:j
2739:[
2736:S
2733:+
2730:]
2727:i
2724:[
2721:S
2718:=
2715:]
2712:k
2709:[
2706:S
2686:n
2683:2
2677:j
2674:+
2671:i
2651:)
2648:j
2645:+
2642:i
2639:(
2636:+
2633:)
2630:]
2627:j
2624:[
2621:S
2618:+
2615:]
2612:i
2609:[
2606:S
2603:(
2600:n
2597:2
2594:=
2591:k
2588:+
2585:]
2582:k
2579:[
2576:S
2573:n
2570:2
2550:]
2547:j
2544:[
2541:T
2538:+
2535:]
2532:i
2529:[
2526:T
2523:=
2520:]
2517:k
2514:[
2511:T
2500:.
2498:T
2484:]
2481:j
2478:[
2475:T
2472:+
2469:]
2466:i
2463:[
2460:T
2457:=
2454:)
2451:j
2448:+
2445:]
2442:j
2439:[
2436:S
2433:n
2430:2
2427:(
2424:+
2421:)
2418:i
2415:+
2412:]
2409:i
2406:[
2403:S
2400:n
2397:2
2394:(
2391:=
2388:j
2385:+
2382:i
2379:+
2376:]
2373:j
2370:+
2367:i
2364:[
2361:S
2358:n
2355:2
2352:=
2349:]
2346:j
2343:+
2340:i
2337:[
2334:T
2314:]
2311:j
2308:[
2305:S
2302:+
2299:]
2296:i
2293:[
2290:S
2287:=
2284:]
2281:j
2278:+
2275:i
2272:[
2269:S
2253:.
2251:T
2244:n
2240:n
2226:i
2223:+
2220:]
2217:i
2214:[
2211:S
2208:n
2205:2
2202:=
2199:]
2196:i
2193:[
2190:T
2180:i
2176:T
2150:]
2147:j
2144:[
2141:S
2138:+
2135:]
2132:i
2129:[
2126:S
2123:=
2120:]
2117:j
2114:+
2111:i
2108:[
2105:S
2075:]
2072:j
2069:[
2066:S
2063:+
2060:]
2057:i
2054:[
2051:S
2048:=
2045:]
2042:k
2039:[
2036:S
2014:Z
2012:∈
2010:c
2006:Y
2004:∈
2002:b
1998:X
1996:∈
1994:a
1987:.
1969:/
1965:)
1962:3
1959:+
1952:c
1948:(
1942:c
1936:,
1929:/
1925:)
1922:2
1912:b
1908:(
1902:b
1896:,
1889:/
1885:)
1882:1
1872:a
1868:(
1862:a
1849:.
1835:0
1832:=
1825:c
1821:+
1814:b
1810:+
1803:a
1778:S
1768:c
1761:,
1758:S
1748:b
1741:,
1738:S
1728:a
1714:.
1712:Z
1708:Y
1704:X
1700:S
1695:.
1681:3
1669:]
1666:i
1663:[
1660:Z
1654:]
1651:i
1648:[
1645:Z
1621:2
1618:+
1609:]
1606:i
1603:[
1600:Y
1594:]
1591:i
1588:[
1585:Y
1561:1
1558:+
1549:]
1546:i
1543:[
1540:X
1534:]
1531:i
1528:[
1525:X
1513:Z
1509:Y
1505:X
1482:0
1479:=
1476:c
1473:+
1470:b
1467:+
1464:a
1451:Z
1449:∈
1447:c
1443:Y
1441:∈
1439:b
1435:X
1433:∈
1431:a
1406:0
1403:=
1400:)
1397:3
1393:/
1389:C
1383:c
1380:(
1377:+
1374:)
1371:3
1367:/
1363:C
1357:b
1354:(
1351:+
1348:)
1345:3
1341:/
1337:C
1331:a
1328:(
1316:C
1305:C
1282:)
1279:)
1276:]
1273:j
1270:[
1267:S
1264:+
1261:]
1258:i
1255:[
1252:S
1249:(
1243:C
1240:(
1228:C
1207:8
1203:2
1191:2
1157:8
1124:c
1120:b
1116:a
1043:)
1038:2
1034:n
1030:(
1027:O
992:)
989:]
986:j
983:[
980:S
977:+
974:]
971:i
968:[
965:S
962:(
939:j
919:i
895:]
892:i
889:[
886:S
866:)
861:2
857:n
853:(
850:O
826:]
823:1
817:n
811:[
808:S
780:S
752:S
749:+
746:S
722:S
702:)
699:N
690:N
687:+
684:n
681:(
678:O
658:]
655:N
652:,
646:,
643:N
637:[
614:)
609:)
606:1
603:(
594:2
590:n
586:(
583:O
563:)
559:n
551:2
542:n
539:(
536:O
512:)
508:n
500:2
490:/
484:)
481:1
478:(
475:O
471:)
467:n
452:(
447:2
443:n
439:(
436:O
416:)
411:n
398:2
394:/
390:3
386:n
382:(
379:O
355:)
350:3
346:/
342:2
338:)
333:n
316:/
311:n
301:(
297:/
291:2
287:n
283:(
280:O
260:)
255:2
251:n
247:(
229:(
213:)
205:2
201:/
197:k
190:n
186:(
163:)
158:2
154:n
150:(
147:O
137:k
133:k
119:n
94:?
82:0
56:)
45:2
41:n
37:(
34:O
23::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.