Hey Guys , Can anyone help me with BinaryStrings , I tried making a TRIE and taking maximum of the input length of the string and padding all others with same 0s to make the strings equal , any query string with length greater than this , I took a substring of the the appropriate length (max length that is ), i searched in TRIE as usual and each node with indices which pass through that number were stored , I calculated the one in range linearly , It passed most of the cases but TLED in(5,7,8,14)My solution :-https://www.codechef.com/viewsolution/21596350
Can someone please suggest why this is so are the input strings too big such that you cant pad everyother string or is it due to the way i search in Ingervals
Side Note :- Also there was Sigsegv before for the cases not TLED , did it exceed memory Requirement in anyway ?Any help is appreciated! Thankyou :D:D
RECIPES
I used Gauss Elimination + Bitmasks. My Soln
CHEFEQUA
I used O(n^3) to find the inverse of a matrix and fetch 5pts. My Soln
GMEDIAN
My approach was to count Bad Sequences. Only matrices with even length(2*n) and different element on n and n+1 position are bad. My Solns O(n*logn) O(n^2*logn) . I recommend reading O(n^2*logn) first.
Let Sequence Length = 2*n
GMEDIAN 100 pts = 2^n - (Even length elements with nth , n+1th element are different.)
Run a for loop fixing nth element.
Let no of elements less than x.X be cnt. And no of elements less than and equal x.X be cnt+x.Y. No of ways different first half = C(cnt+x.X,n) - C(cnt,n)
nth element x.X = All sequences with nth element <= x.X - All sequences with nth element < x.X
MAXDTREE
I first made a hypothesis that all no which contains only 2 as digits are present. Running it offline gave me 222. Rest all no up to 2222222222 (10 digits) were present in this recurrence.
I changed the hypothesis in All no of form 222…2222 are present in this recurrence except 222. My Soln (20 pts)
BINSTR
My code is of 415 lines uncommented. I will keep job of explaining soln of this for editorials and other community members.
Click to view
TRIE + 2 segment trees +two overlap functions (although one is sufficient) + 1bf fn + 1 soln fn + 1 search fn + 2dfs fn(although 1 is sufficient) + 2 debug fn + string to int conversion + int to string conversion.
Chef Vijju Corner -#
Click to view
@vijju123 named my trick of checking upto 2222222222(10 digits) and assuming rest to be true as -
Click to view
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
My soln is an online soln. But because it is very long. I have to reread It so I skipped that. 
My Solution (100pts)
Since the sequence C is not really restricted to have only N elements, I made a generating function for it. What you get is:
\displaystyle C_0 + C_1x + C_2x^2 \ldots = \sum_{i=0}^{N-1} B_i(1 + A_ix + A_i^2x^2 + \ldots) = \sum_{i=0}^{N-1} \frac{B_i}{1-A_ix}
\displaystyle \text{Now let } Q(x) = \prod_{i=0}^{N-1}(1-A_ix)
If I multiply Q to both sides of this, on the right I get a polynomial of degree N-1 i.e. N coeffients.
Since the first N coefficients of the product depend only on the first N coefficients of the 2 polynomials being multiplied, I can write the right side as \displaystyle \frac{P(x)}{Q(x)} where P(x) = The first N coefficients of \displaystyle (C_0 + C_1x + C_2x^2 \ldots + C_{N-1}x^{N-1})Q(x)
\displaystyle \therefore \frac{P(x)}{(1-A_1x)(1-A_2x)\ldots(1-A_{N-1}x)} = \frac{B_1}{1-A_1x} + \frac{B_2}{1-A_2x} \ldots \frac{B_{N-1}}{1-A_{N-1}x}
This is a partial fraction decomposition and the solution is given by \displaystyle B_i = -A_i\frac{P\left(\frac{1}{A_i}\right)}{Q'\left(\frac{1}{A_i}\right)} where Q' is the derivative of Q (cover up method).
If we further let P^*(x) = x^{N-1}P\left(\frac{1}{x}\right) i.e. the polynomial we get by reversing the coefficient list of P and similarly Q^*(x) = -x^{N-1}Q'(\frac{1}{x}) we get
\displaystyle B_i = A_i\frac{P^*(A_i)}{Q^*(A_i)}
We can find out the values of P^* and Q^* at any N points in O(N\log^2 N) using the algorithm described here.
An example in case anyone doesn’t get it. I’ll be using the sample test case for this.
Q(x) = (1-x)(1-2x)(1-3x) = 1-6x+11x^2-6x^3
P(x) = \text{First 3 coefficients of } (3+6x+14x^2)(1-6x+11x^2-6x^3) = 3 - 12x + 11x^2
P^* (x) = 11-12x+3x^2
Q'(x) = -6 + 22x - 18x^2
Q^* (x) = 18 - 22x + 6x^2
\therefore B_0, B_1, B_2 = \text{value of } \displaystyle x\frac{11-12x+3x^2}{18-22x+6x^2} \text{ at } x=1,2,3 \text{ respectively.}
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.
How the heck do you solve RECIPES? The only solution I know is checking if there’s a subset XOR = 0, and for this I check for each bitset if there’s a subset not having it that XOR is equal to it. Performed Gaussian Elimination, however, there are N equations and K variables maximally, which bring a query’s complexity to O(NK^2), and this of course TLE out even on subtask 2. So how did you guys Gauss? What were the equations, and what were the variables?
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.
Link to my solution : https://www.codechef.com/viewsolution/21546305
Why you made this as wiki ??
Can you unwikify it?
Wiki post don’t add karma to user.
@vijju123 kan you help him??
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.
Can anyone tell what I could do to improve my solution to BINSTR (https://www.codechef.com/viewsolution/21589740). 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.
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.
Damn, this problem was great! Learnt a lot. Thanks to your tip I have gotten Accepted on it.
All upvotes done on wiki post didn’t add. But new upvotes will increase reputation.
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.
@insanity_123 Kindly read the reply I gave to @arpit_2k on this thread below. If you are padding zeros then you are also having bug similar him.
So this is another bug in Discuss then.
Nope, it is not a bug.