wtw's blog

A Combinatorics Problem
By wtw, history, 8 years ago, In English

Hi,Codeforces! I need your help!

There is a kind of integer sequence of length (n+k). (k<=n)

Constraints follow:

  1. For every element in sequence, its value is either -1 or a positive integer.

  2. The number of -1's occurrences is n and the number of positive integers's occurrences is k.

  3. The sum of all positive integers equals n.

  4. 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.

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wtw (previous revision, new revision, compare).

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

Here is problem link.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think they are two different problems although they are both about bracket. Please read my constraints carefully.

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

nice try

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

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.

→ Reply