asawa_harsh's blog

Unable to solve Atcoder ABC237 Problem F

By asawa_harsh, history, 2 years ago, In English

Can anyone tell me the dp transitions for this problem ? Even after seeing the editorial I am not able to code.

Problem link

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

»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

we will assume fir, sec, and third are three elements in lis array and fir<=sec<=third. now we'll assume x be the next element, then we'll check which element it replace fir, sec, third or none. you can look at this for reference. Link

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thanks ! Can u explain base case in your code ? I wrote this as base case but not getting correct output of samples.

    for (int i = 1; i <= m; i++) {

    for (int j = i + 1; j <= m; j++) {

      for (int k = j + 1; k <= m; k++) {

                dp[3][i][j][k] = 1; // Base Case

       }

 }

    }

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wrote dp[0][m + 1][m + 1][m + 1] = 1 as my base case because initially there will be no elements in lis array and i took m+1 so that all subsequent elements will be less than it so can be instantly inserted in lis array.

      → Reply