AjaySabarish's blog

Amazon Online Assessment Problem[Ended on 21st March]
By AjaySabarish, history, 4 years ago, In English

You are given an array of N integers (N is even), at each round you have to select 2 numbers $$$(A[i],A[j])$$$, and do $$$ Sum = Sum + GCD(A[i], A[j]) * round $$$, post calculating sum remove those 2 numbers from Array. What is the maximum possible sum you can obtain?

Round's value starts from 1.

Constraints

$$$ 2 \leq N \leq 20 $$$

$$$ 1 \leq A[i] \leq 1e9 $$$

I tried Bitmasking Dp ( $$$ O(2 ^N * N ^2) $$$ ) but got TLE.

Example :

2 3 5 9

1st Round — 2 5, Sum = GCD(2,5) * 1

2nd Round — 3 9, Sum = GCD(3,9) * 2

The maximum possible sum is 7

Any insights?

  • Vote: I like it
  • -18
  • Vote: I do not like it

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

I did the same and got AC, u did it in recursive or iterative approach?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    recursion

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain the solution i was only getting 15/25 tc

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for mask : [1, 2^20]: for ith setbit in mask: for jth setbit in mask: dp[mask] = max(dp[mask], dp[mask ^ (1 << i) ^ (1 << j)] + (gcd(a[i],a[j]) * m))

      where 'm' refers to the round number that can be found for every mask in constant time.

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

same problem

but it is having constraints as N <= 14.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Even I also did the same thing and got TLE.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is an online version of it: https://leetcode.com/contest/biweekly-contest-48/problems/maximize-score-after-n-operations/

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Precompute all GCDs

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But isn't the worst-case time complexity the same ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Yes, but the running time decreases significantly as calculating GCD is O(log n) and precomputing will help. I was also getting TLE in the start but after precomputing, the code worked fine

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

how does this state work, dp[mask] = max gcd pairwise sum you can achieve from bits present in mask

i wrote code with this as state and it passed all test cases except one due to recursion

I also wrote dp like this dp[mask][R] = max gcd pairwise sum you can achieve from bits present in mask and the current round is R,

I feel that the second dp notation has correctness in it, but for the first case since the round information is missing

my code: https://ideone.com/2Q4I3m , same code after removing the second state which stores the round number also passed.

my doubt is around the correctness of the first dp notation where we are only memoizing the mask

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that popcount/2 + 1 is the round number for particular mask (ignoring odd bits masks), hence round is a redundant state and need not to be present

    → Reply