Блог пользователя Greatest789

Автор Greatest789, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can you provide link for question 1

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

sorry i didn't read full article!