Change each a[I] from a to z and take the sum everytime of its cost and how many elements are greater than it and check for minimum value every time ....
@hii each number appears a total of (n-1)C(k-1) times.
we need to find how many times that number appers at the coners and subtract that from the total!! hope that helps
write down a few examples.
Calculate how many total times each index shows up(no matter in middle or on sides)(hint: it would be equal for every index)
Then calculate how many times each index shows up on boudaries in a subsequence(first or last).
Then subtract it from total and there u are!!
@all for NSA brute force if u are changing a particular value of string again and again and then changing it back, then dont copy whole string, just copy the index u want to change, that did the trick for me to get from 10 to 30
I had already solved NSA 100pts so here are few hints on NSA.
1) Use Fenwick Tree to count the pairs(S[i] < S[j])
2) There is no shortcut approach to know which char in string to be replaced, so you have to check for each char from [a-z].
3) Step 2 might look like brute force approach but try to achieve in O(n).
I have optimized the solution of NSA to O(n), but I am getting WA for tasks 1 and 2 of subtask 3.
I have used the dynamic programming approach to optimize my solution. I can't find the error. Please, can anyone tell me what possibly be wrong in my code?