For CHEFEQUA2, the algorithm for inversion of a system with power equations is given in Erich Kaltofen's Homepage . All that is required is a fast multipoint evaluation algorithm using FFT.
Can anyone share idea for solving pritree
0.14 sec, same with my solution. I donāt remember why I wrote so much code, but still fastest Python solution belongs to me 
https://www.codechef.com/viewsolution/21381609
1 Like
I so wanted to get 5 points from CHEFEQUA. I understood it requires something like FFT but still tried hard with Gaussian elimination, then tested my solution with n=10 custom test and it failed. FFT solutions looks too scary but I guess itās time to familiarize with it.
1 Like
even i used combinatorics for GMEDIAN but getting TLE: Can someone helpā¦?
My Solution Link: CodeChef: Practical coding for everyone
1 Like
@tushar2899 try to use some naive code as tester for your code. If your code was on the right direction it should not have failed for task 1 atleast. Check your approach and use some naive code for checking your direction of the code. I have included a naive checker below in my code 
HMAPPY1 can also be solved like this Codechef November Challenge 2018 | Appy Loves One ( HMAPPY1 ) - YouTube
Considering I didnāt compete this time Iāll let gorre_morre make comments on CHEFEQUA if he wishes to.
I know he had a blast with the problem. It boils down to speeding up polynomial calculations with NTT for quick convolutions and some cleverness, both of which are up his alley.
His last submission on the problem has rather clean code, so itās worth looking at: CodeChef: Practical coding for everyone
2 Likes
here is what I did :
- made an array of all the strings that have length > THRESHHOLD
- made the trie with interval for all other string that have length < THRESHOLD
For every query compute 2 results -
- one from the array (elems that fit in [L, R] inteval)
- one from trie
Output the max out of those 2.
1 Like
nice solution joffan, youāre even not using something like deque
CHEFEQUA was 2x multipoint evaluation i think, i guess in O(NlogN^2) standard approach with modulos of polynomials with FFT division, though it was too hard to code for me. One multi point is for some kind of convolution with vector C (can google solving transpose vandermonde system), other one is in derivative of (x-x_1)(x-x_2)..(x-a_n), since those are actually denominators of Lagrangian basis polynomials. Pretty hard i would say, and doable in few hours if you have done fft divisions before and can google good. NTT*
BINSTR -> query_sort_by_L + right_to_left_pass + min_seg_tree + min_trie_for_each_length + jump_pointers_for_each_string
I disagree that CHEFEQUA was a math mammoth especially compared to some other math based questions that I have seen in previous long contests. Maybe you should look at my answer on this thread.
For RECIPES there is a pretty joyful solution, whereas you would normally map bases to 2^0, 2^1, ..., 2^(10000), you now map them to random int [0, 2^64], and proceed normal xor, so probabilistic solution.
I didnāt intentionally make this a wiki. I thought some moderator did that. Strange. Changed it back now. Thanks @aryanc403!
Edit: That didnāt increase my reputation 
@arpit_2k your solution will not work for following testcase.
n=105 Ā Ā q=105
length of First String = 105
length of all other strings = 9
So your code will try to make Radix tree as follows:
It will append zeros to make the length of strings = 105
Now this makes the total Number of character to placed in Radix tree = 1010
1010 Characters nearly takes 40GB memory.
The TLE verdict you got, is actually because of the large number of nodes that are required to create.
If you run this code locally on such large input file, The OS will Kill the process because so much Memory cannot be allocated.
2 Likes
Damn, this problem was great! Learnt a lot. Thanks to your tip I have gotten Accepted on it.
Oh. I did not think of that.I guess Iāll slightly modify my approach and try to compress those strings or some other modification.