Secretary problem
Statement
Goal
You are interviewing a series of n candidates for a position. The candidates are presented to you in random order, each represented by his/her score, and you must make an immediate decision on whether to hire a candidate or not. You have decided on the following strategy:(1) Reject the first n/
(2) From the remaining candidates, hire the first with a strictly higher score than all the rejected candidates.
Output the zero-based index of the hired candidate. If the strategy ends up with no hiring, output
Example:
Input:
9
5 3 8 2 7 9 4 1 6
Output: 5
In this example, there are 9 candidates. You should reject the first 9/
Input
Line 1: An integer n for the number of candidates.
Line 2: A space separated string containing n integers. The x-th integer represents the score of the x-th candidate.
Line 2: A space separated string containing n integers. The x-th integer represents the score of the x-th candidate.
Output
An integer, the zero-based index of the hired candidate or -1 if none was hired.
Constraints
0 < n <
0 < score <=
Example
Input
9 5 3 8 2 7 9 4 1 6
Output
5
Game modes
Fastest, Shortest
Test cases
1. Example Test
Input
9
5 3 8 2 7 9 4 1 6
Output
5
1. Example val Validator
Input
9
5 3 8 2 7 9 3 3 3
Output
5
2. No hiring Test
Input
9
5 3 8 2 2 2 2 2 2
Output
-1
2. No hiring val Validator
Input
9
5 3 8 1 1 1 1 1 1
Output
-1
3. Strictly better Test
Input
9
5 3 8 2 8 8 1 8 9
Output
8
3. Strictly better val Validator
Input
9
5 3 8 2 8 8 2 9 2
Output
7
4. No hiring (2) Test
Input
5
5 5 4 4 5
Output
-1
4. No hiring (2) val Validator
Input
5
5 5 1 1 5
Output
-1
5. Cutoff (1) Test
Input
5
3 5 1 5 5
Output
1
5. Cutoff (1) val Validator
Input
6
54 12 69 39 50 30
Output
2
6. Cutoff (2) Test
Input
9
18 52 97 97 42 13 93 72 6
Output
-1
6. Cutoff (2) val Validator
Input
9
67 61 86 86 82 14 85 78 24
Output
-1
7. Random 15 Test
Input
15
55 4 45 27 49 9 1 11 4 61 55 81 43 64 37
Output
9
7. Random 15 val Validator
Input
15
41 99 88 81 12 70 31 61 25 95 69 37 94 31 80
Output
-1
8. Random 30 Test
Input
30
93 6 82 73 24 27 63 7 50 59 9 15 51 70 100 57 83 62 28 27 62 40 74 14 84 9 4 32 29 95
Output
14
8. Random 30 val Validator
Input
30
17 54 50 77 35 72 38 63 12 89 87 8 52 55 24 90 5 2 63 100 42 56 49 75 96 44 46 65 68 42
Output
15
9. Random 50 Test
Input
50
54 95 61 15 65 2 95 9 80 7 87 26 10 15 62 43 36 24 28 89 97 42 26 41 88 47 39 81 90 17 13 84 95 80 40 81 18 34 10 87 53 83 46 22 81 53 58 79 59 61
Output
20
9. Random 50 val Validator
Input
50
39 98 1 68 42 43 59 64 85 80 88 8 13 70 43 98 68 41 93 47 66 97 66 65 87 94 57 84 90 37 61 41 66 55 38 56 98 53 33 43 95 49 16 86 86 86 21 56 34 39
Output
-1
10. Random 75 Test
Input
75
47 36 51 10 25 24 57 17 57 35 16 56 17 26 15 69 70 4 10 94 3 86 49 62 77 43 17 70 25 12 77 48 37 82 2 3 73 18 63 2 47 82 51 78 86 46 100 20 37 14 54 27 48 66 87 82 98 15 25 32 61 47 52 21 11 2 65 27 75 63 7 85 25 78 36
Output
46
10. Random 75 val Validator
Input
75
56 96 1 29 30 30 16 48 4 77 77 49 87 71 84 44 36 25 28 5 58 35 88 68 75 24 10 63 56 71 10 17 92 55 17 37 18 88 11 15 85 84 7 82 50 59 84 30 73 59 23 49 70 87 5 81 50 24 50 19 42 31 98 57 44 37 80 63 59 19 17 1 74 79 92
Output
62
11. Random 90 Test
Input
90
27 95 62 32 24 85 66 45 94 17 25 42 71 78 33 13 18 37 69 54 36 81 74 6 65 50 23 64 46 62 41 47 27 90 90 16 75 51 4 28 96 53 78 59 58 13 97 5 4 48 43 71 33 91 77 61 52 2 43 96 71 86 7 22 96 28 24 71 58 59 58 66 68 86 94 32 64 28 87 87 92 38 73 34 23 39 59 62 45 19
Output
40
11. Random 90 val Validator
Input
90
17 12 45 57 36 42 39 62 11 62 7 87 68 10 8 12 72 67 20 55 92 94 61 89 75 16 93 94 71 74 11 44 2 86 10 60 14 17 35 43 53 55 81 83 85 48 48 20 84 68 76 30 6 4 9 3 91 83 51 54 39 42 81 49 99 68 66 82 22 87 2 72 15 81 77 74 17 48 25 22 1 47 56 35 92 88 41 82 14 82
Output
64
Solution language
Solution
Stub generator input