K-th element P63584


Statement
 

pdf   zip   main.cc

thehtml

Using the definitions

typedef vector<int> VI; typedef vector<VI> VVI;

implement a function

int k_esim(int k, const VVI& V);

to return the k-th global element (starting at one) of the elements in the vector of vectors V. Let n = V.size(). For every 0 ≤ i < n, V[i] is sorted increasingly. Furthermore, there are no repeated elements in V.

For exemple, if k = 5, n = 3, and the three vectors are

|| V[0]

121015


V[1]

-5-312


V[2]

034620

||

then the answer is 2, which is the fifth smallest element inside all the vectors.

Let m = ∑0n−1 V[i].size(). Assume that k is between 1 and m, that n is between 2 and 500, and that some V[i] can be empty. If needed, you can implement auxiliar procedures. Take into account that, for the “large” test cases, k = Θ(n) and m = Θ(n2). The expected solution in this cas has cost Θ(n logn).

Observation You only need to submit the required procedure; your main program will be ignored.

Information
Author
Enric Rodríguez
Language
English
Translator
Salvador Roura
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++