ACMICL4 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

http://www.codechef.com/ICL2015/problems/ACMICL4

Author:

Ravi Shankar Pandey

Tester:

Shubham Gupta

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Longest Common Subsequence and Longest Increasing Subsequence

EXPLANATION:

This is a classical LCS(Longest Common Subquence) problem can solved using Dynamic Programming method.
Using classical LCS Dynamic Programming algorihtm will have a complexity of O(N*N).
But with given constraints we can easily see that it will time out(TLE).

Since in this particular case the max possible number is 10^5 and each number comes only once in an array. We can easily convert this LCS problem to a LIS(Longest Increasing Subsequence) in the following way:-
first A3 stores the index of an element in A1
then A1 sotres the index of an element of A2 in A3
remove all non-zero elements of A1
then finally find LIS of A1

This aproach has run time complexity of O(nlog(n))

SOLUTION:

intialize an array A3 with all values as zero
	then
		for each i in A1
		A3[A1[i]] = i;
		for each i in A2
		A1[i] = A3[A2[i]]
		res = LIS(A1)
2

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346

2 Likes