Codechef Long Contest

[nikita00]

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

even after reading the editorial i am not able to get what actually we are doing so please could someone explain me with suitable examples!

[stav]

I'm just a student so this might be wrong, but here's how i interpreted it:

The program:
Basically you are asked to create a program that takes in a string as an argument and outputs the number: X + Y

(and you want X+Y to be as small as possible)

Finding X:
When your program starts you are allowed to change ONE of the letters in your string. But you dont have to do this.

X is the difference in ASCII value of the two letters that change.

So, for example, if you are given the string "abc" and you change the letter "a" to a "d":
"a" has the ASCII value: 97
"d" has the ASCII value: 100
So the difference (X) is 3 (because 100-97 = 3)

if you dont change the string then the difference (X) will always be 0.

(you may think that you should never change the string then, because then X will always be 0. But you have to keep in mind that changing one of the letters may result in Y becoming many times smaller so the overall the output of the program (X+Y) is smaller )

Finding Y:
I'm not 100% sure about this part but here is how i understood it:

Basically you have to choose two (a pair of) indices in your string array.
The two indices are denoted as i and j.

BUT you cant just choose any pair of indices, the two indices you choose must follow these "rules":

1) i must either be 1 or larger
2) i must be less than j
3) j must be less than or equal to the length of the string

4) The ASCII value of the character at index i must be less than the ASCII value of the character at index j

There may be 0 or multiple pairs that follow these rules.

Y is the number of pairs that follow the rules.


Hard part:
The hard part is that your program MUST output the smallest possible number.

So for example if you are given a string
and you dont change a letter in the string: then X will be 0 and Y will be 10. Output 10.
But if you instead change one of the letters so that X is 3 that could result in Y only being 4. Output 7.


How to solve it:
i have no idea :-(

Perhabs somebody can confirm whether my interpretation is correct, and how to solve it?

[nikita00]

@stav you gave a great explanation but i more anxious about how would we solve this question! i didnt quite get from the editiorial.. :(

[dhayden]

Stav, I think your explanation has one small problem. Rule #3 for the values of i and j is that i must be less than or equal to j. So basically a naive way to compute Y is:

string S;
...
unsigned Y=0;
for (size_t i=0; i< S.size()-1; ++i) {
    for (size_t j=i+1; j<S.size(); ++j) {
        if (S[i] < S[j]) ++Y;
    }
}

Here are the examples and solutions:

abcd -> aacd  X=1 ('b'-'a')    Y=5 (ij pairs are 13, 14, 23, 24, 34)
dbca -> dcca  X=1 ('c'-'b')    Y=0
dcba -> dcba (no change)  X=0 Y=0

Now to solve it? Hmm. Consider one position in the string. When you change it, it affects Y only for the pairs that involve that position. I guess you could compute the best X+Y value for changing that position. Then move to the next position and do the same.