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 .
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | SecondThread | 150 |
| 8 | -is-this-fft- | 148 |
| 9 | pajenegod | 145 |
| 10 | BledDest | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 16.04.2024 15:32:22 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
You already answered your own question:
I often get stuck at problems of combinatorics involving dynamic programming
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.
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.
I don't get how rating factors into this.
You offered nothing of substance in your comment, so why post it?
I never asked for your help, so please shut up.
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.
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.
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
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 ofnCr. Here is my submission 68815420the 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