NOV18 - Problem Discussion

“HMAPPY1”
first find 2 max size substring and store their first and last pointer and when shift queries come you just move 4 points and for length query you just need to check size of both substring both query thake O(1) time

https://www.codechef.com/viewsolution/21397995

“GMEDIAN”
Its simple observation you for making odd length subset you have 2^(n-1) possible way i proved that with equation (l+r) C (l) way to choose elements in array at (l+1) position where (l+r+1) = n

Now for even length we need to check frequency of number and after some observations you can find solutions with O(n²) so total time complexity O(n²)

https://www.codechef.com/viewsolution/21483295

“MAGICHF2”
If N is even than we need to divide N like after devide N is two part one part still can divide by 2
But for odd we need to add one into it
And after logN/K iteration you can find its probability.

https://www.codechef.com/viewsolution/21521761

"CHEF and Eq "
First i tried with Gaussian elimination in O( n³ ) but after reading some papers i can make in O(n²)
Its known as vandermonde matrix.
And i read about FFT i think that it will be solutions of it
May be using MOD root of unity.
I can’t solve it for 100 point.

O( N²) for more information

https://discuss.codechef.com/questions/80978/sata05-editorial

" MaxDigit "

For subtask 1 we just need to know how many paths are passing from node 1 in s using dfs an after than remove node from distance 3 and ( Children of root C 2 ) from ans…

I didn’t paste partially point solutions you can check

For prime tree and Chef and recipe i used brute force approach for partially point
I got TLE in BinXor

3 Likes

The test cases for Binary Strings were very weak, I have seen many PYPY solutions where just brute force was applied and they got AC. It just kills the main motive behind the problem and a language advantage is the last thing I want to see on Codechef. I myself was not able to solve the problem and seeing so many people get AC using only brute force is saddening :frowning:

I am eagerly waiting for Editorial of CHEFEQUA , RECIPIES, and MAXDTREE. I was only able to grab partial points.

RECIPES: These type of Half-second question are really interesting. (CPCOMP) Last time. One can definitely relate merging of elements. @bciobanu or @gorre_morre anyone else who could enlighten about variants of these kinds of problems would be help to all. I am really eager to know different approach to solve such merging question.

CHEFEQUA: A Math-Mamoth I would say. One could easily figure out 20 point solution using Vandermonde Matrix to solve Linear System of Equation. After some more efforts one could relate it with FFT and Interpolation. The giant Task lies in connecting it question. I spent a lot of time going through different articles and Tutorial about FFT and Interpolation. Unfortunately, I couldn’t figure out the solution for question. @taran_1407 expecting a gem from you again.

MAXDTREE: One can check the length of patterns with occurrence of 2 using program to generate series and easily deduce that pattern for 2 exist for all, but length 3. I am totally blank about that 100pt approach. Waiting for editorials.

An awesome contest, I would say. Learnt a lot ( though couldn’t implement everything :stuck_out_tongue: ).

2 Likes

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 :-CodeChef: Practical coding for everyone
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

1 Like

CHEFEQUA:

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.}

18 Likes

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 : CodeChef: Practical coding for everyone

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.

1 Like

Noobie here: Please explain the 1st problem CHFTIRED

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.

7 Likes
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             }

@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.

@masood786

Thanks

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

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 :stuck_out_tongue:
https://www.codechef.com/viewsolution/21381609

2 Likes

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 :slight_smile: