Predatory banks take the debits to an account that occur over the day and reorder them to maximize the fees they can charge. For each debit that results in taking an account into overdraft (having negative balance in the account) or where the account is already in overdraft, the bank charges the customer an overdraft fee: 10% of the debited amount. For example, if the sequence of debits D is $3, $4, $5 and the initial account balance B = $8, the optimal order (for the bank) is: $4, $5, $3 with overdraft fees: 0.1 * ($5 + $3) = S0.80. Assume that the debit amounts D = [d_1, ..., d_n] and initial balance B are in whole dollars (so $4 is ok, but $4.1 is not). Suppose we have an array A = [a_1, ..., a_n] containing positive integers. For some value k, we want to know if A contains a subset of elements that sums to exactly k. An example of an instance for SUBSET SUM: A = [3, 7, 13, 19, 29, 37] and k = 55. This is a YES-instance, since 55 = 7 + 19+ 29. Another example: the same A with k = 54, which is a NO-instance (feel free to try ail 64 combinations). Note that SUBSET SUM is NP-complete. Knowing only that the largest debit in D is d_max and the sum of all debits is d_sum > B, give a (non-asymptotic) upper-bound on the overdraft fees the bank could collect. Answer this question in terms of d_max, d_sum and B without knowing anything else about the debit amounts. The bank will collect fees for the debits that already in the overdraft, so in order to maximize profit they would want to have the largest debit amount putting the account in overdraft in such a way that the most of this debit is paid by the available balance and only a tiny bit is covered by borrowed money, as this way the bank could charge 10% on the largest amount that is technically still covered by the balance. The smallest tiny bit is $1 (since we assume debits and the initial balance are integers), so let's assume that the sum of debits processed up to d_max (including d_max) is B + 1. Hence, the overdraft fee 10% is collected from d_max and the subsequent debits, which sum up to 0.1 * (d_max + d_sum - (B + 1)). After hearing about the possibility of collecting the amount of fees described in the previous part, the CEO of Greedy Banks Consortium wants to find out for which collections of debits D and initial balances D (both containing only integer values) it's possible to charge this maximal fee 0.1 * {d_max + d_sum - (B + 1)), where d_max is the largest and d_sum is the sum of all debits in D. Let's call this problem the GREEDY CEO problem. So, the answer to an instance of this problem is "YES" if it is possible to achieve this upper-bound on fees, and the answer is "NO", otherwise. An example of a YES-instance (with D = 2, 3, 3, 4, 6 and B = 10) is illustrated in the following diagram in which rectangles represents different debits (the number of boxes in the rectangle shows the amount of debit), shaded rectangles are debits in overdraft and the vertical line show the initial account balance: An example of a NO-instance is the following: D = 1, 3, 4 and B = 5. Here, if we "place" d_max = 4 to right position (just $1 over the balance B), it creates two gaps, one before and one after d_max, of size 2, which we cannot "fill" with debits $1 and S3 (as we are not allowed to break debits into smaller pieces). You were tasked to write an efficient (polynomial) algorithm for the GREEDY CEO problem. You suspect that such an algorithm might not exist, so you want to prove to your boss that the problem cannot be solved by any efficient algorithm (assuming P notequalto NP). You came up with the following reduction from the SUBSET SUM problem to the GREEDY CEO problem: Reduction: Let a_1, ..., a_n, k be an instance of the SUBSET SUM problem. Let a_max = max{a_1, ..., a_n}. In order to achieve this maximum overdraft fee, we have to "pack" a subset of debits just before d_max. That means they would have to sum up to B + 1 - d_max. Let's construct an instance of the GREEDY CEO problem from the instance of the SUBSET SUM problem by using numbers in A as the debit amounts (so D = A) and setting B = k + a_max - 1. Explain why this reduction is incorrect! Your explanation must include a simple counterexample to the correctness of the reduction. Predatory banks take the debits to an account that occur over the day and reorder them to maximize the fees they can charge. For each debit that results in taking an account into overdraft (having negative balance in the account) or where the account is already in overdraft, the bank charges the customer an overdraft fee: 10% of the debited amount. For example, if the sequence of debits D is $3, $4, $5 and the initial account balance B = $8, the optimal order (for the bank) is: $4, $5, $3 with overdraft fees: 0.1 * ($5 + $3) = S0.80. Assume that the debit amounts D = [d_1, ..., d_n] and initial balance B are in whole dollars (so $4 is ok, but $4.1 is not). Suppose we have an array A = [a_1, ..., a_n] containing positive integers. For some value k, we want to know if A contains a subset of elements that sums to exactly k. An example of an instance for SUBSET SUM: A = [3, 7, 13, 19, 29, 37] and k = 55. This is a YES-instance, since 55 = 7 + 19+ 29. Another example: the same A with k = 54, which is a NO-instance (feel free to try ail 64 combinations). Note that SUBSET SUM is NP-complete. Knowing only that the largest debit in D is d_max and the sum of all debits is d_sum > B, give a (non-asymptotic) upper-bound on the overdraft fees the bank could collect. Answer this question in terms of d_max, d_sum and B without knowing anything else about the debit amounts. The bank will collect fees for the debits that already in the overdraft, so in order to maximize profit they would want to have the largest debit amount putting the account in overdraft in such a way that the most of this debit is paid by the available balance and only a tiny bit is covered by borrowed money, as this way the bank could charge 10% on the largest amount that is technically still covered by the balance. The smallest tiny bit is $1 (since we assume debits and the initial balance are integers), so let's assume that the sum of debits processed up to d_max (including d_max) is B + 1. Hence, the overdraft fee 10% is collected from d_max and the subsequent debits, which sum up to 0.1 * (d_max + d_sum - (B + 1)). After hearing about the possibility of collecting the amount of fees described in the previous part, the CEO of Greedy Banks Consortium wants to find out for which collections of debits D and initial balances D (both containing only integer values) it's possible to charge this maximal fee 0.1 * {d_max + d_sum - (B + 1)), where d_max is the largest and d_sum is the sum of all debits in D. Let's call this problem the GREEDY CEO problem. So, the answer to an instance of this problem is "YES" if it is possible to achieve this upper-bound on fees, and the answer is "NO", otherwise. An example of a YES-instance (with D = 2, 3, 3, 4, 6 and B = 10) is illustrated in the following diagram in which rectangles represents different debits (the number of boxes in the rectangle shows the amount of debit), shaded rectangles are debits in overdraft and the vertical line show the initial account balance: An example of a NO-instance is the following: D = 1, 3, 4 and B = 5. Here, if we "place" d_max = 4 to right position (just $1 over the balance B), it creates two gaps, one before and one after d_max, of size 2, which we cannot "fill" with debits $1 and S3 (as we are not allowed to break debits into smaller pieces). You were tasked to write an efficient (polynomial) algorithm for the GREEDY CEO problem. You suspect that such an algorithm might not exist, so you want to prove to your boss that the problem cannot be solved by any efficient algorithm (assuming P notequalto NP). You came up with the following reduction from the SUBSET SUM problem to the GREEDY CEO problem: Reduction: Let a_1, ..., a_n, k be an instance of the SUBSET SUM problem. Let a_max = max{a_1, ..., a_n}. In order to achieve this maximum overdraft fee, we have to "pack" a subset of debits just before d_max. That means they would have to sum up to B + 1 - d_max. Let's construct an instance of the GREEDY CEO problem from the instance of the SUBSET SUM problem by using numbers in A as the debit amounts (so D = A) and setting B = k + a_max - 1. Explain why this reduction is incorrect! Your explanation must include a simple counterexample to the correctness of the reduction