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

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter19: Probabilistic Dynamic Programming

Section19.4: Further Examples Of Probabilistic Dynamic Programming Formulations

Problem 7P

See similar textbooks

Related questions

Concept explainers

Question

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in java. 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 merge sort/quicksort

Output Format

Output consists of K lines.

For each query, output the age of Danny's soulmate in hours, similar to the input.

Sample Input 0
5 3
16
8
14
10
4
2 4 1 5
1 3 1 5
1 5 1 5

Sample Output 0
10
16
16

Sample Input 1
7 3
9
30
10
19
26
3
12
2 2 2 7
1 3 3 7
7 7 2 5

Sample Output 1
30
12
30

Sample Input 2
9 4
26
35
24
32
31
36
27
22
23
2 9 2 9
2 6 1 5
2 8 1 8
1 8 2 9

Sample Output 2
35
32
35
24

The actual code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

String[] parts = br.readLine().trim().split(" ");
int n = Integer.parseInt(parts[0]);
int k = Integer.parseInt(parts[1]);
int[] ages = new int[n];

for(int i = 0; i < n; i++) {
ages[i] = Integer.parseInt(br.readLine().trim());
}

for(int i = 0; i < k; i++){
parts = br.readLine().trim().split(" ");
int s1, e1, s2, e2;
s1 = Integer.parseInt(parts[0]);
e1 = Integer.parseInt(parts[1]);
s2 = Integer.parseInt(parts[2]);
e2 = Integer.parseInt(parts[3]);

sb.append(String.format("%d\n",solve(n,ages,s1,e1,s2,e2)));
}
System.out.print(sb);
}

/*
Solves a test case

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
*/
public static int solve(int n, int[] ages, int s1, int e1, int s2, int e2) {
// TODO
}
}

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₂ ≤ 10¹4
1 ≤ S₁ ≤E <N
1 ≤ S₂ ≤ E2 ≤ N

Expert Solution

Step by step

Solved in 4 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

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.