Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Marks Crisis!!!

By shihan04 · Limits 1s, 512 MB

Rakib got the result of his previous English exam. But he did very poor in the exam, and went to his English teacher to increase his marks.

There was a question in the exam where Rakib had to rearrange nn sentences to make a valid story. The correct answer was the sequence A1,A2,,An A_1, A_2, \dots, A_n but Rakib wrote the sequence B1,B2,,Bn B_1, B_2, \dots, B_n . The teacher was supposed to give 1 mark for each ii such that Ai=Bi(1in)A_i = B_i (1 \leq i \leq n). But because of Rakib's request, the teacher asked Rakib to find a common subsequence between his answer and the correct one. His marks will then be equal to the length of the common subsequence he finds.

As Rakib wants the highest marks possible, he has to find the longest common subsequence. Since he is really foolish, he wants you to help him.


First you will be given an integer nn (1n1051\leq n\leq 10^5) — the number of sentences in the sequence.The next line will contain nn integers AiA_i (1Ai,in1\leq A_{i},i\leq n). Next line will also contain nn integers BjB_j (1Bj,jn1\leq B_{j},j\leq n).


Print a single integer which indicates the highest possible marks that Rakib can obtain.


2 4 3 5 6 1 8 7
2 8 4 3 5 6 7 1
1 2 3 4 5
3 4 1 2 5



75% Solution Ratio

dip_BRUREarliest, Apr '20

skmonirFastest, 0.0s

CodefresherLightest, 918 kB

mdalaminislamShortest, 447B


Login to submit


First we need to observe that array AAA and BBB are permutations of 111 to nnn. So we can map AAA in...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.