I used a double ended queue for solving HMAPPY1, by storing count of consecutive 1’s and 0’s. Like for case: 1 1 0 0 0 1 1 deque contains: 2 -2 2. I found that max value after rotation depends on front and rear too.
Can anyone tell what I could do to improve my solution to BINSTR (CodeChef: Practical coding for everyone). I’ve implemented a radix tree and for input strings of different lengths, I’m padding the shorter strings with 0’s initially.
My solution gives TLE on tasls 5, 7, 8 but runs in <= 0.08 seconds on all the other.
About CHEFEQUA, I think that @psaini72 solution is great. But here is what I did:
When I first saw the problem I recognized that the matrix in the problem is the transpose of something called a Vandermonde matrix, usually denoted V. This is a well known type of matrix and from some googling I found On the Inversion of Vandermonde Matrices pretty much telling me how to solve this problem. Note that the inversion formula for V^T contains V, which will essentially be just a multipoint evaluation of a polynomial at points A_0,A_1,…,A_{N-1}. So all I needed to do now was to implement a multipoint evaluator for polynomials.
My favorite source for FFT algorithms are these lecture notes. It shows how to reduce multipoint evaluation to polynomial modulu at a cost of O(N \log^2 N). After looking around I also found these lecture notes on how to implement polynomial modulu in O(N \log N) using convolution based on FFT or NTT. Later on I even found that someone had already implemented this specific algorithm in python. This implementation is probably pretty slow and there are some things that could be done differently so I made my own implementation in C++, still it should be pretty easy to rewrite the python code into a somewhat quick fully working C++ code if you just want to solve the problem.
Finally after getting accepted I noticed that I only got a running time of 2.3 s while some people got around 1.2 s, so I tried to speed up the algorithm. After playing around with the algorithm for a bit I noted that what slowed everything down was that I used 4 mod operations in the deepest part of my NTT. After some thinking/rewriting I was able to get it down to using a single mod operation, speeding up the algorithm significantly. Currently I’m pretty happy with my implementation, it is both pretty clean, readable and especially the NTT is noticeable quicker than most implementations I’ve seen. All in all I got it running in under <1.2 s. I could probably even get it under 1 s by reusing some calculations.
Can somebody suggest test cases for GMEDIAN on which my code is failing?
https://www.codechef.com/viewsolution/21621610
First I found the number of odd subsequeces by: 2^(N-1)
I have used following variables:
l=length of contiguous subsequence containing elements less than that number
r=length of contiguous subsequence containing elements more than that number
d=length of duplicate string
Then,I have choosen the duplicate subsequences containing of even length and then choosen equal elements from left and right side
EXP:{ C[l,0]C[r,0] + C[l,1]C[r,1] +...+ C[l,l]C[r,l] }X{ C[d,2]+C[d,4]+...+C[d,d OR d-1] }
EXP:{ C[N-d,l] }X{ 2^(d-1)-1 }
BECAUSE: l+r = N-d
Then,I have choosen the duplicate subsequences containing of odd length and then choosen unequal elements from left and right side(by diff of 1)
EXPR 1:{C[l,0]C[r,1] + C[l,1]C[r,2] +...+ C[l,l]C[r,l+1] }X{ C[d,3]+C[d,5]+...+C[d,d OR d-1] }
EXPR 1:{ C[N-d,l+1] }X{ 2^(d-1)-d }
EXPR 2:{C[l,1]C[r,0] + C[l,2]C[r,1] +...+ C[l,l-1]C[r,l] }X{ C[d,3]+C[d,5]+...+C[d,d OR d-1] }
EXPR 2:{ C[N-d,l-1] }X{ 2^(d-1)-d }
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.
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.
@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
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.