SafeRemoval | Topcoder Archive

Problem Statement

Did you know that platypuses can be very superstitious? A certain platypus was on a mission to remove exactly k numbers from a sequence in such a way that the sum of the remaining numbers is as large as possible. This task would have been very simple, were it not the case that our platypus wants to avoid some unlucky situations.

More precisely, our platypus thinks that the number 4 is unlucky, and so are all its multiples. Fortunately, the sum of the original sequence of numbers is not a multiple of 4. The platypus wants to keep it that way. It will only consider removing a number from the sequence if after the removal the sum of the remaining elements is not a multiple of 4. We will call such a removal safe.

You are given int[] seq and int k. If it is possible to perform exactly k safe removals (one element at a time), return the maximum possible sum of the elements remaining after the k removals. In case it is not possible to perform k safe removals, return -1.

Definition

Class:: SafeRemoval
Method:: removeThem
Parameters:: int[], int
Returns:: int
Method signature:: int removeThem(int[] seq, int k)
(be sure your method is public)

Constraints

seq will contain between 2 and 50 elements, inclusive.
Each element of seq will be between 1 and 1000, inclusive.
k will be at least 1.
k will be less than the number of elements in seq.
The sum of all elements of seq will not be a multiple of 4.

Examples

```
{3, 8, 4}
```
```
1
```
```
Returns: 11
```
The best move for the platypus is to remove 4. The platypus cannot remove 3, because the remaining elements would add up to 4+8 = 12, a multiple of 4. Removing 8 is safe, but the total sum of the remaining elements, 3+4=7 is smaller than 11.
```
{1,1,1,1,1,1}
```
```
3
```
```
Returns: -1
```
The initial sum is 6. After removing any of the elements, the sum becomes 5. At that point it becomes impossible to remove any of the remaining elements without making the sum a multiple of 4.
```
{1,6,1,10,1,2,7,11}
```
```
6
```
```
Returns: 21
```
```
{1,1,1,1,1,1,1,1,7}
```
```
3
```
```
Returns: 6
```
One of the three removed elements has to be the 7. The platypus has to remove the elements either in the order 1,7,1, or in the order 1,1,7.

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.