Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### inazuma_11's blog

By inazuma_11, history, 2 months ago, ,

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 .

• +3

 » 2 months ago, # | ← Rev. 3 →   -16 You already answered your own question:I often get stuck at problems of combinatorics involving dynamic programming
•  » » 2 months ago, # ^ | ← Rev. 2 →   +2 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.
•  » » » 2 months ago, # ^ |   0 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.
•  » » » » 2 months ago, # ^ |   0 I don't get how rating factors into this. You offered nothing of substance in your comment, so why post it?
•  » » » » 2 months ago, # ^ |   0 Let me remind you that you're unrated
•  » » » » 2 months ago, # ^ |   0 I never asked for your help, so please shut up.
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   0 Thanks gupta_samarth for your help ...
 » 2 months ago, # |   +1 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. 74618508dp[i][j] denotes that you are on jth position of array and you have used values from 1 to i.
•  » » 2 months ago, # ^ |   0 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
•  » » » 2 months ago, # ^ |   0 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
 » 2 months ago, # |   0 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