Gargari and Permutations (Codeforces 463D)
Tags: Implement, graphs

Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Input: The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.

Output: Print the length of the longest common subsequence.

Note: The answer for the first test sample is subsequence [1, 2, 3].

Sample Inputs:
4 3
1 4 2 3
4 1 2 3
1 2 4 3

Sample Outputs:
3

Solution (Python):
(q, k) = tuple(map(int, input().split()))
Q = [set(range(q)) for _ in range(q)]
for _ in range(k):
    p = set()
    for j in map(int, input().split()):
        Q[j - 1] -= p
        p.add(j - 1)
sa = sorted(range(q), key=lambda i: len(Q[i]))
maxx = [0] * q
res = 0
for i in sa:
    m = 1 + maxx[max(Q[i], key=lambda e: maxx[e])] if Q[i] else 0
    maxx[i] = m
    res = max(res, m)
print(res)

Solution (Python):
def main():
    (n, k) = tuple(map(int, input().split()))
    a = [set(range(n)) for _ in range(n)]
    for i in range(k):
        p = set()
        for j in map(int, input().split()):
            a[j - 1] -= p
            p.add(j - 1)
    sa = sorted(range(n), key=lambda i: len(a[i]))
    maxx = [0] * n
    res = 0
    for i in sa:
        m = 1 + maxx[max(a[i], key=lambda e: maxx[e])] if a[i] else 0
        maxx[i] = m
        res = max(res, m)
    print(res)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000)
from copy import deepcopy
from math import inf, gcd, sqrt, ceil, floor
from bisect import bisect_left, bisect_right
from string import ascii_lowercase, ascii_uppercase
from collections import deque, Counter, defaultdict
from functools import cache, lru_cache, reduce, cmp_to_key
from itertools import accumulate, permutations, combinations
from heapq import heapify, heappush, heappop, nlargest, nsmallest

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LMII():
    return list(map(int, input().split()))
mod = 10 ** 9 + 7
dxy = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def solve():
    (n, m) = MII()
    data = []
    for _ in range(m):
        data.append(LMII())
    index = [[0 for _ in range(n + 1)] for _ in range(m)]
    for i in range(m):
        for (j, x) in enumerate(data[i]):
            index[i][x] = j
    dp = [1] * (n + 1)
    for i in range(1, n + 1):
        x = data[0][i - 1]
        for j in range(1, i):
            y = data[0][j - 1]
            ok = True
            for idx in index:
                if idx[y] > idx[x]:
                    ok = False
                    break
            if ok:
                dp[i] = max(dp[i], dp[j] + 1)
    print(max(dp))
if __name__ == '__main__':
    solve()