All Tracks Algorithms String Algorithms Problem

(Problem C ) Error Sequence
Tag(s):

Algorithms, Medium, String, Suffix Automata

Problem
Editorial
Analytics

Consider a strictly-increasing sequence of integers \(a_1, a_2, \dots, a_k\). Alice picked a continuous sequence \(p_1, p_2, \dots, p_n\) from it.

Bob then removed exactly \(n-m\) numbers from this sequence, while maintaining the relative order of the remaining elements, thus obtaining a sequence \(q_1, q_2, \dots, q_m\). He then subtracted \(q_1\) from all the elements to form the final sequence \(b_1, b_2, \dots, b_m\).

For example, let \(\{a_i\} = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}, p_1 = 11, n = 6, m = 4\). This yields the sequence of primes \(p=\{11, 13, 17, 19, 23, 29\}\). Assume that Bob has removed the numbers 17 and 23 to obtain \(q=\{11, 17, 19, 29\}\). After that, he subtracted 11 from every element to get \(b=\{0, 6, 8, 18\}\).

Alternatively, he could have removed 11 and 29 to obtain the sequence \(q = \{13, 17, 19, 23\}\) and \(b = \{0, 4, 6, 10\}\). Note that the same sequence may also be generated by, for instance, picking \(p = \{13, 17, 19, 23, 29, 31\}\) and removing 29 and 31.

Eve found the number \(n\) and the sequences \(\{a_i\}_{i=1}^{k}\)\(\{b_i\}_{i=1}^{m}\). She now wonders, what is the smallest possible \(p_1\), that could yield the sequence \(\{b_i\}_{i=1}^{m}\) through the process described above?

Input format:

  • First line: \(t \) (number of test cases)
  • For each test case
    • First line: Three space-separated integers \(k\)\(n\)and \(m\) satisfying \(1 \leq m \leq n \leq k\)
    • Second line: \(k\) space-separated integers \(\{a_i\}_{i=1}^k\) satisfying \(0 \leq a_i \leq 10^9\) and \(a_i < a_{i+1}\)
    • Third line: \(m\) space-separated integers \(\{b_i\}_{i=1}^m\). It is guaranteed that \(b_1 = 0\) .

It is guaranteed that there always exists a solution.

Output:

For each test case, output a single integer \(p_1\) - the smallest element in the sequence that Alice chose.

Scoring:

In all test sets, \(1 \leq t \leq 10\).

In the first test set, worth 12 points, \(1 \leq m = n \leq 10^2\) and \(k \leq 10^4\).

In the second test set, worth 21 points, \(1 \leq m < n \leq 10^2\) and \(k \leq 10^4\).

In the third test set, worth 24 points, \(1 \leq m = n \leq 10^5\) and \(k \leq 2*10^5\).

In the fourth test set, worth 25 points, \(1 \leq m \leq n \leq 10^5\)\(n - m \leq 50\) and \(k \leq 2*10^5\).

In the fifth test set, worth 18 points,\(t=3\)\(1 \leq m \leq n \leq 5*10^5\)\(n - m \leq 100\) and \(k \leq 10^6\).

SAMPLE INPUT
1
11 6 4
2 3 5 7 11 13 17 19 23 29 31
0 6 8 18
SAMPLE OUTPUT
11
Explanation

This is the example from the statement.

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #3

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?