Encoder 2010

Hi I am interested in the editorial to this contest, mainly in the explanation of the problem SUM3.Please somebody help me.Thanks.

Hi dioxid,

This was an external contest. The organizers for the contest have not provided the editorials. You can view the solutions for the problems from the practice problem sections.

Yes i saw solutions to the problems, but in one specific problem I need the explanation of the problem , the problem is SUM3.If you can help me.Thanks.

you should have a look at this wikipedia page, and especially :

When the integers are in the range [?u
… u], 3SUM can be solved in time O(n

  • u lg u) by representing S as a bit vector, determining S + S by
    performing a discrete convolution
    using FFT, and then comparing to -S.

good luck ! :slight_smile:

Man thank you so much, I really waste a big time in the explanation of this problem, but in this page is all what I need.Thanks really