the-legend-of-tanmay

Tanmay is a legendary spammer - everyone in the spamming world knows and admires his abilities to spam anyone, anytime, anywhere. He decided to guide one of his mentors, named Arjit, as part of the Apex body of spamming. 

Tanmay has no doubts on his skills of teaching and making his mentor, Arjit, learn about the art of spamming. But, he surely has serious doubt on Arjit's skills of learning, implementing and executing whatever he has decided to teach him as part of the syllabus of spamming.

Tanmay has sent Arjit to test his skills, but he's getting extremely anxious about the performance of his mentee. So, to calm himself down he asks you to help him find out the maximum and the minimum productivity attained by Arjit in his travel.

Arjit has the option to visit N Facebook groups - where every Facebook group has some potential which can be negative, zero or positive. Now, he can decide to visit a group if he wants to or not. (Depending on the lessons taught to him by the great master!) The total productivity attained by Arjit is the product of all the groups he decides to visit.

Given the values of all the groups, find out the maximum and minimum spamming potential he can achieve and let Tanmay know about it, so that he calm himself down.

Input format:
The first line contains an integer, T, denoting the number of test cases. Each line of the test case contains an integer, N, denoting the size of the array. The next line contains N integers, denoting the value of the numbers in the array.

Output format:
Print the maximum product you can obtain followed by the minimum product. A space separates both these outputs. Answer to each test case is on a new line.  

Constraints:
1 ≤ T ≤ 500
1 ≤ N ≤ 18
-10 ≤ Ni ≤ 10  

Note:
In some cases only one element may be considered for minimum or maximum product.
If the array is (1, 2, 3), minimum product is 1 whereas maximum product is 6.
When the array is (-1, -2), minimum product is -2 whereas maximum product is 2.

SAMPLE INPUT
2
4
1 0 2 10
3
0 0 0

SAMPLE OUTPUT
20 0
0 0

Explanation

In the first test case, the maximum product is the product of all the numbers except 0, whereas the minimum product is the product of all numbers including 0.
In the second test case, the maximum and minimum product both are 0 as 0 is the only available number.

Difficulty: EASY
Tags: Ad-hoc

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(eval(input())):
	n = eval(input())

	vals = sorted(list(map(int, input().split())))

	mx = vals[-1]
	mn = vals[0]

	neg = sorted(list([x for x in vals if x < 0]))
	pos = sorted(list([x for x in vals if x > 0]))

	v = None
	for x in pos:
		if v == None:
			v = x
		else:
			v *= x
		mx = max(mx, v)
	if len(neg) % 2 == 1:
		neg = neg[:-1]
	for x in neg:
		if v == None:
			v = x
		else:
			v *= x
		mx = max(mx, v)
	if v != None:
		mx = max(mx, v)


	neg = sorted(list([x for x in vals if x < 0]))
	v = None
	for x in pos:
		if v == None:
			v = x
		else:
			v *= x
		mn = min(mn, v)
	if len(neg) % 2 == 0:
		neg = neg[:-1]
	for x in neg:
		if v == None:
			v = x
		else:
			v *= x
		mn = min(mn, v)
	if v != None:
		mn = min(mn, v)

	print(mx, mn)




def prod(xs):
	p = 1
	for x in xs:
		p *= x
	return p

def solve(xs):
	negatives = sorted(x for x in xs if x < 0)
	positives = sorted(x for x in xs if x > 0)
	zeros = [0] if 0 in xs else []
	if len(negatives) % 2 == 0: maxi = negatives + positives
	else: maxi = negatives[:-1] + positives
	if not maxi and zeros : maxi = zeros
	elif not maxi: maxi = negatives[-1:]

	if len(negatives) % 2 == 1: mini = negatives + positives
	elif len(negatives) >= 2: mini = negatives[:-1] + positives
	else: mini = (zeros + positives)[:1]
	return '{} {}'.format(prod(maxi), prod(mini))

if __name__ == '__main__':
	for _ in range(int(input())):
		input()
		print(solve(list(map(int, input().split()))))


t=int(input())
for i in range(0,t):
	n=int(input())
	l=list(map(int,input().split()))
	l=sorted(l)
	m=l.pop()
	s=m
	if m==0:
	    if len(l)>0:
	        while l[-1]==0:
	            l.pop()
	            if len(l)==0:
	                break;
	    if len(l)>1:
	        m=l.pop()
	        s=m
	    elif len(l)==1:
	        s=l.pop()
	if m<0 and len(l)>0:
	    if len(l)%2!=0:
	        s=1
	        for j in range(0,len(l)):
	            k=l.pop()
	            s*=k
	            m*=k
	    else:
	        m=1
	        for j in range(0,len(l)):
	            k=l.pop()
	            s*=k
	            m*=k
	elif m>0 and len(l)>0:
		while l[-1]>0:
			s=l.pop()
			m*=s
			if len(l)==0:
			    break
		if len(l)!=0:
		    while l[-1]==0:
		        l.pop()
		        if len(l)==0:
		        	s=0
		        	break
		    if len(l)>0 and (len(l)%2)==0:
		        s=m
		        m*=l.pop()
	    		while len(l)>0:
	    			k=l.pop()
	    			m*=k
	    			s*=k
	    	if len(l)%2!=0:
	        	s=m
	        	s*=l.pop()
	        	while len(l)>0:
	        		k=l.pop()
	        		m*=k
	        		s*=k
	print(m,s)


