- Forum
- General C++ Programming
- Competitive progrsmming
Competitive progrsmming
i am finding difficulty in finding x how should i find that? i can find Y in nlogn but not able to get the value of x
You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.
Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.
Find the minimum possible value of X+Y.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string S.
Output
For each test case, print a single line containing one integer — the minimum value of X+Y.
Constraints
1≤T≤20
1≤N≤10^5
S contains only lowercase English letters
Subtasks
Subtask #1 (10 points): 1≤N≤50
Subtask #2 (20 points): 1≤N≤250
Subtask #3 (70 points): original constraints
Example Input
3
abcd
dbca
dcba
Example Output
6
1
0
You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.
Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.
Find the minimum possible value of X+Y.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string S.
Output
For each test case, print a single line containing one integer — the minimum value of X+Y.
Constraints
1≤T≤20
1≤N≤10^5
S contains only lowercase English letters
Subtasks
Subtask #1 (10 points): 1≤N≤50
Subtask #2 (20 points): 1≤N≤250
Subtask #3 (70 points): original constraints
Example Input
3
abcd
dbca
dcba
Example Output
6
1
0
Last edited on
I don't get abcd
change b to c for example
accd, cost 1
ac, cd +2
= 3?
changing b breaks the old substring ys of abcd, abc and bcd and bc, all 4 now fail that test because its pure < not <= and the cost to get rid of those is 1 so net gain of 3
what do I not understand?
change b to c for example
accd, cost 1
ac, cd +2
= 3?
changing b breaks the old substring ys of abcd, abc and bcd and bc, all 4 now fail that test because its pure < not <= and the cost to get rid of those is 1 so net gain of 3
what do I not understand?
Last edited on
I totally misunderstood the question. It's just counting how many pairs of indices satisfy the condition. I thought it was counting the differences in the letters that satisfy the condition.
Last edited on
I showed that for the first one x is 1, y is 2. x+y =3, unless you can tell me otherwise. I am asking why a cost of 1 change (x) does not reduce the total?
that is,
what is the answer for
"accd"
??
that is,
what is the answer for
"accd"
??
The cost for accd is:
1. a to first c
2. a to second c
3. a to d
4. first c to d
5. second c to d
Plus 1 for changing b to c, for a total of 6.
1. a to first c
2. a to second c
3. a to d
4. first c to d
5. second c to d
Plus 1 for changing b to c, for a total of 6.
I see. you are saying si and sj are strict boundaries, and ignore the middle.
Last edited on
I'm assuming it doesn't include the in-between ones. But those questions (especially codechef) are so badly described and their examples are so bad (and not explained) that it's maddening. That's what I hate most about this "competitive" programming. In real programming, you can ask for clarification.
the point of these nonsense competition questions is they avoid well known problems usually.
Here is what I would do. It may or may not be right...
- write a routine to get the score of the unchanged string.
- now, no matter what we do, we can't exceed or even equal the base cost of the unchanged string, so any change to the string has to actually reduce the cost below the original score. So, for changing abcd to zbcd is right out, as a to z costs a lot of points.
-to be cost effective, a change has to eliminate some of the i to j valid strings to reduce the Y count.
- so, you need an algorithm that can make a change that eliminates some of the Ys and costs less than the number of things it eliminates. To do that you need all the i to j substrings and a way to look at them to find a common letter that, if changed, invalidates them. That appears to be the first and last letter. so if you had 10 strings that started with the letter a and the ending letter max of all those was f, you can see if setting a ==f is a net gain by getting the score for that string. Or, in our abcd example ... ab abc abcd d is the biggest. so set a to d to eliminate 3? d-a is too big, not a valid change, look again. bc, bcd, set b to d to eliminate 2? difference is too big, skip and look again... etc. That is the beginnings of how I would try to do it... again, could be way off...
Here is what I would do. It may or may not be right...
- write a routine to get the score of the unchanged string.
- now, no matter what we do, we can't exceed or even equal the base cost of the unchanged string, so any change to the string has to actually reduce the cost below the original score. So, for changing abcd to zbcd is right out, as a to z costs a lot of points.
-to be cost effective, a change has to eliminate some of the i to j valid strings to reduce the Y count.
- so, you need an algorithm that can make a change that eliminates some of the Ys and costs less than the number of things it eliminates. To do that you need all the i to j substrings and a way to look at them to find a common letter that, if changed, invalidates them. That appears to be the first and last letter. so if you had 10 strings that started with the letter a and the ending letter max of all those was f, you can see if setting a ==f is a net gain by getting the score for that string. Or, in our abcd example ... ab abc abcd d is the biggest. so set a to d to eliminate 3? d-a is too big, not a valid change, look again. bc, bcd, set b to d to eliminate 2? difference is too big, skip and look again... etc. That is the beginnings of how I would try to do it... again, could be way off...
You have written the wrong code in the input method such as Subtask #1 (10 points): 1≤N≤50
Subtask #2 (20 points): 1≤N≤250
Subtask #3 (70 points): original constraints
Here you need to change like subtask#2(10):1<N<150
Subtask #3 (100 points): original constraints
Constraints
1≤T≤50
1≤N≤100^20
this is the right code for the right output
Example Input
3
abcd
dbca
dcba
Example Output
10
5
0
For more info visit:- http://www.traininginlucknow.in/best-c-language-training-in-Lucknow.html
Subtask #2 (20 points): 1≤N≤250
Subtask #3 (70 points): original constraints
Here you need to change like subtask#2(10):1<N<150
Subtask #3 (100 points): original constraints
Constraints
1≤T≤50
1≤N≤100^20
this is the right code for the right output
Example Input
3
abcd
dbca
dcba
Example Output
10
5
0
For more info visit:- http://www.traininginlucknow.in/best-c-language-training-in-Lucknow.html
Topic archived. No new replies allowed.