Its easy to solve this using brute force approach but I was curious to know if there was any better approach :)

Revision en1, by MMA_199, 2021-01-03 22:26:49

Hi Codeforces

One of my Codeforces friends and I were solving a binary search question([Multiplication Table])(http://https://mirror.codeforces.com/problemset/problem/448/D) and then we thought of the problem stated below

Suppose we have a graph in the form of an adjacency list and each list is sorted in non decreasing order(Positive numbers only with no repetitions). We are given q queries and for each query we will take the adjacency lists which are mentioned in the query. Now the lists mentioned in the query are arranged in non-decreasing order and we have to find the Kth element in the new arrangement of elements.

Each list is sorted. Each query contains 2 lines

1st line contains the list numbers that will be merged and 2nd line contains an integer K(Element in the Kth position after arrays are merged and sorted)

Suppose the example given below

Example

  1. {2,4,7,9}

  2. {6,11,13,18}

  3. {1,3,5,8,14}

  4. {12,26}

  5. {10,24}

Q=2

3 4 5

5

1 2 3

11

Answer for 1st query- 12

Answer for 2nd query- 13

Its easy to implement this in the brute force approach but I was curious to know if there was any better approach considering the queries are very large 10^4.

I would like to know your approach for this problem.

Thanks and have a good day:)

Tags #binary search, adjacency list, #sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English MMA_199 2021-01-04 00:43:24 11 Tiny change: 'h question[Multiplic' -> 'h question ([Multiplic'
en2 English MMA_199 2021-01-03 22:30:25 58
en1 English MMA_199 2021-01-03 22:26:49 1429 Initial revision (published)