Greatest789's blog

By Greatest789, history, 4 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you provide link for question 1

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

sorry i didn't read full article!