UVa 111

From Algorithmist
Jump to navigation Jump to search

111 - History Grading[edit]

Summary[edit]

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

Explanation[edit]

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):

Gotchas[edit]

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.

Input1[edit]

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

Output1[edit]

1
2
3

Input2[edit]

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

Output2[edit]

6
5
10
9

Solution[edit]

C++: http://acm-solution.blogspot.com/2011/09/acm-uva-111-history-grading.html