C++

 100 Minutes
 1 Questions



Example Question:

Coding
Task: Art Editorials

Description:

The annual Art Showcase is approaching, and Marion and Petra have been chosen as the curators. However, they face a time constraint, as they must complete the exhibition setup before the grand opening.

The showcase consists of n unique art installations, numbered from 1 to n. Each art installation requires a[i] minutes to set up. Marion and Petra need to conduct an editorial for exactly k of these art installations.

The editorial process is as follows: They have a complete collection of n art installations arranged in a specific order. They must remove n-k art installations without changing the order of the remaining k installations. Afterward, Marion selects a portion of these k installations, which can be an empty selection or all of the installations in the chosen set. Meanwhile, Petra takes the remaining installations. They then move to separate rooms and conduct their editorials in parallel. The duration of the editorial is determined by the longer time taken by either Marion or Petra.

Marion and Petra seek your assistance in choosing the art installations and the split in a way that ensures the editorial process finishes as quickly as possible. Your task is to determine the duration of the editorial.

The function should return the optimal time required for the editorial.

Example:

n = 5 (total number of art installations)
a = [4, 2, 7, 5, 1] (time taken for each installation)
k = 3 (number of installations to conduct the editorial for)

In this case, Marion and Petra need to select and conduct the editorial for exactly 3 installations out of the 5 available. The order of the installations is important.

To minimise the duration of the editorial, they need to select the installations with the shortest durations. One possible solution could be:

Marion selects the first problem (problem 1), which takes 4 minutes.
Petra selects the second and last problems (problems 2 and 5), which take 2 and 1 minutes, respectively.

In this scenario, Marion's editorial takes 4 minutes, while Petra's editorial takes 1 minute. Since the duration of the editorial is determined by the longer time taken by either of them, the overall duration of the editorial would be 4 minutes.

Therefore, the function should return 4.