Costly Summit
Source: codechef
Difficulty: 1425

Costly Summit
Chef is going to meet$N$people. Each person speaks one of the five languages:$A$,$B$,$C$,$D$, or$E$. Chef does not know any language at the start. To communicate, he has two options:
Chef can learn a language for a fixed cost$C$. Once he learns a language, he can talk with everyone who speaks that language.
Chef can hire a translator to help him. The cost of hiring a translator goes up each time he uses one, no matter which language it is. For example, his first use costs$1$unit, his second use costs$2$units, his third use costs$3$units, and so on. So if he has already used a translator three times, the next time will cost him$4$units.
You are given a string$S$of length$N$where$S_i$represents the language spoken by the$i_{th}$person. Your task is to find the minimum total cost for Chef to talk with all$N$people.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains two space-separated integers$N$and$C$— the number of people and the cost to learn any language, respectively.
The second line contains a string$S$of length$N$where each character is one of$A$,$B$,$C$,$D$, or$E$.$S_i$is the language spoken by the$i_{th}$person.
Output Format
For each test case, output on a new line the minimum total cost for Chef to talk with all$N$people.
Constraints$1 \leq T \leq 10^5$$1 \leq N,C \leq 10$The sum of$N$over all test cases won't exceed$2\cdot10^5$.
Sample 1:
Explanation:
Test Case 1:
Chef needs to meet$3$people who all speak language$A$, and he can either learn language$A$for$10$units or use a translator for each conversation with incremental costs of$1$,$2$, and$3$units respectively. Using translators, the total cost adds up to$6$, which is lower than the fixed cost of$10$, so the minimum cost is$6$.
Test Case 2:$3$people speaking$A$,$B$, and$C$and a learning cost of$2$, if Chef uses translators for all three, the cost would be$1 + 2 + 3 = 6$. However, if he learns one language (say$A$) for$2$units and then uses translators for the remaining two people (costing$1$and$2$units), the total comes to$2 + 3 = 5$, which is optimal. It can be proven that the above strategy results in the minimum possible cost.
Test Case 3:$2$people speaking$A$and$B$with a learning cost of$3$. Using translators for both results in a cost of$1 + 2 = 3$, which is as good as any mixed strategy (for instance, learning one language and translating for the other would exceed$3$), so the minimum cost is$3$.
Test Case 4:
Chef meets$5$people speaking$D$,$C$,$B$,$A$, and$E$with a learning cost of$4$. If he relies solely on translators, the total cost would be$1 + 2 + 3 + 4 + 5 = 15$. Alternatively, if he learns one language (for example,$A$) for$4$units and translates for the other four people with costs of$1$,$2$,$3$, and$4$, the total cost is$4 + 10 = 14$. It can be proven that the above strategy results in the minimum possible cost.

Sample Input:
4
3 10
AAA
3 2
ABC
2 3
AB
5 4
DCBAE

Sample Output:
6
5
3
14

C++ solution:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl '\n'
#define forn(i, n) for(int i = 0; i < n; i++)
//vector<vector<int>> a(n, vector<int>(n));
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T; cin>>T;
    while(T--){
        int n, c; cin>>n>>c;
        string s; cin>>s;
        vector<int> freq(5, 0);
        forn(i, n) freq[s[i] - 'A']++;
        sort(freq.begin(), freq.end());

        ll cost = 0;
        int x = 0, y = 0;
        for(int i = 0; i < 5; i++){
            y += freq[i];
            int sum = (y*(y+1)) / 2;
            
            if(sum - x <= c) cost += (sum - x);
            else{
                cost += c;
            }
            x = sum;
        }
        cout<<cost<<endl;
    }
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    scanner.Scan()
    t, _ := strconv.Atoi(scanner.Text())
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    for i := 0; i < t; i++ {
        scanner.Scan()
        n, _ := strconv.Atoi(scanner.Text())
        scanner.Scan()
        c, _ := strconv.Atoi(scanner.Text())
        scanner.Scan()
        s := scanner.Text()
        freq := make([]int, 5)
        for j := 0; j < len(s); j++ {
            freq[s[j]-'A']++
        }
        best := int(1e18)
        for mask := 0; mask < (1 << 5); mask++ {
            learnedCount := 0
            numLanguages := 0
            for j := 0; j < 5; j++ {
                if mask&(1<<j) != 0 {
                    learnedCount += freq[j]
                    numLanguages++
                }
            }
            translatorCalls := n - learnedCount
            translatorCost := translatorCalls * (translatorCalls + 1) / 2
            costTotal := numLanguages*c + translatorCost
            if costTotal < best {
                best = costTotal
            }
        }
        fmt.Fprintln(writer, best)
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String[] parts = br.readLine().split(" ");
            int n = Integer.parseInt(parts[0]);
            int c = Integer.parseInt(parts[1]);
            String s = br.readLine();

            sb.append(minCostToTalk(n, c, s)).append("\n");
        }

        System.out.print(sb.toString());
    }

    public static int minCostToTalk(int n, int c, String s) {
        int[] freq = new int[5]; // A to E
        for (char ch : s.toCharArray()) {
            freq[ch - 'A']++;
        }

        int minCost = Integer.MAX_VALUE;

        // Try all subsets of languages (2^5 = 32)
        for (int mask = 0; mask < 32; mask++) {
            int covered = 0;
            int learnedCount = 0;

            for (int i = 0; i < 5; i++) {
                if ((mask & (1 << i)) != 0) {
                    covered += freq[i];
                    learnedCount++;
                }
            }

            int translators = n - covered;
            int translatorCost = translators * (translators + 1) / 2;
            int learnCost = learnedCount * c;
            int totalCost = translatorCost + learnCost;

            minCost = Math.min(minCost, totalCost);
        }

        return minCost;
        

    }
}

