How to solve this array based problem ?

Revision en2, by Greatest789, 2020-10-02 18:54:16

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.)

Tags #arrays

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Greatest789 2020-10-02 20:10:06 2 Tiny change: ',\n\nwhere , \n\n$C[i] ' -> ',\n\nwhere,\n\n$C[i] '
en2 English Greatest789 2020-10-02 18:54:16 240
en1 English Greatest789 2020-10-02 18:47:56 928 Initial revision (published)