Given 2-arrays "$A$" and "$B$" of length $n$ , calculate maximum possible product of all elements of array "$C$" ,↵
↵
where , ↵
↵
$C[i] = A[j]*B[k] $↵
↵
Or↵
↵
$C[i] = A[j] + B[k] $,↵
↵
(its your choice, what to select from both of them)↵
↵
for all $1<=i<=N$↵
↵
Once an index 'j' and 'k' have been used from array A and B respectively, you can't use them ever again.↵
↵
Find the maximum possible value of C[1]*C[2]*......C[N] modulo p , where p = 1000000007. ↵
↵
$1<=A[i]<=100000 $↵
↵
$1<=B[i]<=100000 $↵
↵
$1<=N<=100000 $↵
↵
Example : ↵
↵
Array A : [1,2] ↵
↵
Array B : [4,3]↵
↵
Best possible array C :$ [(3+1),(4*2)] = [4,8] .$↵
↵
Final answer = 4*8 = 32 which is the maximum possible product.↵
↵
↵
I applied the greedy approach in the test which failed all the test cases except 1.↵
↵
↵
My greedy approach was : Sort both "A" and "B", then do $C[i]=max(A[i]+B[i], A[i]*B[i]) $↵
↵
↵
Second problem of the test was : Given a graph with $N$ nodes and $M$ edges , remove any number of nodes you want to remove and calculate the maximum-sized-bipartite-graph. (Don't remember the constraints, I think N and M were small.)↵
↵
↵
↵
↵
where , ↵
↵
$C[i] = A[j]*B[k] $↵
↵
Or↵
↵
$C[i] = A[j] + B[k] $,↵
↵
(its your choice, what to select from both of them)↵
↵
for all $1<=i<=N$↵
↵
Once an index 'j' and 'k' have been used from array A and B respectively, you can't use them ever again.↵
↵
Find the maximum possible value of C[1]*C[2]*......C[N] modulo p , where p = 1000000007. ↵
↵
$1<=A[i]<=100000 $↵
↵
$1<=B[i]<=100000 $↵
↵
$1<=N<=100000 $↵
↵
Example : ↵
↵
Array A : [1,2] ↵
↵
Array B : [4,3]↵
↵
Best possible array C :$ [(3+1),(4*2)] = [4,8] .$↵
↵
Final answer = 4*8 = 32 which is the maximum possible product.↵
↵
↵
I applied the greedy approach in the test which failed all the test cases except 1.↵
↵
↵
My greedy approach was : Sort both "A" and "B", then do $C[i]=max(A[i]+B[i], A[i]*B[i]) $↵
↵
↵
Second problem of the test was : Given a graph with $N$ nodes and $M$ edges , remove any number of nodes you want to remove and calculate the maximum-sized-bipartite-graph. (Don't remember the constraints, I think N and M were small.)↵
↵
↵
↵
