NSA - Editorial

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

1 Like

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


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.

1 Like

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

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


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