×

# NOV18 - Problem Discussion

 4 1 copy paste Hey guys!! Finally after 10 tiring days the A̶u̶g̶u̶s̶t̶ November long concludes. Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over :) So, which was your favourite problem? I had best time solving ̶I̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ ̶M̶a̶t̶r̶i̶x̶ ̶:̶)̶.̶ MAGICHF2 ̶T̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶g̶a̶v̶e̶ ̶m̶e̶ ̶a̶ ̶r̶u̶n̶ ̶f̶o̶r̶ ̶m̶y̶ ̶s̶c̶o̶r̶e̶ ̶x̶D̶ ̶-̶ ̶s̶o̶ ̶I̶ ̶l̶e̶t̶ ̶h̶e̶r̶ ̶s̶t̶a̶y̶ ̶w̶i̶t̶h̶ ̶d̶r̶a̶g̶o̶n̶s̶ ̶a̶n̶d̶ ̶b̶e̶ ̶b̶y̶ ̶h̶e̶r̶s̶e̶l̶f̶ ̶t̶h̶e̶n̶ :p But on a serious note, anyone who was able to MAXDTREE s̶a̶v̶e̶ ̶t̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶(̶o̶r̶ ̶p̶r̶i̶n̶c̶e̶.̶.̶.̶? :p). I kept on getting TLE W̶A̶ for larger TCs, so I appreciate any approaches for it :) P.S. - If someone can write something on interpolation (s)he is most welcomed. I invite @gorre_morre and @algmyr for this task. (:( Tagging here don't send any notification.) I derived some required equations for CHEFEQUA, didn't check the correctness of those equations because I knew even I these are correct then time left for the contest in insufficient to implement those. Let the discussion begin! /copy paste asked 12 Nov '18, 15:53 2.3k●1●5●16 accept rate: 10% 1 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. (12 Nov '18, 17:13) tieros4★ 3 Considering I didn't compete this time I'll let gorre_morre make comments on CHEFEQUA if he wishes to. :P 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: https://www.codechef.com/viewsolution/21514506 (12 Nov '18, 17:59) algmyr7★ 1 Gaussian elimination trick gives 5pts for CHEFEQUA. My Soln (12 Nov '18, 23:50) 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* (13 Nov '18, 01:22)

 17 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.}$ answered 13 Nov '18, 11:18 4★psaini72 283●1●11 accept rate: 25% Why you made this as wiki ?? Can you unwikify it? Wiki post don't add karma to user. @vijju123 kan you help him?? (13 Nov '18, 18:05) 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 :| (13 Nov '18, 19:29) psaini724★ All upvotes done on wiki post didn't add. But new upvotes will increase reputation. (13 Nov '18, 20:32) So this is another bug in Discuss then. (14 Nov '18, 00:27) Nope, it is not a bug. (14 Nov '18, 00:39) 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? (14 Nov '18, 00:51) showing 5 of 6 show all
 8 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. answered 14 Nov '18, 06:58 954●2●10 accept rate: 42%
 3 "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 answered 12 Nov '18, 21:29 5★abba5 113●3 accept rate: 0%
 3 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 :P ). answered 13 Nov '18, 00:25 32●3 accept rate: 0% 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. (13 Nov '18, 11:30) psaini724★

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

View Content

# Chef Vijju Corner -

View Content

2.3k1516
accept rate: 10%

BINSTR -> query_sort_by_L + right_to_left_pass + min_seg_tree + min_trie_for_each_length + jump_pointers_for_each_string

