cfisfake's blog

By cfisfake, history, 4 months ago, In English,

How to solve APIO 2016 Boats? I couldn't find a detailed solution anywhere and I tried looking for similar problems to it but couldn't find detailed explanation. The question formally states to find the number of increasing subsequences of length n where each element Ai has constraint Li<=A[i]<=R[i]. the arrays L[i] and R[i] are given to you. n is upto 300.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div. 1 500 from here is the same. You can see the editorial in the comment.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    See the tags, I mentioned topcoder. I was not able to understand from that "brief" tutorial by tourist. xD

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The naive dp is something like this: dp[i][j]= answer for the first i elements given that the last chosen element has value j. The problem here is that j can be too large. However note that we can partition the integers into certain partitions, and only the partition to which j belongs should matter: to be precise, let t1 < t2 < ... < tN be the set {L1, ... , Ln, R1, ... , Rn} in sorted order, then it only matters to which of the intervals (ti, ti - 1) j belongs to. So the dp will now look like this: dp[i][j]= answer for the first i elements given that the last element belongs to the j'th interval. The transitions will be like this: iterate over the k < i for which the number is in another interval, multiply the number of increasing subsequences of length k - i contained in the j'th interval (O(1) formula is easy to derive) by and add it to result. There are a few minor details to work out here (which I unfortuntely I couldn't do in contest time :( ).