This https://codeforces.net/contest/1956/submission/256474898 solution consumes at least (2 * n + 1) * sizeof(int) bytes, on the test #4 the memory usage must be at least 1_600_004 bytes instead of 56 KB.

Proof:

Осталось 11 дней до профессионального праздника шпуртивных программистов, очень надеюсь, что Миша-ибн-Расих-аль-Мирзаян приготовил какой-нибудь подарок для пользователей CF.

https://codeforces.net/contest/1846/submission/215981788

1. how to type capital letters?
2. if you've seen this approach before, post links in the comments.

MikeMirzayanov не читает ЛС:

The code (Ruby) below is a solution for https://leetcode.com/problems/uncrossed-lines/

Note: In Ruby Array#shift is O(1)

The trick is on the lines 14-15:

def max_uncrossed_lines a, b
    s = 0
    while !a.empty? && a.first == b.first
        a.shift
        b.shift
        s += 1
    end
    while !a.empty? && a.last == b.last
        a.pop
        b.pop
        s += 1
    end
    # These two lines
    c = a.to_set & b.to_set
    a, b = *[a, b].map! { | v | v.filter { c === _1 } }
    r0, r1 = *Array.new(2) { [0] * (b.size + 1) }
    for x in a
        for y, j in b.each_with_index
            r1[j + 1] = (x == y) ?
                1 + r0[j] :
                [r0[j + 1], r1[j]].max
        end
        r0, r1 = r1, r0
    end
    s + r0.last
end