In this post, we are going to solve Decrypt DSA Problem from Oracle, Online Assessments conducted on 13th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.
Decrypt DSA Problem Statement
Alice has an integer array
of size
. Alice has saved these integers in her computer but due to a virus attack some of the digits of her integers changed to some character of uppercase English alphabets from ‘A’ to ‘J’, but it is known that a unique digit is changed with a unique character.
For example, Let us suppose an integer was “1221321” and due to the virus,it is changed to “B2AB3A1”, i.e., some of “1” is changed to the character ‘B’ and some of ‘2’ is changed to the character ‘A’. But it is not possible that this integer is changed to “BB21321” or “B22A321” because In “BB21321” two different digits are changed to a single character ‘B’ and in “B22A321” two same digits ‘1’ is changed to two different characters.
You have been given array
after the virus attack, Alice asked you to decode integers in this array in such a way that after decoding, the summation of all integers of the array is minimum possible.
Note: You have to decode the integers in such a way that no integer contain leading zeroes like 001, 0123, 0 etc.
The first line of input contains an integer
— the number of testcases.The description of
testcases follows.
The first line of each testcase contains an integer
— the size of array
.
The second line of each testcase contains
space separated alpha-numeric strings denoting the elements of array
. There will be atmost 10 characters in every element of array
.
It is guaranteed that sum of
over all testcases does not exceed
.
For each testcase, print a single integer — the maximum possible sum of elements of array
.
321 134 1426
In sample test case 1, one of the optimal ways is to assign ‘A’ = 1 and ‘B’ = 0, then array
will be
and hence sum =
In sample test case 2, one of the optimal ways is to assign ‘A’ = 0, ‘B’ = 1 and ‘C’ = 2, then array
will be
and hence sum =
In sample test case 3, one of the optimal ways is to assign ‘A’ = 1, ‘B’ = 2 and ‘D’ = 0, then array
will be
and hence sum =
Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, long long int> p1, pair<int, long long int> p2){
return p1.second > p2.second;
}
int main() {
int t;
cin>>t;
while(t){
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;i++){
string str;
cin>>str;
v.push_back(str);
}
vector<pair<int, long long int>> charCnt(10, {10, 0});
for(auto str: v){
int l = str.size();
for(int i=0;i<l;i++){
int ind = str[i]-'A';
if(ind>=0 && ind<10){
int minInd = charCnt[ind].first;
long long val = charCnt[ind].second;
minInd = min(minInd, i);
val += pow(10, l-1-i);
charCnt[ind].first = minInd;
charCnt[ind].second = val;
}
}
}
vector<int> charCode(10, -1);
int code = -1;
long long maxCnt = -1;
for(int i=0;i<10;i++){
if(charCnt[i].first != 0){
if(charCnt[i].second > maxCnt){
maxCnt = charCnt[i].second;
code = i;
}
}
}
charCode[code] = 0;
for(code=1;code<10;code++){
int c = -1;
maxCnt = -1;
for(int i=0;i<10;i++){
if(charCode[i] == -1){
if(charCnt[i].second > maxCnt){
maxCnt = charCnt[i].second;
c = i;
}
}
}
charCode[c] = code;
}
// for(int i=0;i<10;i++){
// cout<<charCode[i]<<endl;
// }
long long ans = 0;
for(auto str: v){
int l = str.size();
long long num = 0;
for(int i=0;i<l;i++){
int ind = str[i]-'A';
if(ind>=0 && ind<10){
num = num*10 + charCode[ind];
}
else{
num = num*10 + str[i]-'0';
}
}
ans += num;
}
cout<<ans<<endl;
t--;
}
return 0;
}