NOV18 - Problem Discussion

general
,
30

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
31

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

32

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

1 Like
33

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

35

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*

36

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

38

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.

40

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.

41

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

42

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

2 Likes
43

Damn, this problem was great! Learnt a lot. Thanks to your tip I have gotten Accepted on it.

45

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.

46

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

47

So this is another bug in Discuss then.

49

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?

52

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

1 Like
53

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

54

Haha, nice comment @ducpro :))

55

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.

56

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