- Question 1
Given an array arr of n integers, choose any two of the first three elements of the array and remove them. The cost of such an operation is the maximum of the two elements removed. For example, in the array [1, 2, 3, 4, 5], (1, 3) can be removed at a cost of 3, (1, 2) can be removed at a cost of 2 but (2, 4) cannot be removed as 4 is not amongst the first three elements of the array.
If there are less than three elements left in the array, remove all of them at a cost of the maximum of the remaining values.
Find the minimum cost to remove all the elements from the array.
Example
Suppose n = 4, arr = [3, 1, 4, 2].
Among the possible options for the first step, i.e. {(3, 1), (1, 4), (3, 4)}, it is optimal to remove (3, 4) at a cost of 4. The remaining array in that case would be [1, 2]. You can now remove both the elements at a cost of 2. Thus the total cost to remove all the elements from the array is 6.
Removing any other combination in the first step, i.e. either of (3, 1) and (1, 4), would lead to a higher overall cost. For example, removing (3, 1) in the first step at a cost of 3 would entail removing (4, 2) in the next step at a cost of 2, leading to an overall cost of 7.
Function Description
Complete the function getMinCost in the editor below.
getMinCost has the following parameter:
- int arr[n]: an array of integers
Returns
- int: the minimum cost to remove all the elements from the array
Constraints
- 1 ≤ n ≤ 10^3
- 1 ≤ arr[i] ≤ 10^6
- Question 2
Given a tree of g_nodes nodes rooted at 0, each node has a value given in array A. There is also a parameter, K.
An unweighted undirected tree is represented with g_nodes nodes numbered from 0 to g_nodes - 1 and g_edges = g_nodes - 1 edges where the i-th edge connects the nodes numbered g_from[i] to g_to[i]. Each node numbered u is associated with a value represented by A[u].
Collect all of the values at the nodes using one of two methods:
- Collect A[u] - K points.
- Collect floor(A[u]/2) points. If this method is chosen, all values of node u in this node's subtree are changed to floor(A[u]/2) as well.
You can only collect the value at a node if its parent's value has been collected before (except the root). You have to maximize the total points collected.
Note: It is possible that the accumulated value may be negative at some point.
Example
g_nodes = 4
g_edges = 3
g_from = [0, 1, 2]
g_to = [1, 2, 3]
A = [10, 10, 3, 3]
K = 5
Function Description
Complete the function treePoints in the editor below.
treePoints has the following parameters:
- int g_nodes: the number of nodes in the graph
- int g_from[g_nodes - 1]: one end of each edge
- int g_to[g_nodes - 1]: the other end of each edge
- int A[g_nodes]: the values at the nodes
- int K: the cost to collect a full value
Returns
- long: the maximum sum of values that can be collected
Constraints
- 1 ≤ g_nodes ≤ 10^5
- g_edges = g_nodes - 1
- 0 ≤ g_from[i], g_to[i] < g_nodes
- g_from[i] ≠ g_to[i]
- 1 ≤ A[i] ≤ 10^9
- 1 ≤ K ≤ 10^9
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
