Hi,Codeforces! I need your help!
There is a kind of integer sequence of length (n+k). (k<=n)
Constraints follow:
For every element in sequence, its value is either -1 or a positive integer.
The number of -1's occurrences is n and the number of positive integers's occurrences is k.
The sum of all positive integers equals n.
Any prefix sum of the sequence is non-negative.
Now you must calculate the number of different sequences satisfying the constraints above.
Is there a general formula for this answer? Most thanks.
Auto comment: topic has been updated by wtw (previous revision, new revision, compare).
Here is problem link.
I think they are two different problems although they are both about bracket. Please read my constraints carefully.
nice try
In the problem, n and k's upper bound is 300 and time limit is 1 second for per test case.
We can easily come up with a dp solution,in which, let f[i][j][p] denotes number of the sequences of length i and they has j positive integers and their sum is p.
And, we can get O(n^5) solution.
But, it's too slow. So I look for a fast solution such as a formula for this answer or a O(n^3) solution.