plehem's blog

By plehem, history, 16 months ago, In English,

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 на пляже. 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 is 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!

Read more »

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