rhezo's blog

By rhezo, history, 9 years ago, In English

How to solve BAT2-SPOJ?

My idea is that you need to find all increasing subsequences from left (1->n), and all increasing subsequences from right (n->1). Since n can be <=100, this will take 2^100 time, which is too slow. How can it be done efficiently? Or am I thinking in the wrong direction?

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I think so. You must find length of max increasing subsequence in array B. Array B = A + A, where A is array that we were given. It can be done in O(nlog(n))

code
»
9 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Clearly you don't have enough time to enumerate all those sequences, so that direction won't lead very far. Note that instead of thinking that Catwoman moves from right to left in an increasing sequence, the problem doesn't change if she moves from left to right in a decreasing sequence.

Why is this helpful? Because now Batman and Catwoman are moving in the same direction, which should let you use a really well-known technique to construct both of their paths at the same time.

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

    what is this algorithm ?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I thought of finding the length of longest increasing subsequence and the length of longest decreasing subsequence but what if they have a common term ?

    Could you please give more hints?

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

we can see that its finding disjoint increasing subsequence and longest decreasing subsequence used simple DP

dp[pos][x][y] = the longest increasing subsequence and decreasing subsequence, using elements 1..pos, and the last index of longest increasing is x, while the last index of longest decreasing is y

then dp[pos][x][y] is the max of the following:

dp[pos+1][x][y] //not take the pos element
dp[pos+1][pos][y] + 1 //take the pos element as the next element in increasing (a[pos] > a[x])
dp[pos+1][x][pos] + 1 //take the pos element as the next element in decreasing (a[pos < a[y])
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just ACed the problem using your logic,thanks a lot... But I submitted a recursive DP solution, Can someone provide me a bottom-up table method DP of this problem,thanks a lot!!

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

      Can you please share your code, with some comments. And I am not getting what will be the base case in recursion.

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

        Sure , CODE

        Pardon me , the comments can be a little hard to read because of the indentation , but its still readable and I did my best explaining the DP in the code , If you dont get it , ask!

»
7 years ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Found the error, fixed