LSU - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef will meet N people, each of whom speaks one of five languages.
Chef can either learn a language for a cost of X and speak to everyone who speaks that language; or hire a translator for a single person.
Hiring a translator starts at a cost of 1, with an increase of 1 every time it’s done.

Find the minimum cost of talking to everyone.

EXPLANATION:

If Chef chooses to learn a language, he of course doesn’t need to hire a translator for anyone of that language at all.
If he doesn’t learn a language, he needs to hire a translator for everyone who speaks that language.

Our task is thus to decide which languages Chef will learn.

There are five languages, so Chef can learn anywhere between 0 and 5 languages.
Suppose he decides to learn k languages.
This has a fixed cost of k\cdot X, after which the translator must be used for everyone else.

To minimize the translator’s cost, we should minimize the number of people who need it.
So, it’s best to choose to learn the k most frequent languages, and use the translator for the rest.

Compute the cost of doing this for each k, and take the minimum of them all.
That is,

  • First, calculate the number of people who speak each language.
  • Iterate over k from 0 to 5.
    • With k fixed, the cost of learning languages is k\cdot X.
    • Then, the k languages with the maximum frequency will be learnt. That leaves 5-k languages which need the translator, compute the cost needed for that and add it to k\cdot X to obtain the overall cost.
  • The answer is the minimum of this across all k.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    s = input()
    
    freq = {}
    for c in s:
        if c not in freq: freq[c] = 0
        freq[c] += 1
    
    vals = sorted(freq.values())
    sz = len(vals)
    ans = 10**9
    for i in range(sz+1):
        req = sum(vals[:sz-i])
        ans = min(ans, i*x + req*(req+1)//2)
    print(ans)
1 Like
2

The code needs a small change in line 13.
change : for i in range(sz):
to : for i in range(sz+1):

2 Likes
3

actually, I used greedy method to solve this problem.
for languages with frequency from low to high, decide whether to learn or to buy. here is the code:

from collections import Counter


for _ in range(int(input())):

    n, c = list(map(int, input().split(" ")))
    s = input()
    cnt = Counter(s)
    kvs = sorted([[k, v] for k, v in cnt.items()], key=lambda x: x[-1])
    cur = 1
    ans = 0
    for k, v in kvs:
        cost1 = c
        cost2 = (2 * cur + v - 1) * v // 2
        if cost1 <= cost2:
            ans += cost1
            continue
        else:
            ans += cost2
            cur += v
            continue

    print(ans)
1 Like