CF - LIS on Permutations
Author: Dong Liu
Slow Solution
Time Complexity:
See here.
Efficient Solution
In the solution, we increase the DP arrray only if , but since both arrays are permutations of length , for each , there must be only one matching element in .
Let us create an array where is the index of in (). Then, we can create another array, where stores .
Notice that every increasing subsequence in corresponds to a common subsequence between and . Increasing subsequence corresponds to the the common subsequence , which is equivalent to . Thus, the length of the longest common subsequence between and is the longest increasing subsequence of .
Implementation
Time Complexity:
C++
#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5;int n, a[N], b[N], c[N], pos[N];vector<int> lis;int main() {cin.tie(0)->sync_with_stdio(0);cin >> n;
Java
import java.io.*;import java.util.*;public class Main {Code Snippet: Kattio (Click to expand)public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt();int[] a = new int[n + 1], b = new int[n + 1], c = new int[n + 1],
Python
from bisect import bisect_leftn = int(input())a = list(map(int, input().split()))b = list(map(int, input().split()))# pos is the inverse of apos = [0] * (n + 1)c = [0] * n
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!