PrimePruning | Topcoder Archive

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.

Definition

Class:: PrimePruning
Method:: maximize
Parameters:: int, int
Returns:: String
Method signature:: String maximize(int N, int E)
(be sure your method is public)

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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.