SWPDGT - Editorial (Unofficial)

Lately, there has been a lot of video solutions coming out. I thought of writing a solution in the old format. There is already a video solution for this. You may check that out too.

PROBLEM LINK:

Div2
Practice

Setter - Farhan Hasin

DIFFICULTY:

Easy

PROBLEM:

Given two numbers A and B, maximize their sum. We are allowed to swap a digit in A with a digit in B at most once.

EXPLANATION:

Here, both A and B are in the range [1, 99]. So, they are either single or double digit.

The solution to the problem involves finding whether we want to do the swap. If yes, what is the correct swap so that it maximizes the sum.

In order to find the correct swap let’s first see -

  • what an effective swap is; and
  • what is the effect of the swap on the Sum = A + B.

Lets represent A and B in their decimal representation.
A = a_{1}a_{2}
B = b_{1}b_{2}
Here, if either A or B < 10 then, a_{1} or b_{1} = 0 respectively.

A swap is considered effective only if it is between digits of different decimal places i.e., if we swap a_{1} with b_{2} or a_{2} with b_{1} otherwise, the effect is 0.
For example, say we swap a_{2} and b_{2} or a_{1} and b_{1} then, the change in Sum is 0.

So, the swap will be between a ones-digit and a tens-digit of the two numbers.

Now that we know, what an effective swap is. Let’s see what is the effect of the swap on the sum.

Let Sum_{original} = A + B
Say we swap a_{2} and b_{1}. Then,

Sum_{new} = A + B + 10*(a_{2} - b_{1}) + (b_{1} - a_{2}) = A + B + 9*(a_{2} - b_{1})

Which can be generalized to,

Sum_{new} = A + B + 9*(d_{1s} - d_{10s}) where,

d_{1s} = ones-digit of one number and
d_{10s} = tens-digit of the other number.

Inorder to maximize the Sum we need to maximise diff = d_{1s} - d_{10s}.

Lets find all the pairs (d_{1s}, d_{10s}) for A and B. As mentioned before since A, B \in [1, 99]. There can be 0 to 2 valid pairs.

0 when both A, B < 10 and
2 when both A, B \geq 10.

So, the pairs are (b_{2}, a_{1}) and (a_{2}, b_{1}).

A pair is considered invalid if d_{10s} == 0 (i.e the relevent number is < 10) then its corresponding diff is 0 because the swap itself is invalid.

diff_{1} = b_{2} - a_{1} or 0 if a_{1} = 0 \Rightarrow A < 10
diff_{2} = a_{2} - b_{1} or 0 if b_{1} = 0 \Rightarrow B < 10

So, Sum_{max} = A + B + 9*max(0, diff_{1}, diff_{2}). Here, 0 represents no-swap scenario.

SOLUTION

Code (Python)
for t in range(int(input().strip())):
   a, b = tuple(map(int, input().strip().split()))
   diff1 = 0 if b < 10 else (a % 10 - b // 10)
   diff2 = 0 if a < 10 else (b % 10 - a // 10)
   res = a + b + 9 * max(0, diff1, diff2)
   print(res)

Time Complexity = O(1)
Space Complexity = O(1)

5 Likes

Actually it is an overkill for a simple cakewalk problem. As given range is too small you can always brute-force the answer with two nested loops, by treating both the numbers as string (of at most 2 characters).

My submission

2 Likes

Yup we can do that too. But i was too lazy to write too much code. The explanation is the overkill otherwise its very straight forward. And I was itching to write my first editorial (what else to do when you are in a lockdown :stuck_out_tongue: ).

can someone tell what is wrong in this code,all test cases in question are giving correct ans still not able to submit??

#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int x,y;
	    cin>>x;
	    cin>>y;
	    int temp=max(x,y);
	     y=min(x,y);
	    int b1= y /10;
	    int b2=y% 10;
	  
	     x=temp;
	    int a1=x/10;
	    int a2=x%10;
	    
	    int ans;
	    if(x < 10)
	       ans=x + y;
	    else if(y < 10){
	        ans= max(b2,a1)*10 + min(b2,a1)+a2;
	    }
	    else{
	        ans= max(a1,b2)*10+min(a1,b2)+ max(b1,a2)*10 +min(b1,a2);
	    }
	    cout<<ans<<endl;
	    
	}
	return 0;
}

In the else block your code will end up doing 2 swaps which is not allowed. For example, take
28 and 39. Your solution will make 2 swaps, resulting with 93 and 82 which is wrong.

But the correct swap results in 98 and 32. Sum = 130.

ok i got it ,thanks alot

whats the problem in this code although its passing test cases…?
#include
#include
using namespace std;

int main() {
// your code goes here
int t;
cin >> t;
while(t)
{
int a=0,b=0,c=0,d=0,n1,n2;
cin >> n1 >> n2;

    b = n1%10;
    n1 = n1/10;
    a = n1 %10;
    d = n2%10;
    n2 = n2/10;
    c = n2 %10;
    int ar[4];
    ar[0] = n1 + n2;
    ar[1] = ((a*10)+d)+((c*10)+b);
    ar[2] = ((a*10)+c)+((b*10)+d);
    ar[3] = ((c*10)+b)+((a*10)+d);
    ar[4] = ((d*10)+b)+((c*10)+a);
    int *p = max_element(ar,ar+5);
  //  cout << a << b << c << d << endl;
  //  cout << ar[0] << endl << ar[1] <<endl<< ar[2]<<endl << ar[3] << endl << ar[4] << endl << ar[5] << endl;
    cout  << *p << endl;
    t--;
}
return 0;

}