NOV18 - Problem Discussion

general
,
41

Oh. But this still needs to be fixed. Why should upvotes done on wiki post not add to the karma after un-wikifying the post?

42

You can do without random mapping. In that case, you will have to implement your own bitset class. My Soln
Query Complexity - O(Q*K*K*N/64) and this is fast enough for given constraints.

43

Noobie here: Please explain the 1st problem CHFTIRED

44

In one line answer is yes irrespective of given values.
Reason -
Without loss of generality, we can assume a>b and x=a-b
Then adding d in b and d-1 in a => a+d-1 , b+d. Now diff becomes x-1. So repeating this process x times makes a+x*d-x=b+x*d

45

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.

8 Likes
46

How the heck is THAT fast enough? Doesnā€™t make any sense to me.

1 Like
47 
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             }
48

@temp1234

Hereā€™s a test Case on which your program is failing.

1

8

1 2 2 2 2 3 3 3

The correct answer is 196 while your code outputs 192.

49

@masood786

Thanks

50

Thanks a ton ! :smiley: I already read your reply though XD

51

//can anyone explain me ? what is the concept behind goodmedian questionā€¦ how to solve it for 100 points ?

52

Haha, nice comment @ducpro :))

53

No Iā€™m serious. I originally implemented your idea with a complexity of O(Q * K * K * 64) and it already TLEd on subtask 2. That monstrosity of a complexity passing in 0.15 secs is just beyond my understanding.

54

@ducpro The worst case which I can think of for my code.
Q=N=20000, K=30
I made sure that all loop run up to their maximum value.
That too takes only 0.24 sec.
Maybe because of bitwise operations, It is running faster?

55

For CHEFEQUA2, the algorithm for inversion of a system with power equations is given in http://www4.ncsu.edu/~kaltofen/bibliography/88/KaLa88.pdf . All that is required is a fast multipoint evaluation algorithm using FFT.

1 Like
56

Can anyone share idea for solving pritree