Unofficial Editorials November Cook Off

Reading problem statements and constraints require a lot of patience mate!!!

I too wasted much time on ONCHESS, instead of writing brute force, i went for the mess i explained above. :stuck_out_tongue:

1 Like

Writing editorial in ~20 min or so.

Thanks Mateā€¦

@nik_84 . Most probably in your case NZEC is caused because of Stack Overflow Error. Try reading this on how to avoid it : JAVA - Stack Size - Recursion Limit - general - CodeChef Discuss .

1 Like

Beautiful Logicā€¦

Thereā€™s one more solution CodeChef: Practical coding for everyone

Failed because of this while same solution in c++ passed.

I was wondering on how people did it using FFT. Nice trick man!!

Before their recent memory changes, i.e. in the age of fairies, demons and dinosaurs (i.e. this Jan,2017), even a recursion depth of {10}^{6} was acceptable in JAVA. But now its something less than {10}^{5}ā€¦

@aayushkapadia can you please explain ā€œSome Mathematics before Moving Furtherā€ this part a little more? how did (x^0 + x^1 +ā€¦) comes ? i mean why does the numbers are in powers ?

and also how we are making sure of the fact that the resultant string is palindrome as if any pair with case2 left then the string wouldnā€™t be palindrome !
i know i am missing something please help .

@vijju123 I tried to run your code for an array of size 500X500 and populating it by randomly generated numbers. It does not fit in time limits. It runs well for size ~200X200. Please correct me if I made some error in your original code. Your code: mYM9sw - Online C++ Compiler & Debugging Tool - Ideone.com
I think it is because of that extra factor in your time complexity.

Thats because the random test data has 0 in between. I have specifically instructed DFS function to instantly return if it encounters a ā€œ0ā€ in array, as 0 means it is going out of bounds (I decalred array of larger sides, this means that if index goes above 1000 or less than 1, it will encounter 0 and instantly return).

If 0 is in array, then my DFS wont even count it visited, it will immediately return. This causes an infinite loop.

Though idk if it will run in time even after correcting this XD

My codeā€™s complexity is O(N*M*X) where X is number of times I will have to repeat those tedious N*M operations of finding maxima, and doing DFS from them.

In worst case, I can visit only 4 more cells from current highest cell, then X= (N*M)/5. But I doubt you need the worst case to time my code out.

My code ran rather quickly- 0.16 seconds only!
(TBH, I submitted it just ā€œfor sake of itā€. I knew it will TLE, but idk I decided to give a try before wasting more time on that Q :stuck_out_tongue: )

(Now now, dont be so cruel on this poor man. His approach is 90% correct :3)

Oh! I did not see that in your dfs. But it still wonā€™t run without the zeros. If you do not traverse each to find the max element it will work fine I suppose.

@rumblefool Yes, if I store and sort the elements, instead of performing o many operations to find next maxima, it will fit in the time limit. Thanks for working on my solution :slight_smile:

That was just for killing time btw. I was getting bored and saw your comment and thought of testing your code for a larger input. Btw I also got AC solution in SEPT Long Challenge with an n^2 time complexity (n~10^5)that should ideally have failed. But the cases were not so robust after all. All in good spirit! :smiley:

Yup, thank you :slight_smile: . (BTW, I am glad theres no ā€œHACKING PHASEā€ here like CFā€¦:stuck_out_tongue: XD)

1 Like

FFT seems to apply everywhere in combinatorics. :slight_smile:

Hahaā€¦ @vijju123

@pk301 You can read about how to solve counting problems using polynomials (generating functions) in this link : Brilliant | Learn interactively .

For case 2 pairs we are changing 1 character or 2 characters to change it to case 1. And hence its polynomial only contains coefficient of x^1 and x^2.And coefficient describes how many ways are there to change it. Visit the link above to see some example mentioned.

1 Like

Always the unique solutions, with even better references. :slight_smile: @aayushkapadia

1 Like