inazuma_11's blog

Problem in dp with combinatorics ???
By inazuma_11, history, 5 years ago, In English

1288C - Two Arrays Hi , Can someone help me with the above problem ... It seems tutorial is not available for this problem . Thanks in advance . Also I often get stuck at problems of combinatorics involving dynamic programming . Can someone tell me what should i refer to learn to solve these type of problems .

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

Comments Comments (10)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

You already answered your own question:

I often get stuck at problems of combinatorics involving dynamic programming

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Please try not to comment at all on codeforces as it will save your time as well as ours as we wouldn't have to read your comments which are not helpful more often than not. Thanks.

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

      Thanks for letting me know about the stubborness of you div 2 green/gray/cyans. Suggestion accepted. I shall not help you green/gray/cyan coders from now on.

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

        I don't get how rating factors into this.

        You offered nothing of substance in your comment, so why post it?

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

        I never asked for your help, so please shut up.

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

Actually, I guess they forgot to link the announcement and editorial to the contest, but the editorial exists.

Also, you can look at my comment in the editorial for further help towards the problem.

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

I had done the same thing using DP. You can see my solution if you are not finding combinatorics approach mentioned in the editorial intuitive. 74618508
dp[i][j] denotes that you are on jth position of array and you have used values from 1 to i.

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

    hello lonewolf can you please give me more intuition about your solution. i would really appreciate that like in the question we were asked to solve for the number of pairs of arrays and also i didn't get why you multiplied 2 with m with. please i would really appreciate that i always have problem in applying dp whenever we are asked about array construction problems what is your approach for these problems

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

      The question is the same as follows: How many arrays of size 2m can you find that are non-descending? With some maths you should get a combinatorial series that is actually equal to ((2m + n - 1)C2m). (This is a formula for that series). Then you just use dp to calculate this particular value of nCr. Here is my submission 68815420

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

the problem is a standard stars and bars problem. Its quite easy once you know the algorithm. You can understand it through a very good video- link

→ Reply