Although the LIS solution is more efficient than the DP ones, it was very tough to figure out and implement. The DP approach is significantly better to think and implement. Learned a lot from this problem! Thanks!

Active In

Competitive Programming

Featured Contributions

comment in this discussion

Although the LIS solution is more efficient than the DP ones, it was very tough to figure out and implement. The DP approach is significantly better to think and implement. Learned a lot from this problem! Thanks!

Read more… (37 words)

comment in this discussion

I also did BAT2 and BORW using both top-down and bottom-up DP. For the BORW problem (in which the time taken is more conspicuous), the top-down solution gives 1.74s while the bottom-up solution gives 2.94s. The contrast between this and my earlier solution of 0.45s can be explained due to the former's time complexity being O(n^3) while the latter's is only O(n^2 log n).

The difference between both DP solutions is surprising and counter-intuitive. Perhaps it is because a lot of 3d dp states are not achieved but are nevertheless filled in the bottom-up approach, while the recursion is very economical in this regard. Is this right? Are there any other factors affecting the runtimes?

Here are my DP solutions for BORW:

#include <bits/stdc++.h>using namespace std;int n;int a[201];int c[201][201][201];int f(int ti, int td, int i){if(i == n + 1)return 0;if(c[ti][td][i] != -1)return c[ti][td][i];int mx = 0;if(!ti || a[i] > a[ti])mx = 1 + f(i, td, i+1);if(!td || a[i] < a[td])mx = max(mx, 1 + f(ti, i, i+1));mx = max(mx, f(ti, td, i+1));c[ti][td][i] = mx;return mx;}int main(){while(true){cin >> n;if(n == -1)break;for(int i = 1; i <= n; ++i)cin >> a[i];memset(c, -1, sizeof c);cout << n - f(0, 0, 1) << '\n';}}

#include <bits/stdc++.h>using namespace std;int n;int a[201];int c[201][201][202];int main(){while(true){cin >> n;if(n == -1) break;for(int i = 1; i <= n; ++i)cin >> a[i];memset(c, 0, sizeof c);for(int i = n; i > 0; --i){for(int ti = 0; ti <= n; ++ti){for(int td = 0; td <= n; ++td){int mx = 0;if(!ti || a[i] > a[ti])mx = 1 + c[i][td][i+1];if(!td || a[i] < a[td])mx = max(mx, 1 + c[ti][i][i+1]);mx = max(mx, c[ti][td][i+1]);c[ti][td][i] = mx;}}}cout << n - c[0][0][1] << '\n';}}

Read more… (122 words)

comment in this discussion

I did this problem by listing out all the longest increasing subsequences and all the longest decreasing subsequences and then checking every pair of these for common rooms. Although it feels like this should take too long, I got AC with 0.00s on BAT2. Even the related problem BORW accepted this solution with AC at 0.45s.

#include <bits/stdc++.h>using namespace std;int main(){int t;cin >> t;while(t--){int n;cin >> n;vector<int> v(n);for(int &x: v)cin >> x;vector<vector<vector<int>>> vi = {{}};vector<int> li = {v[0]};for(int i = 0; i < n; ++i){int x = v[i];auto it = lower_bound(li.begin(), li.end(), x);int y = (it - li.begin()) + 1 + n - i;if(y < 0 || y < vi.size())continue;if(it == li.begin()){li[0] = x;vi[0].push_back({i});}else{int j = it - li.begin();if(it == li.end()){li.push_back(x);vi.push_back({});}else{*it = x;}for(auto &xv: vi[j - 1]){if(v[xv.back()] < x){vi[j].push_back(xv);vi[j].back().push_back(i);}}}}vector<vector<vector<int>>> vd = {{}};vector<int> ld = {v[0]};for(int i = 0; i < n; ++i){int x = v[i];auto it = lower_bound(ld.begin(), ld.end(), x, greater<int>());int y = (it - ld.begin()) + 1 + n - i;if(y < 0 || y < vd.size())continue;if(it == ld.begin()){ld[0] = x;vd[0].push_back({i});}else{int j = it - ld.begin();if(it == ld.end()){ld.push_back(x);vd.push_back({});}else{*it = x;}for(auto &xv: vd[j - 1]){if(v[xv.back()] > x){vd[j].push_back(xv);vd[j].back().push_back(i);}}}}const vector<vector<int>> &iv = vi.back(), &dv = vd.back();bool fd = false;for(auto &v1 : iv){for(auto &v2 : dv){int i1 = 0, i2 = 0;bool br = false;while(true){if(v1[i1] == v2[i2]){br = true;break;}if(v1[i1] < v2[i2]){++i1;if(i1 == v1.size())break;}else{++i2;if(i2 == v2.size())break;}}if(!br){fd = true;break;}}if(fd)break;}if(fd)cout << li.size() + ld.size() << '\n';elsecout << li.size() + ld.size() - 1 << '\n';}}

Read more… (56 words)