NOV18 - Problem Discussion

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:

HMAPPY1 can also be solved like this Codechef November Challenge 2018 | Appy Loves One ( HMAPPY1 ) - YouTube

This may help you Codechef November Challenge 2018 | Appy Loves One ( HMAPPY1 ) - YouTube

Considering I didn’t compete this time I’ll let gorre_morre make comments on CHEFEQUA if he wishes to. :stuck_out_tongue:

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

2 Likes

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.

Link - CodeChef: Practical coding for everyone

@tieros we are switching “fastest” for different tasks, but you get the lowest maximum. my code

1 Like

nice solution joffan, you’re even not using something like deque

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

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.

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.