Please Help with this Problem

Revision en10, by plehem, 2018-03-26 10:32:57

Hello everyone!

Since, I've found out that I'm weak at DP tagged problems, I decided to fix it, now I'm struggling at one really cool problem.

The problem is 588D - Duff in Beach. I found a solution but after reading the editorial I realized that it solves different problem. Perhaps I misunderstood the problem. So, please explain the following case where I think answer should be 48 but it's 30:

3 12 2
5 9 1

Author's output: 30, but there are 48 non-decreasing subsequences, e.g.

5 9 1  5 9 1  5 9 1   5 9 1  --> b
1 2 3  4 5 6  7 8 9  10 11 12 --> positions

length 1 subsequence 12
length 2: 
1-4,1-5,1-7,1-8,1-10,1-11,2-5,2-8,2-11,3-4,3-5,3-6,3-7,3-8,3-9,3-10,3-11,3-12,
4-7,4-8,4-10,4-11,5-8,5-11,6-7,6-8,6-9,6-10,6-11,6-12
7-10,7-11,8-11,9-10,9-11,9-12

total 36+12 = 48

Thanks in advance!

Any help'll be appreciated!

Tags dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English plehem 2018-03-26 12:46:01 3 Tiny change: ' 48 but it's 30:\n\n~' -> ' 48 but it is 30:\n\n~'
en10 English plehem 2018-03-26 10:32:57 31 Tiny change: 'preciated!\n\nSorry, for my poor English.' -> 'preciated!'
en9 English plehem 2018-03-26 02:48:20 5 Tiny change: 'y, for my English.' -> 'y, for my poor English.'
en8 English plehem 2018-03-25 23:42:40 2 Tiny change: 'already>\nSince, I' -> 'already>\n\nSince, I'
en7 English plehem 2018-03-25 23:41:55 23 Tiny change: 'eryone! \n\nSince, I' -> 'eryone! \n<fucking reply already>\nSince, I'
en6 English plehem 2018-03-25 21:08:28 4 Tiny change: 'weak at **dp** tagged ' -> 'weak at **DP** tagged '
en5 English plehem 2018-03-25 19:53:01 12
en4 English plehem 2018-03-25 19:50:16 411 Tiny change: ' [problem:588D]. I found' -> ' [problem:<b>588D<b>]. I found'
en3 English plehem 2018-03-24 20:31:19 2 Tiny change: '[Problem](http://c' -> '[Problem D](http://c'
en2 English plehem 2018-03-24 17:43:38 4 Tiny change: 'problem/587/B)\n\nI mig' -> 'problem/588/D)\n\nI mig'
en1 English plehem 2018-03-24 14:08:18 614 Initial revision (published)