Solve Two Array Optimization Problems

This online assessment included two coding problems.

Problem 1: Maximize protected city population You are given:

• an integer n
• an array population of length n, where population[i] is the population of city i + 1
• a binary string unit of length n, where unit[i] = '1' means city i + 1 initially has one security unit, and unit[i] = '0' means it does not

For each city i > 1 that initially has a security unit, you may either keep that unit in city i or move it left to city i - 1. Each unit can be moved at most once, and moving a unit removes it from its original city. A city is considered protected if it has at least one security unit after all moves. If multiple units end up in the same city, that city's population is still counted only once.

Return the maximum possible sum of populations of all protected cities.

Example:

• n = 5
• population = [10, 5, 8, 9, 6]
• unit = "01101"

One optimal strategy is to move the unit from city 2 to city 1, keep the unit at city 3, and move the unit from city 5 to city 4. The protected cities are 1, 3, and 4, so the answer is 10 + 8 + 9 = 27.

Problem 2: Minimize total cost to remove all ones You are given a binary array product of length n and an integer k, where product[i] = 1 represents variant B and product[i] = 0 represents variant A.

You must turn every 1 into 0 using a sequence of operations. In one operation:

1. Choose a subarray [l, r] of length exactly k.
2. Pay a cost equal to the sum of the current values in product[l..r].
3. Choose one index p in [l, r] such that product[p] = 1, and set product[p] = 0.

The array changes after each operation, so the cost of later operations depends on earlier choices. Find the minimum total cost required to convert all 1s to 0s. You may assume 1 <= k <= n.

Part 1: Maximize Protected City Population

You are given n cities numbered from 1 to n. City i has population population[i - 1]. You are also given a binary string unit of length n, where unit[i - 1] = '1' means city i initially has one security unit. For every city i > 1 that initially has a unit, you may either keep that unit in city i or move it exactly one city to the left, to city i - 1. Each unit can be moved at most once, and moving it removes it from its original city. After all choices are made, a city is protected if it has at least one unit. If multiple units end up in the same city, that city's population is counted only once. Return the maximum total population of all protected cities.

Constraints

• 0 <= n <= 200000
• len(population) = n
• len(unit) = n, and each character of unit is '0' or '1'
• 0 <= population[i] <= 10^9
• The answer fits in a 64-bit signed integer

Examples

Example 1

Input: (5, [10, 5, 8, 9, 6], '01101')
Output: 27

Explanation: Move the unit from city 2 to city 1, keep the unit at city 3, and move the unit from city 5 to city 4. Protected cities are 1, 3, and 4, for a total of 10 + 8 + 9 = 27.

Example 2

Input: (0, [], '')
Output: 0

Explanation: There are no cities, so the protected population is 0.

Hints

1. Process cities from left to right. Once you decide what happens to the unit at city i, the final status of city i - 1 is fixed.
2. A small DP state is enough: track whether the current city is already protected by decisions made so far.

Part 2: Minimize Total Cost to Remove All Ones

You are given a binary array product and an integer k. In one operation, you must choose a subarray of length exactly k, pay a cost equal to the current sum of values inside that subarray, then choose one index in that subarray that currently contains 1 and change it to 0. The array changes after every operation, so future costs also change. Return the minimum total cost needed to turn every 1 into 0. This version of the problem guarantees that the number of 1s is small enough for an exact state-compression solution.

Constraints

• 1 <= len(product) <= 50
• 1 <= k <= len(product)
• product[i] is either 0 or 1
• The number of 1s in product is at most 15

Examples

Example 1

Input: ([1, 0, 1, 1], 3)
Output: 4

Explanation: Remove the 1 at index 2 first with cost 2, then the remaining two 1s can each be removed with cost 1.

Example 2

Input: ([1], 1)
Output: 1

Explanation: The only valid subarray is the whole array, whose sum is 1.

Hints

1. Only the positions that currently contain 1 matter. Compress those positions and represent a state by a bitmask of remaining ones.
2. For a fixed state and a fixed 1, its immediate removal cost is the minimum number of remaining 1s among all length-k windows that contain it.