You are not logged in. Please login at www.codechef.com to post your questions!

×

NZEC error in java in FARASA

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

vermashubhang's gravatar image

5★vermashubhang
1.5k11025
accept rate: 23%


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.

link

answered 07 Mar '14, 02:03

anuraganand's gravatar image

5★anuraganand
21128
accept rate: 21%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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