REC19B - Editorial

editorial
,
1

Problem: Vipers Experiment
Author: Abhinav
Tester: Onkar

DIFFICULTY:

EASY

QUICK EXPLANATION:

By following a greedy strategy, letters with higher contribution are replaced with greater digits.

EXPLANATION:

First, for each letter, we will find its contribution in the final sum (maximum damage). Decimal values of a letter are summed to obtain its contribution. For example, suppose the strings are - “abc”, “cb”, “c”. Contribution of ‘c’ in these strings are 1, 10 and 1 respectively. Hence, total contribution of ‘c’ is 1+10+1 = 12. Similarly, contribution of ‘b’ is 10+1 = 11, and that of ‘a’ is 100.

Letters are replaced with digits (0 - 5), such that the letter with higher contribution is replaced with the greater number. In the above example, ‘a’ is replaced with 5, ‘c’ with 4 and ‘b’ with 3.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main()
{
    ll n;
    cin >> n;
    ll weight[6] = { 0 };	// stores the contribution of each letter

    for (ll i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        ll temp = 1;
        for (ll i = s.length() - 1; i >= 0; i--)
        {
            weight[s[i] - 'a'] += temp;
            temp = temp * 10;
        }
    }

    sort(weight, weight + 6);

    ll maxDamage = 0;
    for (ll i = 0; i < 6; i++)
    {
        maxDamage += i *weight[i];
    }

    cout << maxDamage;
    return 0;
}
Tester's Solution 
#include <bits/stdc++.h>
using namespace std;
#define sub             freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);
#define helpUs          template<typename T = ll , typename U = ll>
#define helpMe          template<typename T = ll>
#define pb              push_back
#define ll long long
#define all(x) x.begin(),x.end()
#define ss second
#define ff first
#define endl "\n"
#define int ll
helpUs class comp{public:bool operator()(T a, U b){
    return a>b;

}};

helpUs istream& operator>>(istream& aa, pair<T,U> &p){aa>>p.ff>>p.ss;return aa;}
helpMe ostream& operator<<(ostream& ja, vector<T> &v){for(auto it:v)ja<<it<<" ";return ja;}
helpMe istream& operator>>(istream& aa, vector<T> &v){for(auto &it:v)cin>>it;return aa;}
helpUs ostream& operator<<(ostream& ja, pair<T,U> &p){ja<<p.ff<<" "<<p.ss;return ja;}

ll n, k, tt = 1;
void solve()
{
    cin >> n;
    assert(n > 0 && n <= 1000);
    vector<string> ar(n);
    cin >> ar;

    ll sum = 0;
    map<char, int> sumPerChar;
    for (string num: ar)
    {
        ll l = num.size();
        reverse(all(num));
        assert(l > 0 && l <= 7);
        int sum = 1;
        for (int i = 0; i < l; i++)
        {
            sumPerChar[num[i]] += sum;
            sum *= 10;
        }
    }

    vector<int> v;
    for (auto it: sumPerChar)
    {
        v.push_back(it.ss);
    }

    sort(all(v), comp < > ());

    int digit = 5;
    for (auto it: v)
    {
        sum += (digit *it);
        digit--;
    }

    cout << sum << endl;

}

signed main()
{
    ll t = 1;#
    ifndef ONLINE_JUDGE
    sub;#
    endif
   	// clock_t clk = clock();
   	// pre();

    while (t--)
        solve();
   	// ttime;
    return 0;
}
1 Like