VM7WC '16 #2 Gold - GGG

View as PDF

Points: 15
Time limit: 0.75s
PyPy 2 1.4s
PyPy 3 1.4s
Memory limit: 64M
PyPy 2 512M
PyPy 3 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

From the previous question, G-strings are strings that are meant to be made of mostly only the character G. However, G-strings can become contaminated with other capital alphabetical characters, sometimes to the point that there are no more G's left in the G-string. A G-string should not be confused with the article of clothing.

Jeffrey is a collector of G-strings. He has them packaged in a sequence of G-strings, which he refers to as a G-sequence. Jeffrey collects G-strings based on their integrity; if he finds a G-string, he will not add it to his G-sequence if he already has a G-string of the same integrity. As a result, every G-string in his G-sequence has a unique integrity. The ordering of the G-strings within Jeffrey's G-sequence matters, as he has ordered them chronologically by time of entry.

Leo is also a collector of G-strings. Just like Jeffrey, he collects G-strings by integrity and no two G-strings in his G-sequence are of the same integrity. Coincidentally, he also ordered his G-sequence chronologically, like Jeffrey. The two G-string connoisseurs are discussing about their G-sequences, and would like to find the length of the longest subsequence that appears in both G-sequences. A subsequence can be derived from a G-sequence by deleting some of its terms. Help them calculate this number!

Input Specification

On the first line, there will be the integer , the number of G-strings that Jeffrey has in his G-sequence. The next line will contain integers, each denoting the integrity of one of the G-strings in Jeffrey's G-sequence, and in chronological order. If is the integrity of a G-string, .

The next two lines will be of the same form, but will describe Leo's G-sequence instead.

Output Specification

On a single line, print the length of the longest common subsequence of G-strings between Jeffrey's and Leo's G-sequences.

Sample Input

5
1 2 3 4 5
5
2 3 4 5 1

Sample Output

4

• commented on April 3, 2016, 7:21 p.m.

is my approach to this problem just flat out wrong

• commented on April 3, 2016, 8:42 p.m.

both your time and memory complexity is , where here is

firstly you go way over memory limits, and secondly C++ can only do around 1 billion operations per second compared to the trillion operations your program will run in its worst case

you'll need to find a way to heavily optimize your algorithm, or come up with something different :P

• commented on April 3, 2016, 10:44 p.m.

Definitely seems like it :< thanks tho

• commented on Jan. 17, 2016, 12:46 a.m.

I just want to clarify something. This question is asking for the largest common subsequence correct? So the largest common sequence of numbers that appears in both sequences? Because I've tried 5 different solutions and every time I get a few WAs. I tried testing random numbers, but I just can't figure out what I'm doing wrong. Just want to make sure I read the question correctly.

• commented on Jan. 17, 2016, 9:28 a.m.

A subsequence is a sequence that can be derived from the original sequence by only deleting certain elements of the original sequence while not changing the order of the elements. This might be where you are making your mistake.

• commented on Jan. 17, 2016, 5:26 p.m.

Thanks, I think I know what I was doing wrong now.

• commented on Jan. 16, 2016, 4:49 p.m.

Can the question be solved within the memory limit in python? I'm 1 Mb over.

• commented on Jan. 21, 2016, 9:53 a.m. edited

No. Even if you only tried to get the largest number in the input, you will TLE or MLE. 80/100 is possible in Python, though.

(this question might be solvable in PyPy 2 if the memory limit is increased to 128M, and even 128M is fairly strict)

• commented on Jan. 28, 2017, 9:09 a.m.

Wow why is that?

The sequence would take up at-most 8 megabytes in c++ probably just 4.

How is it that python is so inefficient?

• commented on Jan. 28, 2017, 10:16 a.m.

Custom limits have been added so it is possible to solve the problem in PyPy.

• commented on Jan. 15, 2016, 10:52 p.m.

^

• commented on Jan. 17, 2016, 6:45 p.m.

Not sure. My solution was in C++.

• commented on Jan. 15, 2016, 11:03 p.m.

Oh wait, it's actually possible.

• commented on Jan. 15, 2016, 10:58 p.m.

I don't think so. I kept getting MLE for a few cases so I switched to C++.

• commented on Jan. 15, 2016, 10:02 p.m.

I can't even read the input in time, even with C++ and fast input.

• commented on Jan. 15, 2016, 12:20 a.m.

Can the G string lengths of Jeffrey and Leo differ or the same lengths?

• commented on Jan. 15, 2016, 8:56 a.m.

The lengths of the G-strings don't matter in this question.

If you're talking about the length of the G-sequences, yes.

• commented on Jan. 14, 2016, 4:37 p.m.

A mistake has been found in one of the test cases, submissions have been rejudged.