(13 Nov '18, 05:46)

My soln is an online soln. But because it is very long. I have to reread It so I skipped that. :P

(13 Nov '18, 06:16)
 1 1. For HMAPPY1: I used Segment Tree. Though, it can be done with Bruteforce on Strings. Here is my Code 2. For GMEDIAN: I used combinatorics approach as the naive submission had complexity O(2^n) which can be seen as a pattern. Here is my Code. 3. For MAGICHF2: This was a simple problem. All you needed is a correct direction of moves and evade some edge cases Here is my Code. 4. For BINSTR: I used Trie with Intervals for this problem. The main issue with this problem is different lengths with larger differences between max length and second max length and the larger number of zeros to be appended which I saved beforehand to prevent again and again traversal. Here is my Code. If you feel like I should comment the code, or you have any queries in the code, you are free to ping me here :) answered 12 Nov '18, 17:01 318●1●10 accept rate: 1% 1 even i used combinatorics for GMEDIAN but getting TLE: Can someone help....? My Solution Link: https://www.codechef.com/viewsolution/21612107 (12 Nov '18, 17:14) @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 :) (12 Nov '18, 17:21)
 1 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. answered 13 Nov '18, 18:38 4★arpit_2k 21●1 accept rate: 0% 2 @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. (13 Nov '18, 19:30) 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. (13 Nov '18, 20:54) arpit_2k4★
 1 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. answered 17 Nov '18, 12:58 7★wmoise 97●2 accept rate: 9% 2.3k●1●5●16
 0 What can be even faster way for this problem "HMAPPY1" Problem Link: https://www.codechef.com/NOV18B/problems/HMAPPY1 My Solution: https://www.codechef.com/viewsolution/21609881 my solution was only able to get me partial points....... answered 12 Nov '18, 16:23 272●1●9 accept rate: 8% 2 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 :P https://www.codechef.com/viewsolution/21381609 (12 Nov '18, 17:08) tieros4★ HMAPPY1 can also be solved like this https://www.youtube.com/watch?v=T47EFVOJbgc (12 Nov '18, 17:43) 1 @tieros we are switching "fastest" for different tasks, but you get the lowest maximum. my code (12 Nov '18, 18:09) joffan5★ nice solution joffan, you're even not using something like deque (12 Nov '18, 19:19) tieros4★
 0 Can someone share his/her approach of binary string? It has really weak test cases, my brute in PYPY passed with a fast IO. In the test cases, there was a large string only, so without inserting it in the trie, one could solve it. But can someone share an approach which runs for large and strong test cases.? answered 12 Nov '18, 16:59 51●4 accept rate: 0% 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. (12 Nov '18, 18:05) inseder6★
 0 Please suggest some test case for which my HMAPPY1 solution should fail, because I am only able to pass few test cases, and others are showing wrong answer.I tried all the possible combination of arrays but still many test cases showing wrong answer. Problem Link My solution answered 12 Nov '18, 17:43 3★ulti72 11●2 accept rate: 0% This may help you https://www.youtube.com/watch?v=T47EFVOJbgc (12 Nov '18, 17:52)
 0 https://www.codechef.com/viewsolution/21550313 My solution to HMAPPY1... segment tree not used.. is based completely on analysis answered 12 Nov '18, 17:57 3★yaminote 42●1 accept rate: 0%
 0 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 :( answered 13 Nov '18, 00:06 5★abhi2402 112●4 accept rate: 40%
 0 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? answered 13 Nov '18, 17:21 6★ducpro 259●1●8 accept rate: 0% 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. (13 Nov '18, 18:14) Damn, this problem was great! Learnt a lot. Thanks to your tip I have gotten Accepted on it. (13 Nov '18, 20:18) ducpro6★ 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. (14 Nov '18, 01:16) 1 How the heck is THAT fast enough? Doesn't make any sense to me. (14 Nov '18, 09:48) ducpro6★ Haha, nice comment @ducpro :)) (15 Nov '18, 03:57) 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. (15 Nov '18, 08:30) ducpro6★ @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? (15 Nov '18, 10:36) showing 5 of 7 show all
 0 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 answered 13 Nov '18, 17:32 11●1 accept rate: 0%
 0 Noobie here: Please explain the 1st problem CHFTIRED answered 14 Nov '18, 01:53 0●1 accept rate: 0% 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$ (14 Nov '18, 03:45)
 0 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 } answered 14 Nov '18, 11:01 3★temp1234 1●1 accept rate: 0%
 0 @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. answered 14 Nov '18, 11:44 106●3 accept rate: 13%
 0 Thanks answered 14 Nov '18, 15:00 3★temp1234 1●1 accept rate: 0%
 0 //can anyone explain me ? what is the concept behind goodmedian question.. how to solve it for 100 points ? answered 15 Nov '18, 00:37 1 accept rate: 0%
 0 Can anyone share idea for solving pritree answered 19 Nov '18, 10:14 3★mk_g 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×398
×154

question asked: 12 Nov '18, 15:53

question was seen: 4,137 times

last updated: 19 Nov '18, 10:14