Question link
My sol.
Getting Wrong Answer.
Can anyone share his approach to this?
I did not realize no one provided any easily searchable solution to this problem over discuss, so I will take liberty to give the outline.
-
The first subtask is clear - you can try all the 26^N strings and check which one satisfies the criterias
-
The second subtask gives first non-significant hint to solve the problem. It says that input is always the largest string for that particular hash value. Say my hash value is 27 for length 2, then the string will be ``zc" (25+2). If my hash value is 105 for length 5, string is zzzzf . The lexicographically smallest string can be easily found by reversing the input string.
-
To solve this problem, first start with base cases. For N=1, or S being only ``aaaaaa" or ``zzzzzz" the answer is -1 because only 1 string exists with that hash value for these cases. So no alternate string P (don’t forget, even for -1 cases you are to print hash value AND -1).
-
For all other cases answer exists.
-
Start by having a string ``aaaaaaa....a" upto length N. Say its hash is H_k. Say our input string is S and its hash is H_S. We need to have (H_S - H_k) value more in our ``aaa..aaaa" string’s hash.
-
Since we want lexicographically smallest, we start at the end and greedily convert the a's to z's as long as we can.
-
If one of the a's cannot be converted to 'z' , we know that (H_S - H_k < 25). Simply change that character to the required character to get H_k = H_S and we are done.
4 Likes
I didn’t even knew that we should print the sum even in case of “-1” . It costed me 7WA’s . Anyways ,nice problem 
@darshpreet You can check my code if you want
#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define vector vector<int>
#define vectorp vector<pair<int,int>>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
int t;
cin >> t;
map<char,int>mp,mp1;
for(int i = 0 ; i < 26 ; i++ ){
mp['a'+i] = i;
}
for(int i = 0 ; i < 26 ; i++ ){
mp[i] = 'a'+i;
}
while(t--)
{
string s;
cin >> s;
int sum = 0;
int n = s.size();
for(int i = 0 ; i < n ; i++ ){
sum+=mp[s[i]];
}
if(sum==(25*n)|| sum==0 || n==1){
cout<<sum<<' '<<"-1"<<'\n';
}
else if(sum<=25)
{
string res(n,'a');
res[n-1]=mp[sum];
if(res==s){
res[n-1]=mp[sum-1];
res[n-2]+=1;
}
cout<<sum<<' '<<res<<'\n';
}
else{
string res(n,'a');
int total = 0;
int pos = -1;
for(int i = n-1 ; i>=0 ; i--){
if((total+25)<=sum){
res[i]='z';
total+=25;
}
else{
pos = i;
break;
}
}
int diff = sum-total;
res[pos]='a'+diff;
if(res==s){
for(int i = 0 ; i<n ; i++){
if(res[i]=='z'){
res[i]='y';
res[i-1]+=1;
break;
}
}
}
cout<<sum<<' '<<res<<'\n';
}
}
}
1 Like
I doubt that this approach is gonna work. Lets take the example of the sample case itself where the given string is “yzz”.
Using your approach we will get the answer as “yzz” which is wrong as the output string cannot be same as the input string.
Please correct me if I am wrong.
It works for all cases where answer exists. I think I need to reword the answer to make it more explicit.
Actually, your case is wrong. The answer is-
74 zyz
The question asks for lexicographically smallest string, which is not equal to P and has same hash - not the overall lexicographically smallest string.
1 Like