What you are missing is, when you change the character, you only consider impact on one size, you do not consider the impact on the other side. My solution is similar to yours. In case of doubt check CodeChef: Practical coding for everyone

If testers and authors are not competing why donāt they write more readable code?

And also we get editorials on time

Unluckily editorialist gave all editorials of questions I already solvedā¦ And editorials for questions I donāt know are not out yet !!!

Contest Lasts for 10 days and editorialist gets solutions from starting of contestā¦ they why this much delay ? If you donāt have time then why to apply as editorialist ???

Please look into this

@admin

@mgch

@vijju123

Hi! My apologies for this inconvenience. The reason why editorials are delayed is that I had relocation due to internship and it definitely didnāt go as well, as I expected month ago when I applied to be an editorialist. I even had to live in a hotel for a while, because securing long-term accomodation here is a huge pain. Now when these things are settled, I do my best to prepare editorials as soon as possible. Please, be patient.

If editorials are unclear, please feel free to point me on particular parts which are difficult to understand and Iāll try to explain it in simpler manner.

@melfice can you explain this problem in a simpler way. I am facing difficulty with understanding the dp part.

B[i][c] - number of letters less than c before position i.

So adding up all B[i][S[i]] = Base cost.

F[i][c] - number of letters greater than c after position i.

This is computed because to calculate the cost of changing a char we need to know its impact on the right side of the string.

Try printing out the variable cunt for different input strings and see if it is correct.

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.

So adding up all B[i][S[i]] = Base cost

why?

Thanks for efforts. I got it already. I felt this problem was more difficult then the next most solved problem in july Challenge.

because itās codechef they consider dp+trees question easy