MMA_199's blog

By MMA_199, history, 4 years ago, In English

Hi Codeforces

One of my Codeforces friends and I were solving a binary search question (Multiplication Table) 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 of the query 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}

//Suppose here 2 queries are given .

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:)

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it