x=eval(input())
for _ in range(0,x):
	y=eval(input())
	f=list(map(int,input().split()))
	mi=min(f)
	ma=max(f)
	k=1
	c=0
	gr=mi
	for i in f:
		if i !=0:
			k=k*i
			if i<0:
				c=c+1
				if i>gr:
					gr=i
	if k<mi:
		mi=k
	if gr!=0 and k/gr<0:
		mi=k/gr
	if c%2!=0:
		k=k/gr
	if c==1 and ma==0:
		k=0
	if ma==mi and ma==0:
		k=0


	if len(f)==1:
		print(f[0],f[0])
	else:
		print(k,mi)


from functools import reduce
__author__ = 'Siddharth'

if __name__ == "__main__":

	T = int(input())

	for t in range(T):

		N = int(input())
		F = list(map(int, input().split()))

		PLUS, MINUS = [], []

		zero = 0 in F
		for i in F:
			if i > 0:
				PLUS.append(i)
			elif i < 0:
				MINUS.append(i)

		P, M = len(PLUS), len(MINUS)

		PROD_PLUS = reduce(lambda x, y: x*y, PLUS, 1)
		PROD_MINUS = reduce(lambda x, y: abs(x)*abs(y), MINUS, 1)

		min_value, max_value = 0, 0

		if P > 0:
			if M % 2 == 0:
				max_value = PROD_PLUS*PROD_MINUS
			else:
				max_value = PROD_PLUS*PROD_MINUS/abs(max(MINUS))
		elif M > 1:
			if M % 2 != 0:
				max_value = PROD_MINUS/abs(max(MINUS))
			else:
				max_value = PROD_MINUS
		else:
			if zero:
				max_value = 0
			else:
				max_value = MINUS[0]

		if M > 0:
			if M % 2 != 0:
				min_value = -1*PROD_MINUS*PROD_PLUS
			else:
				min_value = PROD_MINUS*PROD_PLUS/max(MINUS)
		elif zero:
			min_value = 0
		else:
			min_value = min(PLUS)

		print(max_value, min_value)



for t in range(int(eval(input()))):
	n=int(eval(input()))
	l=list(map(int,input().split()))
	l.sort()
	#print n
	#print l
	pc=0
	nc=0
	ze=0
	ps=1
	ns=1
	mx=1
	mn=1
	for x in l:
		if x==0:
			ze+=1
		elif x<0:
			nc+=1
			ns*=x
		else:
			pc+=1
			ps*=x
	#print ze,pc,nc
	#print ps,ns
	if len(l)==1:
		mn=l[0]
		mx=l[0]
	elif ze==len(l):
		mx=0
		mn=0
	elif pc==0 and ze>=1:
		mx=0
		if nc%2==0:
			mx=ps*ns
			for x in range(nc-1):
				#print l[x]
				mn*=l[x]
			mn*=ps
		else:
			mn=ps*ns 
			#print "min"
			for xx in range(nc-1):
				#print "lll",l[xx]
				mx*=l[xx]
			mx*=ps
	elif nc==0:
		mx=ps
		mn=l[0]
	elif nc%2==0:
		mx=ps*ns
		for x in range(nc-1):
			#print l[x]
			mn*=l[x]
		mn*=ps
	else:
		mn=ps*ns 
		#print "min"
		for xx in range(nc-1):
			#print "lll",l[xx]
			mx*=l[xx]
		mx*=ps
	print(mx,mn)
	


for __ in range(eval(input())):
	x = eval(input())
	a = list(map(int, input().split()))
	neg = []
	pos = []
	zero = 0
	for i in a:
		if i<0: neg.append(i)
		elif i==0: zero+=1
		else: pos.append(i)
	neg.sort()
	pos.sort()
	if len(neg)==0 and len(pos)==0:
		mini = 0
		maxi = 0
	elif len(neg)==0:
		maxi = 1
		for i in pos: maxi*=i
		if zero: mini = 0
		else: mini = pos[0]
	else:
		length = len(neg)
		maxi = 1
		mini = 1
		if len(pos)>0:
			for i in pos: maxi*=i
			for i in pos: mini*=i
		elif len(pos)==0:
			if length ==1 and zero>0:
				mini = neg[0]
				maxi = 0
			elif length ==1 and zero==0:
				mini = neg[0]
				maxi = mini
			elif length!=0:
				if length&1:
					for i in range(length-1): maxi*=neg[i]
					for i in range(length): mini*=neg[i]
				else:
					for i in range(length): maxi*=neg[i]
					for i in range(length-1): mini*=neg[i]
			print(maxi, mini)
			continue
		##solving negative part first
		if length&1:
			for i in range(length-1): maxi*=neg[i]
			for i in range(length): mini*=neg[i]
		else:
			for i in range(length): maxi*=neg[i]
			for i in range(length-1): mini*=neg[i]
	print(maxi, mini)
			


