PROBLEM LINK:
Setter: Devarshi Khanna
Tester: Devarshi Khanna, Taranpreet Singh
Editorialist: Akash Bhalotia
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given an array A of size N, containing only 0’s and 1’s, find the minimum cost to flip elements such that the size of every ‘group’ is between x and y (both inclusive). The cost to flip the i^{th} element is B[i]. If no solution exists, print -1.
CONSTRAINTS:
- 1 \leq T \leq 70
- 1 \leq N \leq 1000
- 0 \leq B[i] \leq 1000
QUICK EXPLANATION:
Precompute prefix sums cost[i][k] = cost to make all elements from start to position i equal to bit k (0 \leq k \leq 1). Using Dynamic Programming, for all x \leq j \leq y compute DP[i][k] = min of all valid DP[i-j][k^1] + cost to make all elements from position (i-j+1) to i equal to bit k. If no solution exists for N, print -1, else print min(DP[N][0], DP[N][8]).
EXPLANATION:
- Let us use 1-based array indexing to understand this.
- We want to divide the array into disjoint groups of size j, x \leq j \leq y. If we can do this, a solution exists, otherwise we’ll be printing -1.
- If make all elements of the first group = 1, we’ll have to make all elements of the second group = 0 and keep alternating. Similarly, if instead, we make all elements of the first group = 0, we’ll have to make all elements of the second group = 1 and keep alternating. Assuming that a solution exists, we’ll have to print the minimum of these two, i.e, either making the first group = 1 and alternating, or making the first group = 0 and alternating.
- Since we are alternating, if we make a group = k, we would have definitely made the previous group = k xor 1. If the current group is of size j and its last element is at position i, then the previous group must have ended at position i-j.
- We’ll be using basic dynamic programming to solve this. Remember, that in DP, generally, first we simply solve the problem for a smaller instance of the problem. For example, if the array has N elements, say, we first solve the problem assuming that the array has only 1 element. Then, we extend this solution to solving the the problem for more elements. Once we have the solution for size i, we never compute it for i again. We simply store this result and use it when needed in future. This is what we’ll be doing here too.
- Let us consider a DP solution with two states: DP[i][k]. This means, if a solution exists for i, DP[i][k] is the minimum cost to give a solution where the last group ends at position i and is set to bit k, where k is 0 or 1. If this group is of size j, then the cost for the previous group must have been stored at DP[i-j][k^1]. Thus, formally:
Click to view
DP[i][k] = min(DP[i-j][k^1] + cost to make all elements from (i-j+1) to i equal to bit k).
- To compute the cost for range efficiently, we can precompute their prefix-sums. Now to use this in our problem:
Click to view
Cost for range of size j, ending at i, setting all elements to k: cost[i][k]-cost[i-j][k]
- Initially, we’ll set all DP[i][k] = -1, signifying that no solution exists for it. We’ll make DP[0][0] = DP[0]{[}10{]} = 0, signifying that a solution exists when the array has 0 elements. Then, if a solution exists which ends at position i and makes all elements = k, we’ll set DP[i][k] = min of all those solutions.
- If DP[N]{[}0{]} = -1 or DP[N]{[}11{]} = -1 , it means that we can’t divide the array into valid sized groups and so we print -1. Otherwise, a solution exists. This involves either setting the elements of the final group to 0 or setting them to 1. Thus, ans = min* (DP[N][0], DP[N]{[}12{]}) *.
COMPLEXITY:
Computing prefix sums takes O(N). DP involves nested loops of size N each. Thus:
- Time Complexity: O(N^2) per test case.
- Space Complexity: O(N) per test case.
AC SOLUTION:
PROBLEMS BASED ON DP:
Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions 
Thanks to @taran_1407 and @vijju123 for their constant guidance and support.