×

# NZEC error in java in FARASA

 1 I am new to the concept of Fast Fourier Transformation. So I looked up at the codes of few very good coders like Ankit Shrivastava. In the solution of Ankit Shrivastava with solution link : http://www.codechef.com/viewsolution/2382669 - and a few other successful submissions. I found that all the coders are doing the naive approach for the smaller values like <5000 values using HashSet and then for the larger values they are doing the Fast Fourier Transformation using their own classes of FFT. But if we try to submit the solution directly without this constraint and apply FFT to all the values of input we get NZEC as I tested on the solution of Ankit Shrivastava. I am unable to figure out the problem with this. Thank You asked 18 Feb '14, 14:06 1.5k●1●10●25 accept rate: 23%

 0 In this problem FFT is used to generate all the possible differences of prefix sums. As all the positive values of such differences will give us the sub-array sum. We do this by multiplication of two polynomials, one with positive prefix sums as powers of x and the other with negative prefix sums as the powers of x. Since values of prefix sums can become very high for smaller values according to the problem constraint. So, this may cause excessive memory which causes NZEC. answered 07 Mar '14, 02:03 211●2●8 accept rate: 21%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,658
×334

question asked: 18 Feb '14, 14:06

question was seen: 998 times

last updated: 07 Mar '14, 02:03