VM7WC '16 #2 Gold - GGG
View as PDFFrom 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 1Sample Output
4
Comments
is my approach to this problem just flat out wrong
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
Definitely seems like it :< thanks tho
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.
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.
Thanks, I think I know what I was doing wrong now.
Can the question be solved within the memory limit in python? I'm 1 Mb over.
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)
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?
Custom limits have been added so it is possible to solve the problem in PyPy.
Can the G string lengths of Jeffrey and Leo differ or the same lengths?
The lengths of the G-strings don't matter in this question.
If you're talking about the length of the G-sequences, yes.