PAUWS - Pair and unpair weightest string
Once I went market to buy a teddy. The shopkeeper offered a puzzle and said he'll give me whatever i wish at a huge discount if i give him the working piece of code for following problem. You will be given a string S of length N, containing either 'A' or 'B'. Make all the possible lists from the given list, with the given operation that you are allowed to change one symbol into another. Then assign maximum weight to each of the string and get the string with maximum weight and return the weight.
You have only following two ways to assign weight to symbol:
- Pair a S[i] symbol with adjacent one (S[i] or S[i-1]). Each symbol can only be paired with exactly one symbol. Weight of a pair is 4. Pair will be either 'AB' or 'BA'.
- Keep a S[i] Symbol independent. Weight of unpaired symbol is 1.
- Each symbol is either involved in exactly one either pair or unpaired status.
- For each string, keep in mind the number of symbols (K) with index i, 1 <= i <= N, which are changed from original symbol S[i].
- For each of the possible lists, Add all the weight assigned as a pair and unpair, then subtract K from it. assign this final value as string weight. Add each paired weight once exactly.
The task is to maximize the weight of the string. Suppose S="ABB", possible transforms can be {"ABB", "ABA", "AAB", "AAA", "BBB", "BBA", "BAB", "BAA"} with respective weight {5, 4, 4, 1, 2, 3, 3, 2}. Maximum weight is found 5 in string 1.
Constraints
1 <= N <= 10^5, 1 <= T <= 500.
Input
First line contains t, number of testcases. For each testcase, first line contains N, length of the string. Second line contains string itself.
Output
For each testcase, output the maximum weight of a string that can be obtained.
Example
Input: 5 3 ABB 7 ABBBAAA 8 BAAAAAAA 12 AAAAAAAAAAAA 11 ABABBBABABA Output: 5 12 13 18 21
hide comments
neekon:
2023-08-31 22:13:10
@author would you like to have a look at my submission id:31776292, please, and tell me whats wrong with my algorithm
|
|
mohit:
2016-01-24 14:58:54
Easy question, ACC in one go :)
|
|
mr_lazy:
2015-08-26 16:08:49
AC in one Go! :D 0.28ms |
|
Akhilesh Anandh:
2014-08-14 22:20:49
Time limit too strict.. had to use faster IO methods to get accepted. |
|
P_Quantum:
2014-08-14 22:20:49
Nice DP ..!! |
|
anurag garg:
2014-08-14 22:20:49
@author can you have a look at my submission id:11468949 and tell me whats wrong with my algorithm
|
Added by: | Rishav Goyal |
Date: | 2014-04-09 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own |