Connection Status:
Competition Arena > SafeRemoval

SafeRemoval

SRM 553 · 2012-06-05 · by vexorian

SRM 553 · 2012-06-05 · by vexorian · Dynamic Programming
Class Name: SafeRemoval
Return Type: int
Method Name: removeThem
Arg Types: (vector<int>, int)
Problem Statement

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.

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
0)
{1, 4, 1, 4, 2, 3, 2, 3, 2}
5
Returns: 14

Makes greedy fail.

1)
{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.

2)
{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.

3)
{1,6,1,10,1,2,7,11}
6
Returns: 21
4)
{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.

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

Coding Area

Language: C++17 · define a public class SafeRemoval with a public method int removeThem(vector<int> seq, int k) · 164 test cases · 2 s / 256 MB per case

Submitting as anonymous