Problem 309930 · medium · Level 03 Linear Management & Searching

Catch Nineteen in Twenty

precision · recall · decision threshold · sorting · sweep

A quick blood test gives every patient a score between 0 and 1; patients with a score of at least a threshold t are sent for a full examination. Missing an ill patient is serious, so the clinic demands a recall of at least min_recall: of the ill patients, at least that share must be sent. Among the thresholds that achieve it, the clinic wants the one with the highest precision (the share of sent patients who are really ill), so that as few healthy people as possible are sent.

Write pick_threshold(scores, truth, min_recall), where truth[i] is 1 for an ill patient and 0 for a healthy one. Only the values that occur in scores are candidate thresholds. Return a tuple (t, precision, recall) for the candidate with recall at least min_recall and the highest precision; if several have the same precision (as exact fractions), return the largest of them. If no patient is ill, return None.

The setup provides screening(n, seed, rate=0.1), which returns (scores, truth) for n random patients with scores rounded to three decimals.

Examples

Input:  scores = [0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3], truth = [1, 0, 1, 1, 0, 1, 0]
        min_recall = 0.75
Output: (0.6, 0.75, 0.75)
Explanation: with t = 0.6 four patients are sent, three of them ill (precision 3/4), and 3 of the
4 ill patients are found (recall 3/4). t = 0.5 and t = 0.4 also reach the recall, with precision
3/5 and 4/6; higher thresholds find at most 2 of the 4.

Input:  the same scores and truth, min_recall = 1.0
Output: (0.4, 0.6666666666666666, 1.0)

Constraints

  • 1 <= len(scores) == len(truth) <= 10**5, 0 <= min_recall <= 1
  • scores may repeat; all patients with the same score are sent or not sent together
  • compare recalls as tp >= min_recall * ill or with a margin of 1e-9; floats are compared with a tolerance of 1e-6
  • each test must finish in well under a second in your browser

Goals

  • Turn classifier scores into decisions with a threshold
  • See how moving the threshold trades precision against recall
  • Find the most precise threshold that reaches a required recall with one sorted sweep
Starting Python…