PrimePruning

SRM 769 · 2019-10-17 · by misof

SRM 769 · 2019-10-17 · by misof · Brute Force, Greedy, Simple Math, Simple Search, Iteration

Show categories

Class Name: PrimePruning

Return Type: String

Method Name: maximize

Arg Types: (int, int)

Problem Statement

An integer is a prime number if it has exactly two positive integer divisors. The first few prime numbers are P[0]=2, P[1]=3, P[2]=5, and so on.

Let alphabet[x] denote the x-th (0-based index) lowercase letter of the English alphabet. For example, alphabet[0]='a' and alphabet[24]='y'.

You are given the ints N and E. Generate an N-character string by concatenating alphabet[P[i] mod 26] for i=0..N-1. Then, produce the lexicographically largest possible string by erasing exactly E of those characters. Return that string.

Constraints

N will be between 1 and 10^9, inclusive.
E will be between max(0,N-1000) and N-1, inclusive.

Examples

10
0
Returns: "cdfhlnrtxd"

We generate a 10-character string using the first 10 primes, and then we don't erase anything.

30
5
Returns: "nrtxdflprvbhjptvbfltxzdfj"

When erasing 5 characters out of the first 30, the optimal solution happens to be erasing the first five.

30
15
Returns: "xvjptvbfltxzdfj"

When erasing 15 characters out of the first 30, the optimal strategy is no longer the same as above.

50
47
Returns: "zzv"

1
0
Returns: "c"

Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PrimePruning with a public method string maximize(int N, int E) · 123 test cases · 2 s / 256 MB per case