Lyft Level 5 Challenge 2018 - Final Round


A. The Tower is Going Home
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 3
6
8
1 5 6
1 9 4
2 4 2
Output
1
Input
1 3
4
1 5 3
1 9 4
4 6 6
Output
1
Input
0 2
1 1000000000 4
1 1000000000 2
Output
2
Input
0 0
Output
0
Input
2 3
4
6
1 4 3
1 5 2
1 6 5
Output
2
----------------------------------------------------------------------------------------------------
B. Intersecting Subtrees
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
3
1 2
2 3
1
1
1
2
2
1
Output
A 1
B 2
C 1
Input
2
6
1 2
1 3
1 4
4 5
4 6
4
1 3 4 5
3
3 5 2
3
6
1 2
1 3
1 4
4 5
4 6
3
1 2 3
3
4 1 6
5
Output
B 2
C 1
A 1
C -1
----------------------------------------------------------------------------------------------------
C. Optimal Polygon Perimeter
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
2 4
4 3
3 0
1 3
Output
12 14 
Input
3
0 0
0 2
2 0
Output
8 
----------------------------------------------------------------------------------------------------
D. Deduction Queries
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
12
2 1 2
2 1 1073741822
1 0 3 4
2 0 0
2 3 3
2 0 3
1 6 7 3
2 4 4
1 0 2 1
2 0 0
2 4 4
2 0 0
Output
-1
-1
-1
-1
5
-1
6
3
5
Input
4
1 5 5 9
1 6 6 5
1 6 5 10
2 6 5
Output
12
----------------------------------------------------------------------------------------------------
E. Grid Sort
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
4 1 2
7 6 3
8 5 9
Output
1
8 1 4 7 8 5 6 3 2
Input
3 5
1 2 3 5 10
11 6 4 14 9
12 7 8 13 15
Output
3
4 4 14 13 8
4 5 10 9 4
4 12 7 6 11
----------------------------------------------------------------------------------------------------
F. DFS
time limit per test: 6 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 2
1 2
1 3
2 3
3 2
Output
2
3
Input
6 6
1 2
2 3
1 4
4 5
1 6
2 5
3 4
5 2
6 4
3 4
6 5
Output
3
2
3
2
3
2
----------------------------------------------------------------------------------------------------
