Problem: two_apples_a_day (2023 practice)

“An apple a day keeps the doctor away” is Steve’s motto. His other motto, “You can never have too much of a good thing,” holds true for both apples and mottos. Steve would like to eat two apples per day for the next \(N\) days, but with strict adherence to his third motto “Consistency is key.” Specifically, he’d like the sum of the two apple weights he eats over the next \(N\) days to be the same for each day.

Steve has already purchased \(2*N-1\) apples, the \(i\)th of which weighs \(A_i\) ounces. He'd like to buy one more apple that's as light as possible to fulfill his goal. Steve can buy an apple of any positive integer weight in ounces from the store. Is it possible for him to reach his goal, and if so, what weight apple should he buy?

{{PHOTO_ID:1563872647765708|WIDTH:600}}


*The above image depicts the solution to the first sample. Each day, Steve will eat two apples totalling \(7\) oz. Steve must buy a \(4\) oz apple to make this happen.*

# Constraints
\(1 \leq T \leq 70\)
\(1 \leq N \leq 3*10^5\)
The sum of \(N\) over all cases is at most \(600{,}000\)
\(1 \leq A_i \leq  10^9\)

# Input Format
Input begins with an integer \(T\), the number of test cases. Each test case starts with a single integer \(N\). The next line contains \(2*N-1\) space-separated integers \(A_1, ..., A_{2*N - 1}\).

# Output Format
For the \(i\)th test case, print "`Case #i:` " followed a single integer, the smallest possible apple weight in ounces that Steve can buy so that he can eat two apples for the next \(N\) days and have the sum of apple weights be the same every day, or \(-1\) if doing so is impossible.

# Sample Explanation

In the first case, if Steve buys a \(4\) oz apple, he can group his apples as shown above. For this input, there's no way to succeed by buying any apple below \(4\) oz.

In the second case, Steve can buy a \(7\) oz apple, and eat two apples totaling \(14\) oz each day.

In the third case, any apple weight will suffice, so Steve will buy the lightest one possible.

In the fourth case, no matter what weight apple Steve attempts to buy, it is impossible for him to achieve his goal.

Please note, as demonstrated in the seventh case, that it's possible for the answer to exceed \(10^9\).




Sample input:
7
3
6 3 1 2 5
2
7 7 7
1
1
3
1 9 1 1 4
4
1 9 1 1 4 9 9
4
1 9 10 1 4 6 9
3
1000000000 2 10 4 999999994


Sample output:
Case #1: 4
Case #2: 7
Case #3: 1
Case #4: -1
Case #5: 6
Case #6: -1
Case #7: 1000000002


Solution: If there's only one element, we don't care what it is, a \(1\) will match it. 

Otherwise, let's solve this backwards: instead of attempting to add a number in, we'll consider starting with a working solution and removing some number from it. Let's denote the daily sum of apple weights as \(K\). We can imagine having a sorted array of \(2*N\) elements where the first and last elements sum to \(K\), the second and second last sum \(K\), etc.

Now, consider removing one element from the \(2*N\) sorted numbers. There are three cases:

1. We removed the first element. Then, \(K\) is the new first element plus the second last element.
2. We removed the last element. Then, \(K\) is the new last element plus the second element.
3. We removed some element in the middle. Then, \(K\) is the sum of the first and last elements.

With \(3\) candidates for \(K\), we'll pick the smallest that works. To check if a \(K\) works, we can use two pointers \(l\) and \(r\) moving from the outside inwards on the sorted input array. If the left and right values sum less than \(K\), we record a "skip" (noting the element that would've been removed) and increment \(l\). If it sums more, we decrement \(r\), else we advance both closer. In the end, \(K\) works if there is at most a single skip (and that removed element is positive).

Running two pointers to check one candidate \(K\) takes \(\mathcal{O}(N)\) time, so the overall running time on \(3\) candidates is still \(\mathcal{O}(N)\).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int INF = (int)1e9 + 5;

int N, sz;
vector<int> a;

int try_sum(int sum) {
  int skipped = 0;
  int l = 0, r = sz - 1;
  int res = sum / 2;
  while (l <= r) {
    if (a[l] + a[r] == sum) {
      l++;
      r--;
      continue;
    }
    skipped++;
    if (a[l] + a[r] < sum) {
      res = sum - a[l++];
    } else {
      res = sum - a[r--];
    }
  }
  return (skipped <= 1 && res > 0) ? res : INF;
}

int solve() {
  cin >> N;
  sz = 2*N - 1;
  a.resize(sz);
  for (int i = 0; i < sz; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int ans = min({
    try_sum(a[1] + a[sz - 1]), // remove first
    try_sum(a[0] + a[sz - 1]), // remove middle
    try_sum(a[0] + a[sz - 2])  // remove last
  });
  return ans == INF ? -1 : ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}