NSA - Editorial

editorial
, ,
13

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

1 Like
14

@melfice why are you using int64_t?

15

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 ?

16

Can someone point out where my logic goes wrong
https://www.codechef.com/viewsolution/19322490

17

Can anyone please tell why my code is giving WA for 2 test cases?
https://www.codechef.com/viewsolution/19349035

18

Please post solution link instead of entire code.

2 Likes
19

https://www.codechef.com/viewsolution/19225307

20

Hi! It indeed is {0, 1, 2, 1}. And code from editorial gives you the same result.

1 Like
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