# UVa 111

Jump to navigation
Jump to search

## Contents

## 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