Yashraj1402's blog

By Yashraj1402, history, 5 weeks ago, In English

Problem Link

My Approach:

Only make the first element of vector A less than vector B. So if B[0] < A[0], iterate over A and find the first element smaller than B[0] by this we will also know the number of swaps required to change the first element of A. Then iterate over B and find the first element greater than A[0] by this we will know the number of swaps required to change the first element of B. Print the minimum number of swaps.

solution Link ,546th test case fails.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

As a counter example try that on:

A : [9 7 5 3 1] and B : [2 8 6 4 10],

We'll have moves_in_a = 4 and moves_in_b = 4 but we can exchange 2 with 8 and 9 with 7 to get the result in 2 steps ending up at:

A : [7 9 5 3 1] and B : [8 2 6 4 10],

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Immagine the following test case:

5

7 5 9 3 1

2 6 4 8 10

The optimal answer is 2 operation: swap(7, 5); swap(2, 6). Your answer is min(4, 3) which is 3(swap(4, 8); swap(6, 8); swap(2, 8)). In order to do these fast, I made a binary search on the answer. If I can get an answer in x operation, I can get it in x+1 operations. You can check a given x using a prefix minimum on a and a prefix maximum on b in O(N). The final complexitiy is O(NlogN).