Help needed in Arrfix SRM 696

general
1

How to solve Arrfix ? Can someone explain in detail?

2

Knock Knock !! Can someone out there help me with this ??!!

3

Here is my solution -

Though the Problem was mention under DP , but I couldn’t find any overlapping substructure.

Example-

Consider all Arrays as 0-indexed.

A ={ 1, 8, 7, 6, 3, 4 }

B ={ 1, 8, 8, 8, 6, 5 }

F ={ 8, 8, 1, 5, 12}

Solution-

  1. Find the common elements of B and F including the repetitions i.e. the Common Elements are = { 8, 8, 1, 5}

  2. Find the optimum position to paste those common elements from F to A such that the difference between A and B is least. For example- Where should first 8 from F be pasted on A ? the optimum position is A[2] i.e. 7 is replaced by 8 . And where would second 8 from F be pasted on A ? The optimum position is A[3] i.e on 6.
    But what if there is no optimum position ? like for 1 ? there is only one 1 in B and the corresponding A is 1 … that is , it already has the best match for it . But remember we have to use all the F elements , so to use the F[2] element i.e. 1 we can Replace A[0] with 1, though A[0] was already 1 but here the optimum position for F’s 1 is A[0] …because if we place anywhere else then it would just increase the difference

  3. Lastly you have to count the number of differences that exist between A and B even after doing the operation (mentioned in 2) for each of the common elements in F.

  4. One More Check Step- In the end you have to check whether the number of differences < the number of uncommon elements between B and F.
    If so, the the least number of differences = the number of un-common elements between B and F. What this means is that no matter what, you have to paste the F elements on A , so u have to paste the uncommon elements also , which increases the difference between A and B.

The Final Arrays are

A = { 1, 8, 8, 8, 12, 5 } modified

B = { 1, 8, 8, 8, 6, 5 } unchanged

Difference = 1

Complexity Analysis -

The main focus is to find the common elements between B and F.

Let n = B.size() and fnum = F.size()

Complexity to find the common elements after sorting B and F = O( n + fnum ). {I made a copy of B then I sort it}

But to sort them = O( max(nlogn, fnumlogfnum) )

Thus the complexity is O( max(nlogn, fnumlogfnum) )

which works fine by the constraints.

If you Like my solution , Give a THUMBS UP. :slight_smile:

2 Likes
4

Thank you.