REALSET - Editorial

editorial
, , , ,
21

Cool thanks :slight_smile: I was only able to get step 1, but wasn’t able to convince myself of step 2 during the contest. It’s much clearer now.

22

jaskaran: If you actually looked more into how/why it works this way, you’d notice that Cooley-Tukey makes use of identities involving the N-th root of unity, and those are only nice if we split the FFT’d array into arrays of equal sizes.

You’re basically padding the array to next larger power of 2, which changes its roots of unity. The most trivial example: {1,1,0} has no solution, but your answer is YES.

Is it really that hard to check small cases by hand when you have days for this?

23

@xelios I had given the incorrect link. I’ve edited it.Could you check it now?It works for 1 1 0.

24

Really awesome explanation @kevinsogo, I am always amazed by how clever and insightful some top coders can be and this is for sure an inspiration for me to keep working harder on my side to improve :smiley:

Thanks for the amazing story :wink:

3 Likes
25

jaskaran: Except it does not work for {1,1,0}. Read what I wrote again. Your solution answers YES, the correct answer is NO.

26

waw. amazing explaination throughout your trials and errors. thanks a lot, mate !

i’ll try to get AC with your ideas. thank you so much !

2 Likes
27

@kuruma @cyberax Thank you for your comments! I’m glad you liked the post. :smiley:

1 Like
28

@cyberax I will try to explain these questions more clearly and thoroughly. Thanks for your concerning.

1 Like
29

xelios:Why is it giving NO on my compiler but not on IDEONE?

30

@shangjingbo: thanks a lot.

31

@cyberax: updated :slight_smile:

4 Likes
32

I don’t know your platform, so I can’t answer that… but I’d expect the Ideone to be more similar to Codechef testing system…

33

Precision is usually not a problem. Ever. Out of hundreds of problems that require doubles among thousands I’ve solved, this is the 2nd one where I’m getting WA because of precisions errors.

34

@anton_lunyov: thanks for you explain!

35

sum of d * nu(d) is O(n * log(n), because sum of d is O(n) and max(nu(d)) is O(log(n)).

36

thank you for the update ! i tried to understand what did that check() function too… :slight_smile: well done !