How do we arrive at the formula Y=Y0−(B[i][c1]+F[i][c1])+(B[i][c2]+F[i][c2]) ?
Well, main idea is to try every possible change. If you change s_i from c_1 to c_2 then you will have to subtract contribution of c_1 and add contribution of c_2. Contribution of c on position i is equal to \#\{j< i|s_j< c\}+\#\{j>i|s_j>c\}. Arrays B[i][c] and F[i][c] just implement these values for each pair of position i and letter c on this position, so you can know new score after change efficiently.
1 Like
Thank you for the clear and informative editorial. It helped me understand and submit a valid solution. Cheers!
So adding up all B[i][S[i]] = Base cost
why?
Needed little explanation on how we reach to that formula.
because the solutions provided are barely readable.
Thanks for efforts. I got it already. I felt this problem was more difficult then the next most solved problem in july Challenge.
I wish the editorial to be more explanatory. Maybe by taking an example string and then showing the arrays B and F for that. Next time maybe 
Hey, I have a query, If we change the letter at some jth position in the string then why are we not updating all the F[i][c] where i<j because due to the change at jth position there is a possibility that the updated letter at jth position becomes greater than then letter at some ith position but initially the not-updated letter was lower than the letter at that i’th position ?
Can anyone please tell why my code is giving WA for 2 test cases?
https://www.codechef.com/viewsolution/19349035