Yes we can, though there is a small problem with your solution, the constraints state that ‘A[i][j]’ can also be ‘0’ since 0 doesn’t count towards the score, its frequency doesn’t matter, but you are considering that in your solution. A small change in the last loop of your solution to ignore the frequency of zero gets an ac. https://www.codechef.com/viewsolution/17561899
1 Like
@garrykevin, you are using float arithmetic here which is causing the issue, consider the following testcase where k is 3 and the string is ‘j’. since replacing j with 10 gives us benefit we should replace it. Now your solution stores it in rsum in the form 2.333333333 (assuming precision of 9 digits) when you convert it back it converts back to 2333333333/1000000000 though the precise answer should be 7/3 (as the actual value is 2.33 repeating). You are loosing precision while storing it as double. Instead store integer numerator and denominators separately.
In problem2. “Geno” can never win… that’s cool observation
Can anyone explain this line “For the substring which contain “x” in the middle we can visualise them as 2 parts, left and right and their mask being the “OR” of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O(ALPHA**2) we can find their contribution too.”,what does convolution means here and what is ALPHA?any help or reference to any tutorial for learnig such concepts is welcomed.
Thanx in advance!!
1 Like
thanks mate.
@vivek_1998299 ALPHA refers to alphabet size, which is 20 here. OR convolution refers to polynomial multiplication where c_0 x^{p_0} \cdot c_1 x^{p_1} = c_0c_1 x ^{p_0 | p_1}. To put it simply the coefficients at p_0 and p_1 affect p_0 | p_1 instead of p_0 + p_1.
This is relevant here in the following manner: assume you know there are c_0 substrings with mask p_0 that begin at “x”. Similarly there are c_1 substrings with mask p_1 that end at “x”. So there will be c_0c_1 substrings with mask p_0 | p_1 that contain “x” irrespective of where it lies.
2 Likes
Thanx a lot!!