hubert322's blog

Changing it into a DP approach.
By hubert322, history, 9 years ago, In English

This is the question I'm dealing with: http://codeforces.me/problemset/problem/327/A

I'm trying to practice dynamic programming, and this is the code that I have came up.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 100;

int a [maxN + 5], dp [maxN + 5];

int main ()
{
	int n;
	
	scanf ("%d", &n);
	
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf ("%d", &a [i]);
		if (a [i] == 1)
			ans++; // get how many 1s are in the numbers
	}
	
	for (int i = 0; i < n; i++)
	{
		dp [i] = 0; // set to 0 since we're getting max
		for (int j = i; j < n; j++)
		{
			int count = 0;
			for (int k = i; k <= j; k++)
			{
				if (a [k] == 1)
					count -= a [k];
				else
					count += 1;
			} // basically, if we have more zero than ones, we would choose it.
			dp [i] = max (count, dp [i]);
		}
		if (i > 0)
			dp [i] = max (dp [i], dp [i - 1]);
	}
	if (ans == n)
		ans--;
	printf ("%d\n", ans + dp [n - 1]);
	
	return 0;
}

Though it got accepted, I feel like this isn't the efficient way? So, what is the correct way of doing such dp problem?

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your approach seems fine except that a lot a lot of waste iterations are being carried out here...The third loop that uses 'k' isin't required I guess...just use a prefix sum array...A prefix sum array is many a times used to solve dynamic programming questions... My code Here...

-If u'd like to know more about using arrays for solving DP questions , my favourite question is: DZY loves sequences..

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your usage of prefix sum for this problem?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      consider the range i...j .the sum of this range is the number of 1's in this range...so the number of 0's in this range =(size of range-sum of range)....number of 1's outside this range =(total_sum-sum of this range.). So max=Math.max(max,number of 1's outside this range+number of zeros that can be flipped in this range).

      → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

for reference since this is a DP exercise, you can also formulate this problem in another way, while achieving the same time complexity (n^2).

focus on a segment of your array defined by indices i...j, and define dp[i][j] to store the optimal solution for that segment (this solution basically refers to the maximum number of 1s that can be achieved when you apply exactly one move in the segment).

How can you find the optimal solution for i....j if you know the optimal solutions for all the small sub problems?

Try all possibilities.

Case 1: Flip everything from i to j. So dp[i][j] = sum of all 1s achieved from i to j. Use the prefix sum approach to find each sum in constant time. Otherwise if you do it like in your code the time complexity will be n^3.

Case 2: Do not flip i, so dp[i][j] = data[i] + dp[i+1][j]

Case 3: Do not flip j, so dp[i][j] = data[j] + dp[i][j-1]

Case 4: Do not flip j AND do not flip i, so dp[i][j] = data[i] + data[j] + dp[i+1][j-1]

The final answer will be stored in dp[0][n-1].

With some care about the corner cases you can achieve a correct implementation.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is there another way that you can think of that can achieve a fewer complexity?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      Yes. In fact as also explained in the tutorial you can do it in O(n) time while only using O(n) space. The tutorial refers to a reduction to another problem which they call "maximum subsequence", however that is not very correct and I will elaborate more here.

      Focus on your input, let's say you store it in an array called A. This array will initially consist of zeros and ones.

      Now focus on a move. Let us try to understand what a move really does. A move is executed on a segment (or subarray) of A defined by some left index i and some right index j. When you apply a move on this segment all its elements are flipped. We want to find that segment, or subarray, defined by i,j such that if a move is applied, then the total number of ones in A is maximized.

      Having understood exactly what this problem is asking us to do, we can now change the formulation a little bit. When we make a move and change some 0 to 1, we get a gain of 1. A gain basically refers to the fact that you just managed to create a 1, and 1s are good since the more you have, the better the score of the corresponding move. If we change some 1 to 0, we get a gain of -1 respectively. Now let G be some array for which initially we have G[i] = 1 if A[i] = 0 and G[i] = -1 if A[i] = 1.

      Suppose that you can somehow find the subarray of G that achieves the maximum overall gain x. And let y be the number of 1s that you originally have in A. The optimal score will then be equal to x + y.

      To find that subarray of G you can apply Kadane's algorithm that finds the subarray with the maximum sum (in our case overall gain) and runs in O(n) time while only using O(n) space. The general idea is to define two variables, maxendinghere and maxsofar. The first variable is updated incrementally and for some position i in your input array (G in this case) it says what is the maximum sum of a subarray ending in position i. And the second variable is used to remember the maximum value of maxendinghere during the course of the algorithm. You can find more on the wikipedia page.

      And a correct solution here.

      → Reply