Connection Status:
Competition Arena > IncrementAndDoubling

IncrementAndDoubling

SRM 596 · 2013-06-25 · by ir5

SRM 596 · 2013-06-25 · by ir5 · Dynamic Programming, Simple Math
Class Name: IncrementAndDoubling
Return Type: int
Method Name: getMin
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have an array with N elements. Initially, each element is 0. You can perform the following operations:

  • Increment operation: Choose one element of the array and increment the value by one.
  • Doubling operation: Double the value of each element.

You are given a int[] desiredArray containing N elements. Compute and return the smallest possible number of operations needed to change the array from all zeros to desiredArray.

Constraints

  • desiredArray will contain between 1 and 50 elements, inclusive.
  • Each element of desiredArray will be between 0 and 1,000, inclusive.
Examples
0)
{2, 1}
Returns: 3

One of the optimal solutions is to apply increment operations to element 0 twice and then to element 1 once. Total number of operations is 3.

1)
{16, 16, 16}
Returns: 7

The optimum solution looks as follows. First, apply an increment operation to each element. Then apply the doubling operation four times. Total number of operations is 3+4=7.

2)
{100}
Returns: 9
3)
{0, 0, 1, 0, 1}
Returns: 2

Some elements in desiredArray may be zeros.

4)
{123, 234, 345, 456, 567, 789}
Returns: 40

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

Coding Area

Language: C++17 · define a public class IncrementAndDoubling with a public method int getMin(vector<int> desiredArray) · 60 test cases · 2 s / 256 MB per case

Submitting as anonymous