test = eval(input())
while test:
	test -= 1
	t = eval(input())
	arr = list(map(int,input().split()))
	arrp = []
	arrn = []
	n = 0
	p = 0
	zero = False

	for i in range(t):
		if arr[i]>0:
			arrp.append(arr[i])
			p += 1
		elif arr[i]<0:
			arrn.append(arr[i])
			n+=1
		else:
			zero = True
	arrn.sort(reverse = True)
	arrp.sort()
	if p==0 and n==0:
		maximum = 0
		minimum = 0
	elif p>0 and n==0:
		if zero:
			minimum = 0
		else:
			minimum = min(arrp)
		maximum = 1
		for i in range(p):
			maximum*=arrp[i]
	elif n>0 and p==0:
		if n%2==0:
			maximum = 1
			for i in range(n):
				maximum*=arrn[i]
			minimum = 1
			for i in range(1,n):
				minimum*=arrn[i]
		else:
			if n==1 and zero:
				maximum = 0
				minimum = arrn[0]
			elif n==1 and zero == False:
				maximum = arrn[0]
				minimum = arrn[0]
			else:
				minimum = 1
				for i in range(n):
					minimum*=arrn[i]
				maximum = 1
				for i in range(1,n):
					maximum*=arrn[i]
	else:
		maximum = 1
		for i in range(p):
			maximum*=arrp[i]
		if n%2==0:
			minimum = maximum
			for i in range(n):
				maximum*=arrn[i]
			for i in range(1,n):
				minimum*=arrn[i]
		else:
			minimum = maximum
			for i in range(1,n):
				maximum*=arrn[i]
			for i in range(n):
				minimum*=arrn[i]
	print(maximum,minimum)
		


import sys
T = int(input())
for k in range(T):
	N = int(input())
	x = [int(y) for y in input().split()]
	x.sort()
	max_z,min_z,max_p,min_p,max_n,min_n=-1000000,1000000,-1000000,1000000,-1000000,1000000
	pos_l,neg_l,zero_l = [],[],[]
	for i in range(N):
		if x[i] > 0:
			pos_l.append(x[i])
		elif x[i] == 0:
			
			zero_l.append(0)        
		else:
			neg_l.append(x[i])

	neg_l.sort(reverse=True)
			
	if len(pos_l) > 0:
		max_p = 1
		for i in pos_l:
			max_p*=i
		min_p = pos_l[0]

	if len(zero_l)>0:
		max_z,min_z = 0,0

	if len(neg_l)>0:
		
		if len(neg_l)>1:
			n = len(neg_l)
			if n%2 == 0:
				max_n=1
				min_n=1
				for i in neg_l:
					max_n*=i
				for j in neg_l[1:]:
					min_n*=j
			else:
				min_n = 1
				max_n = 1
				for i in neg_l:
					min_n*=i
				for j in neg_l[1:]:
					max_n*=j
		else:
			max_n = neg_l[0]
			min_n = neg_l[0]


	ans_max = -1000000                
	if max_n>0 and max_p>0:
		ans_max= max_n*max_p

	elif max_n<0:
		ans_max = max(max_p,max_n,max_z)
		
	elif max_n>0 and max_p==0:
		ans_max = max_n

	ans_M= max(ans_max,max_z,max_p,max_n)

	ans_min = 1000000
	if min_n<0 and max_p>0:
		ans_min = min_n*max_p

	elif min_n<0 and max_p==0:
		ans_min = min_n
		
	elif min_n>=0 and min_p>=0:
		ans_min = min(min_n,min_p,min_z)

	ans_m  = min(ans_min,min_n,min_p,min_z)

	print(ans_M,ans_m)
		
		
		
				
		
			
		
		
	
			
	


t=int(input())
for i in range(0,t):
	n=int(input())
	l=list(map(int,input().split()))
	l=sorted(l)
	m=l.pop()
	s=m
	if m==0:
	    if len(l)>0:
	        while l[-1]==0:
	            l.pop()
	            if len(l)==0:
	                break;
	    if len(l)>1:
	        m=l.pop()
	        s=m
	    elif len(l)==1:
	        s=l.pop()
	if m<0 and len(l)>0:
	    if len(l)%2!=0:
	        s=1
	        for j in range(0,len(l)):
	            k=l.pop()
	            s*=k
	            m*=k
	    else:
	        m=1
	        for j in range(0,len(l)):
	            k=l.pop()
	            s*=k
	            m*=k
	elif m>0 and len(l)>0:
		while l[-1]>0:
			s=l.pop()
			m*=s
			if len(l)==0:
			    break
		if len(l)!=0:
		    while l[-1]==0:
		        l.pop()
		        if len(l)==0:
		        	s=0
		        	break
		    if len(l)>0 and (len(l)%2)==0:
		        s=m
		        m*=l.pop()
	    		while len(l)>0:
	    			k=l.pop()
	    			m*=k
	    			s*=k
	    	if len(l)%2!=0:
	        	s=m
	        	s*=l.pop()
	        	while len(l)>0:
	        		k=l.pop()
	        		m*=k
	        		s*=k
	print(m,s)