VM7WC '16 #2 Gold - GGG

View as PDF

Submit solution

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

Problem type

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 N (1 \le N \le 10^6), the number of G-strings that Jeffrey has in his G-sequence. The next line will contain N integers, each denoting the integrity of one of the G-strings in Jeffrey's G-sequence, and in chronological order. If I is the integrity of a G-string, 0 \le I \le 10^6.

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

1 2 3 4 5
2 3 4 5 1

Sample Output



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

    is my approach to this problem just flat out wrong

    • 7
      awaykened  commented on April 4, 2016, 12:42 a.m. edited

      both your time and memory complexity is N^2, where N here is 1\,000\,000

      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

      • 6
        Flowright  commented on April 4, 2016, 2:44 a.m.

        Definitely seems like it :< thanks tho

  • 2
    YouZ  commented on Jan. 17, 2016, 5: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.

    • 4
      r3mark  commented on Jan. 17, 2016, 2:28 p.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.

      • 2
        YouZ  commented on Jan. 17, 2016, 10:26 p.m.

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

  • 2
    minecraftyugi  commented on Jan. 16, 2016, 9:49 p.m.

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

    • 2
      d  commented on Jan. 21, 2016, 2:53 p.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)

      • 2
        println_hi_  commented on Jan. 28, 2017, 2:09 p.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?

        • 2
          Kirito  commented on Jan. 28, 2017, 3:16 p.m.

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

  • 4
    fsdom  commented on Jan. 15, 2016, 5:20 a.m.

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

    • 5
      JeffreyZ  commented on Jan. 15, 2016, 1:56 p.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.