UVa 111

From Algorithmist

Contents 1 111 - History Grading 2 Summary 3 Explanation 4 Notes 5 Input1 6 Output1 7 Input2 8 Output2

[edit] 111 - History Grading

• http://acm.uva.es/p/v1/111.html

[edit] Summary

This is a DP Problem - a modified Longest Increasing Subsequence. Also it can be solved as Longest Common Subsequence but LIS is more clear.

[edit] Explanation

To find Longest Common Subsequence you can use DP: Let we have 2 sequences a[1..n], b[1..n]. And table m[0..n,0..n] were m[i,j] if the longest common subsequence of a[1..i] and b[1..j]. Then for each (i,j):

m[i,j] = m[i - 1,j - 1] + 1,a[i] = b[j]

m[i,j] = max(m[i - 1,j],m[i,j - 1]),a[i] < > b[j]

[edit] Notes

In problem you are given not exactly comparable sequences. Input "5 2 3 1 4" means that 1 must go 5th, 2 must go 2d, 3 must go 3d, 4 must go 1st and 5 must go 4th.

[edit] Input1

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

[edit] Output1

1
2
3

[edit] Input2

10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

[edit] Output2

6
4
10
5