No Strings Attached

I have replaced the current char by the max char occuring after it and had a count of (curr - max).Heres the problem link

https://www.codechef.com/JULY18B/problems/NSA

Jul 9, 2018 at 1:12pm

Someone please help me with this problem !!

Jul 9, 2018 at 2:52pm

blackmamba (122)

i have partially accepted solution for both NSA and NMNMX.
if anyone has fully accepted solution of any and wants partial of the other , DM me

Jul 11, 2018 at 4:20am

@wasp

why are changing with maximum character occuring.

zzzzzzzzaaab

take this example

Jul 11, 2018 at 5:33am

yes here i change every a to b to the answer is 3

Jul 11, 2018 at 5:41am

Why are you changing all a's?You can only change 1 letter in the entire string...

Jul 11, 2018 at 6:05am

I have come up with an O(n^2logn) approach but its still not good enough for 100pts :/

Jul 11, 2018 at 6:13am

@honeybuzz can you share your algo PM me

Jul 11, 2018 at 8:00am

@gear how can your solution be O(n) if it is brute force?I think you might be messing up the logic to reduce the complexity and hence are getting WA...Because using brute force to simply calculate the cost of the given string without even making any changes itself is O(n^2).

Jul 11, 2018 at 8:20am

@vigilante

In abcd
bcd > a so count 3
then cd > b so count 3+2=5
then c>d so count 5+1=6

Jul 11, 2018 at 9:07am

@Wasp actually my solution is just able to pass 1 test case of the last subtask...Hence even though its better than the brute force(since it passes only 3 cases), my solution passes just 1 more case...Moreover, the 2nd test case of the 2nd subtask still gave TLE...

Jul 11, 2018 at 10:34am

@honeybuzz

what algo u use for clearing last subtask . how u reduce time complexity..

Jul 11, 2018 at 10:45am