Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### rhezo's blog

By rhezo, history, 8 years ago, 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? Comments (11)
| Write comment?
 » 8 years ago, # | ← Rev. 3 →   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)) codeint t; cin >> t; while (t > 0){ int n; cin >> n; int a[2*n]; for (int i = 0; i < n; i++){ cin >> a[i]; a[i + n] = a[i]; } vector < int > seq(2*n + 1, 2e9); seq = -1; int ans = 0; for (int i = 0; i < 2*n; i++){ int p = (int)(upper_bound(seq.begin(), seq.end(), a[i]) - seq.begin()); if (a[i] > seq[q - 1]){ seq[p] = a[i]; ans = max(ans, p); } } cout << ans << endl; t--; } 
•  » » 55 4 2 3 1The correct answer is 5 (5->4->1, 2->3).
 » 8 years ago, # | ← Rev. 2 →   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.
•  » » what is this algorithm ?
•  » » » DP
•  » » 7 years ago, # ^ | ← Rev. 2 →   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?
 » 7 years ago, # | ← Rev. 3 →   we can see that its finding disjoint increasing subsequence and longest decreasing subsequence used simple DPdp[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 ythen 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]) 
•  » » 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!!
•  » » » Can you please share your code, with some comments. And I am not getting what will be the base case in recursion.
•  » » » » Sure , CODEPardon 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!
 » 6 years ago, # | ← Rev. 3 →   Found the error, fixed