TopCoder problem "DigitsSwap" used in SRM 436 (Division II Level Three)



Problem Statement

    You are given two positive integers, x and y, whose decimal representations contain the same number of digits. A digit-swap operation for an index i swaps the digits at the i-th positions in x and y. After exactly swaps digit-swap operations, what is the maximal possible value of x*y? Return the String representation of this maximal product with no leading zeroes.
 

Definition

    
Class:DigitsSwap
Method:maximalProduct
Parameters:String, String, int
Returns:String
Method signature:String maximalProduct(String x, String y, int swaps)
(be sure your method is public)
    
 

Constraints

-x and y will each contain between 1 and 50 characters, inclusive.

-x and y will contain only decimal digits ('0' to '9'), and will not start with a '0'.

-x and y will contain the same number of characters.

-swaps will be between 0 and 1,000,000,000, inclusive.

 

Examples

0)
    
"123"
"321"
2
Returns: "39483"
You can transform the numbers to "123", "321" (making two swaps at the same position) or to "321", "123" (making swaps at positions 0 and 2) to produce the product 39483.
1)
    
"4531"
"1332"
0
Returns: "6035292"
You are not allowed to make swaps, so the answer is just x * y.
2)
    
"13425"
"87694"
99
Returns: "1476187680"
The optimal answer is 17695 * 83424.
3)
    
"2872876342876443222"
"2309482482304823423"
5
Returns: "6669566046086333877050194232995188906"
4)
    
"940948"
"124551"
4893846
Returns: "133434353148"
5)
    
"56710852"
"18058360"
1
Returns: "1050671725722720"
6)
    
"9"
"1"
1000000000
Returns: "9"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10342

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13698&pm=10342

Writer:

Gluk

Testers:

PabloGilberto , ivan_metelsky , ged , zhuzeyuan

Problem categories:

Simple Math, Simple Search, Iteration