JavaScript solution:
// your code goes here
function solve() {
    const input = require('fs').readFileSync(0, 'utf-8').trim().split(/\s+/);
    
    if (!input.length) return;

    let index = 0;
    const t = parseInt(input[index++]);
    const results = [];

    const langIndex = { 'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4 };

    for (let i = 0; i < t; i++) {
        const n = parseInt(input[index++]);
        const costLearning = parseInt(input[index++]);
        const s = input[index++];

        // Count occurrences of each language
        const counts = Array(5).fill(0);
        for (const ch of s) {
            counts[langIndex[ch]]++;
        }

        const totalPersons = counts.reduce((a, b) => a + b, 0);
        let bestCost = Infinity;

        // Sort by frequency
        const langFreq = counts.sort((a, b) => b - a);

        let learnedPersons = 0;
        for (let learnedLanguages = 0; learnedLanguages <= 5; learnedLanguages++) {
            const translatorsNeeded = totalPersons - learnedPersons;
            const translatorCost = (translatorsNeeded * (translatorsNeeded + 1)) / 2;
            const totalCost = learnedLanguages * costLearning + translatorCost;
            bestCost = Math.min(bestCost, totalCost);

            if (learnedLanguages < 5) {
                learnedPersons += langFreq[learnedLanguages];
            }
        }

        results.push(bestCost);
    }

    console.log(results.join("\n"));
}

solve();

Python solution:
# cook your dish here
def min_cost(T, test_cases):
    results = []
    for case in test_cases:
        N, C, S = case
        # Count the frequency of each language
        freq = {}
        for lang in S:
            if lang in freq:
                freq[lang] += 1
            else:
                freq[lang] = 1
        
        # Calculate the cost if we learn some languages and use translators for the rest
        min_total_cost = float('inf')
        # We can choose to learn 0 to 5 languages
        for k in range(0, 6):
            # If we learn k languages, we need to choose the k most frequent languages
            # to minimize the cost
            if k > len(freq):
                continue
            # Sort languages by frequency in descending order
            sorted_langs = sorted(freq.keys(), key=lambda x: freq[x], reverse=True)
            # Choose the top k languages to learn
            learned_langs = sorted_langs[:k]
            # Calculate the cost
            total_cost = k * C
            # For the remaining people, we use translators
            # The number of translators needed is the number of people not speaking the learned languages
            translator_count = 0
            for lang in freq:
                if lang not in learned_langs:
                    translator_count += freq[lang]
            # Calculate the cost of translators
            translator_cost = (translator_count * (translator_count + 1)) // 2
            total_cost += translator_cost
            # Update the minimum cost
            if total_cost < min_total_cost:
                min_total_cost = total_cost
        results.append(min_total_cost)
    return results

# Read input
import sys
input = sys.stdin.read
data = input().split()
idx = 0
T = int(data[idx])
idx += 1
test_cases = []
for _ in range(T):
    N = int(data[idx])
    C = int(data[idx+1])
    idx += 2
    S = data[idx]
    idx += 1
    test_cases.append((N, C, S))

# Compute results
results = min_cost(T, test_cases)

# Output results
for res in results:
    print(res)

Ruby solution:
def main
  input = ARGF.read.split("\n")
  test_cases = input.shift.to_i
  
  test_cases.times do
    n, c = input.shift.split.map(&:to_i)
    s = input.shift.chomp
    
    # Calculate cost if using only translators
    translator_cost = (1..n).sum
    
    # Count language frequencies
    freq = Hash.new(0)
    s.each_char { |lang| freq[lang] += 1 }
    
    # Sort frequencies in descending order
    sorted_freq = freq.values.sort.reverse
    
    min_cost = translator_cost
    learned_languages = 0
    remaining_people = n
    
    sorted_freq.each do |count|
      remaining_people -= count
      learned_languages += 1
      
      current_cost = (learned_languages * c) + (1..remaining_people).sum
      
      if current_cost < min_cost
        min_cost = current_cost
      else
        # No further improvement possible
        break
      end
    end
    
    puts min_cost
  end
end

main