Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply divide-and-conquer algorithm in the problem. Make sure ALL test cases return expected outputs by providing output screenshots.
Hint: Use kth order statistics
Output Format Output consists of K lines. For each query, output the age of Danny's soulmate in hours, similar to the input.
Parameters: n : int - number of ages given ages : array-like - list of ages s1 : int - start index of Danny's family. Also Danny's index e1 : int - end index of Danny's family s2 : int - start index of Danny's found family e2 : int - end index of Danny's found family
Return the age of Danny's soulmate """ def solve(n,ages,s1,e1,s2,e2): # TODO
n,k = list(map(int,input().strip().split(" ")))
ages = [int(input()) for i in range(n)]
answers = []
for i in range(k): s1, e1, s2, e2 = list(map(int,input().strip().split(" "))) answers.append(solve(n,ages,s1,e1,s2,e2))
print("\n".join(list(map(str,answers))))
Transcribed Image Text:Danny has been single all his life. He is desperate to find a match. While reading a shady tabloid column, he
saw a surefire way to find a soulmate.
Step 1:
Find a family with at least as many children as yours. For example, if Danny's family has K children, himself
included, he has to find a family with at least K children.
Step 2:
Find your birth order in your family. For example, if Danny is 20 years old and his siblings are 12, 15, 18, 32,
and 33 years old, Danny's birth order is 3 since he is the 3rd oldest.
Step 3:
Find the person in the other family with the same birth order. For example, if the other family has children
with ages 20, 21, 25, 27, 37, and 40, Danny's soulmate is the one aged 27.
Danny can't wait to find his soulmate. He is already done with step 1. Can you help him with steps 2 and 3?
Input Format
Input contains several queries to be processed. Input begins with a line containing two space-separated
integers: N and K. N is the number of ages given. K is the number of queries to answer.
N lines follow. Each line contains one integer A,, indicating the age of the ith person in hours. The first
person is labeled as Person 1. The last person is Person N.
K lines follow, each representing one query. Each line contains four space-separated integers S₁, E1, S2, E2
indicating the start index of the first family, end index of the first family, start index of the second family, and
end index of the second family. For example, if the query contains "1 5 10 20", the first family is Person 1 until
Person 5 in the prior list. The second family is Person 10 until Person 20. Also, assume Danny is Person S₁.
Constraints
1≤ N≤ 105
1≤ K≤ 5.10³
0 ≤ A; ≤ 107 All A; are guaranteed to be distinct.
1 ≤ E₁ - S₁ ≤ E2₂ - S₂ ≤ 104
1 ≤ S₁ ≤ E₁ ≤N
1 ≤ S₂ ≤ E2 ≤ N
Process or set of rules that allow for the solving of specific, well-defined computational problems through a specific series of commands. This topic is fundamental in computer science, especially with regard to artificial intelligence, databases, graphics, networking, operating systems, and security.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
