ayush29azad's blog

By ayush29azad, history, 5 weeks ago, In English

How to solve this problem using Dp ??? I read the editorial and found that it has been solved using combinatorics but I saw others have solved it using Dp approach.

Problem Link -https://codeforces.com/contest/1288/problem/C

Please Help !!!! Thanks in advance

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

At first,we reverse array B and make array B is non-descending.It is easy to find that if array A and array B combine to form array C, array C is non-descending.Therefore, the answer is equal to the number of non-decending array C whose element is an integer between 1 to n.(The length of array C is 2*n).We assume dp[i][j] means the number of array C whose length is i and maximum value is j.So the answer of this problem is dp[2*m+1][n].The dp function is:

dp[i][j]=dp[i-1][1]+dp[i-1][2]+...+dp[i-1][j] So the complexity is O(n*n*m).Since the constraint is too weak.This method is correct.But if the constraint is stronger,you should used some data structure to reduce the time of dp function.

It is my code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=1e9+7;
int dp[22][1002];
signed main()
{
	int h;
	int t,n, m,a,b,c;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		dp[1][i] = 1;
	for (int i = 2; i <= 2*m+1; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= j; k++)
			{
				dp[i][j] += dp[i - 1][k];
			}
			dp[i][j] %= mod;
		}
	}
	cout << dp[2 * m + 1][n] << '\n';
	return 0;
}
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much !!!! Also One doubt that why the final answer will dp[2*m+1][n] , it should be dp[2*m][n] as the final length of the array will be 2*m ???

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because dp[i][j] means the number of array C whose length is i and maximum value is j,final answer = dp[2*m][1]+ dp[2*m][2]+...+dp[2*m][n],which is equal to dp[2*m+1][n].

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

use dp or combinatorics

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You may take a look at this solution

Code