NSA - Editorial

editorial
, ,
21

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

22

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

3 Likes
23

And also we get editorials on time :smiley:

1 Like
24

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

2 Likes
25

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.

2 Likes
26

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

27

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.

28

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

1 Like
29

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
30

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

why?

31

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

32

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