shakil_AUST's blog

DP Problem Help ( Uva 12744 — Just Some Permutations — 2 )

By shakil_AUST, history, 9 years ago, In English

Good Day everyone . Can anyone please tell me the process how to solve this problem . Thanx in advance :)

Tags dp, uva
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

DP with bitmasks. You can use two bitmasks, one for which numbers you have taken so far from the permutation, and the other to indicate which of these numbers are considered in the LIS. You need to update these two masks accordingly whenever you add the next number. Complexity: O(n * 3^n) since the LIS mask is always a subset of the former.

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

    sgtlaugh thank you for your reply . I am troubling with how to do the Lis part calculation . If you kindly post a sudo code for me then it will be easy to understand :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Basically the idea is that you store the values of the lis array in a bitmask. The lis array is the array in the standard N log N algorithm where usually binary search is used to update it.

      https://ideone.com/LEOM5d

      → Reply