Maximum number of pairwise decrements in three numbers

Question

Given are the 3 non-negative integers a,b,c

In a single operation, we have to subtract 1 from two integers only if they don't become negative.

We have to find the maximum no of operations possible than we can do until the given operation is not possible.

constraints:1<=a,b,c<=10^18 , 1<=test-cases<=10^5

Examples:
(1,2,3) -> (1,1,2) -> (1,0,1) -> (0,0,0) , answer is 3
(1,1,8) -> (1,0,7) -> (0,0,6) , answer is 2

Any approach or proof will be highly helpful.

I have actually written a code that's working as far as I know, but I don't know if it's completely true.

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long 

int main(){
   fastio;
   int t; cin>>t;
   while(t--){
      LL a[3]; cin>>a[0]>>a[1]>>a[2];
      sort(a,a+3);
      if(a[0]+a[1]>=a[2]){
         LL ans = a[2] + (a[0]+a[1]-a[2])/2;
         cout<<ans;
      }
      else {
         LL ans = a[1] + min(a[0],a[2]-a[1]);
         cout<<ans;
      }
      cout<<"\n";
   }
}

UPDATE: it turns out my solution is correct, here is the exact same problem,and editorial

Answer 1

It took me three tries to get this right. Mistaking this problem as a dynamic programming problem was the downward spiral

The trick is to recognize that it can be solved in a loop where you continually sort a,b,c from smallest and to largest. Then evaluate which pattern the numbers fit under. Patterns to look for include:

• 1 or fewer positive values in the set: a=0, b=0, c=5
• 2 positive values and a zero in the set: a=0, b=3, c=10
• 3 positive values, all different: a=5, b=11, c=88
• 3 positive values, all the same: a=10, b=10, c=10
• 3 positive values, the smallest two are equal: a=5, b=5, c=22
• 3 positive values, the largest two are equal: a=3, b=5, c=5

After you figure out which pattern a,b,c falls into with the above list, there are specific express reductions that can be made. Many of which will allow you to break out of the loop without needing to further reduce the set. And I think the following code works out so that it only iterates through loop at most 2 (or 3) times. Hence, this is an O(1) solution.

#include <iostream>
#include <algorithm>

using namespace std;

long long maxDeductions(long long a, long long b, long long c)
{
    long long total = 0;  // this is the running count of "deduction" steps made so far

    while (true)
    {
        long long deduction = 0;  // scratch variable for math

        // sort a,b,c into ascending order
        long long sorttable[3] = { a,b,c };
        sort(sorttable, sorttable + 3);
        a = sorttable[0];  // smallest
        b = sorttable[1];  // middle
        c = sorttable[2];  // largest

        // count the number of positive values among a,b,c    
        int positives = 0;
        positives += (a > 0);
        positives += (b > 0);
        positives += (c > 0);

        if (positives <= 1)
        {
            // Nothing left to do, we can break out of the loop
            break;
        }
        else if (positives == 2)
        {
            // When there are only two positives left
            // The number of deductions that can be express computed.
            // as the smaller of the remaining positive values, that is: b
            //
            // ASSERT: (b <= c) && (b > 0) && (c > 0)
            deduction = b;
            total += deduction;
            break;
        }
        else // three positives
        {
            if ((a != b) && (b != c))    // 3 positives, all different
            {
                // reduce the two larger values, b and c,  by the delta between b and a
                // this "b-a" amount is the number of deductions computed to  get the set a,b,c to have 
                // at least 2 identical numbers for the next set
                deduction = b - a;
                b = a;
                c -= deduction;
                total += deduction;
            }
            else if ((a == b) && (b == c)) // 3 positives, all the same
            {
                // when you have 3 identical values: N,N,N
                // It takes three steps to get to N-2,N-2,N-2
                // With a subtle tweak for odd vs even values of N, simple math can be used to 
                // deduce the remaining number of deductions

                if (a % 2) // odd
                {
                    deduction = ((a - 1) / 2) * 3 + 1;
                }
                else  // even
                {
                    deduction = (a / 2) * 3;
                }
                total += deduction;
                break;
            }
            else if (c == b)   // 3 positives, largest two are the same, equivalent to all different
            {
                deduction = b - a;
                b = a;
                c -= deduction;
                total += deduction;
            }
            else if (a == b)   // 3 positives, smallest two are the same
            {
                // this is the tricker one, but you can quickly see the pattern:
                // NNZ reduces in N*2 steps.  Example for N=5
                // 559 -> 548 -> 448 ->  437 -> 337 -> 326 -> 226 -> 215 -> 115 -> 104 -> 003
                // You can see every two reductions steps gets N,N,Z reduced to N-1,N-1,Z-1
                // Hence, exactly N*2 steps remaining
                total += (a * 2);
                break;
            }
        }

    }
    return total;
};

Answer 2

Isn't it just:

Sort the numbers

1 2 3

total 0

Subtract the first (and add to total) such that the second becomes as close as possible, while smaller than or equal to, the third

0 2 2

total 1

Subtract the second and add to total

0 0 0

total 3

?

2 2 2
0

0 1 1
2

0 0 0
3

function f(arr){
  arr.sort((a, b) => a - b);
  
  let [a, b, c] = arr;
  const max_from_c = c - b;
  
  if (max_from_c >= a)
    return a + b;

  let total = max_from_c;
  
  a = a - max_from_c;
  c = c - max_from_c;
  const smaller_half = Math.floor(a / 2);
  const larger_half = a < 2 ? a : Math.ceil(a / 2);
  c = c - larger_half;
  total = total + larger_half;
  b = b - smaller_half;
  total = total + smaller_half;

  return total + Math.min(b, c);
}

var arrays = [
  [1,2,3], // 3
  [1,1,8], // 2
  [3,4,5], // 6
  [1,1,1], // 1
  [1,1,2], // 2
  [2,1,2], // 2
  [2,2,2], // 3
  [3,3,2], // 4
  [10000,10000,10000] // 15000
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
  console.log('');
}