PROBLEM LINK:
Author: Arvind
Tester: Chitturi Sai Suman
Editorialist: Muneeb Hussaini
DIFFICULTY:
Easy
PREREQUISITES:
Comparator based Sorting
PROBLEM:
Arvind loves playing with Numbers. He has a sequence [A_1,A_2,\dots,A_N] of N integers. He wants to reduce the length of the sequence to 1. To do that, he performs exactly Nā1 moves, where a move is defined as follows.
- Pick two Integers A_i and A_j, i \ne j, remove them from the sequence and append the result obtained by concatenating the Integers to the sequence.
He wonders what could be the Largest Integer he can obtain at the end. Can you help him in finding it?
QUICK EXPLANATION:
The problem can be easily solved by sorting the elements of the array based on a Comparator. Refer to the explanation for Comparator based Sorting.
Note: Since the numbers are very large (10^{10^3}), we read them into strings.
EXPLANATION:
Given an array A containing N integers, we need to output the largest number that can be obtained by concatenating these N integers.
This problem can be solved using Greedy Approach. Consider the array of Integers [a_1, a_2, a_3, \dots, a_n]. We sort the sequence by comparing two elements at a time.
Say (S_1,\ S_2) belong to the sequence. The two possible ways of ordering them are:
- (S_1,\ S_2) => (S_1 comes before S_2) after rearranging.
- (S_2,\ S_1) => (S_2 comes before S_1) after rearranging.
Which ordering is optimal?
We can decide this by comparing them the following way:
If (S_1 + S_2) \gt (S_2 + S_1), then the ordering shall be (S_1,\ S_2). Otherwise, the ordering shall be (S_2,\ S_1).
We can prove that the ordering of elements in this way will always produce the largest Number.
SOLUTIONS:
Setter's Solution
def largest(x) :
x = [str(i) for i in x]
for i in range(len(x)):
for j in range(i + 1, len(x)):
if (x[i] + x[j] < x[j] + x[i]):
x[i], x[j] = x[j], x[i]
return ("".join(x))
lis=[]
for i in range((int(input()))):
n=int(input())
x=[int(x) for x in input().split()]
lis.append(largest(x))
for i in range(len(lis)):
print(int(lis[i]))
Tester's Solution
"""
Author: Chitturi Sai Suman
Created: 2021-05-17 19:26:35
Contest: Code with VCE
"""
## 57:69:74:68:20:4C:4F:56:45
## _____ _ _ __ __ ____ __ _
## / ____| | | | | | \ / | / \ | \ | |
## | |___ | | | | | \/ | / _ \ | . \ | |
## \____ \ | | | | | |\__/| | | /_\ | | |\ \| |
## ____| | | \__/ | | | | | | __ | | | \ ` |
## |_____/ \______/ |_| |_| |__| |__| |_| \__|
##
from functools import cmp_to_key, reduce
from fractions import Fraction
from statistics import mean, median, mode
from collections import deque, OrderedDict, defaultdict
from re import compile, findall, escape, search, match
from sys import stdin, stdout, stderr, setrecursionlimit
from math import pi, sqrt, gcd, ceil, floor, log2, log10, factorial
from random import choice, getrandbits, randint, random, randrange, shuffle
from itertools import combinations, combinations_with_replacement, permutations
from collections import Counter, namedtuple, ChainMap, UserDict, UserList, UserString
from math import cos, acos, tan, atan, atan2, sin, asin, radians, degrees, hypot
from bisect import insort, insort_left, insort_right, bisect_left, bisect_right, bisect
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge, nlargest, nsmallest
# from numpy import dot, trace, argmax, argmin, array, cumprod, cumsum, matmul
size = 2 * (10 ** 6 + 1)
# Scope for Global Variables
#
#
class String:
def __init__(self, string: str):
self.string = string
def __str__(self):
return self.string
# def __cmp__(self, other):
# a = self.string + other.string
# b = other.string + self.string
# a = a + "0" * (max(len(a), len(b)) - len(a))
# b = b + "0" * (max(len(a), len(b)) - len(b))
# return int(a) < int(b)
def __lt__(self, other):
a = self.string + other.string
b = other.string + self.string
a = a + "0" * (max(len(a), len(b)) - len(a))
b = b + "0" * (max(len(a), len(b)) - len(b))
return int(a) > int(b)
def preCompute():
# Precompute some values here
#
pass
def solve():
# Solve Test Cases here
#
N = io.Int()
if N not in range(1, 201):
abort("Invalid value of N")
l = list(map(String, io.String().split()))
for i in l:
if int(str(i)) not in range(1, 10**(10**3) + 1):
abort("Invalid Range of Array Elements")
l.sort()
io.write(''.join([str(i) for i in l]))
def main():
testcases = 0
# testcases += 1
if testcases == 0:
testcases = io.Int()
if testcases not in range(1, 10**3 + 1):
abort("Invalid Test Cases")
preCompute()
for test in range(testcases):
# io.write("Case #%d: "%(test+1), end="")
# Use the following lines to write any logic if needed
#
#
solve()
class IO:
def input(self):
return stdin.readline().strip()
def String(self):
return self.input()
def StringList(self):
return list(map(str, self.input().split()))
def Int(self):
return int(self.input())
def Float(self):
return float(self.input())
def List(self):
return list(map(int, self.input().split()))
def Tuple(self):
return tuple(map(int, self.input().split()))
def debug(self, *obj, sep = " ", end = "\n"):
string = sep.join([str(item) for item in obj]) + end
stderr.write(string)
def write(self, *obj, sep = " ", end = '\n'):
string = sep.join([str(item) for item in obj]) + end
stdout.write(string)
def put(self, val: str):
stdout.write(val + '\n')
def yes(self):
self.write("yes")
def Yes(self):
self.write("Yes")
def YES(self):
self.write("YES")
def no(self):
self.write("no")
def No(self):
self.write("No")
def NO(self):
self.write("NO")
io = IO()
shit = 998244353
mod = 10 ** 9 + 7
hell = 10 ** 9 + 9
inf = 10 ** 18 + 3
lcm = lambda x, y: ((x * y) // gcd(x, y))
add = lambda x, y, p: (x % p + y % p + p) % p
sub = lambda x, y, p: ((x % p - y % p) + p) % p
mul = lambda x, y, p: ((x % p) * (y % p)) % p
inverse = lambda x, p: (pow(x, p - 2, p))
setBitCount = lambda x: bin(x).count("1")
sumOfDigits = lambda x: sum([int(i) for i in str(x)])
dc = [1, 0, 0, -1, -1, -1, 1, 1]
dr = [0, 1, -1, 0, -1, 1, -1, 1]
def abort(s):
raise AssertionError(s)
setrecursionlimit(size)
main()