CHFNSWPS - Editorial

editorial
, , , , ,
23

Thanks for the suggestion. Really helped a lot.

1 Like
24

here is my codehttps://www.codechef.com/viewsolution/35380882

I canā€™t find where my code is failing the given test case, can you help me out?

25

You havenā€™t taken care of condition when swapping needs to be done with min element . Like
A=[1,89,89]
B=[1,36,36]
from your algo answer will be 36 but it will be 2

1 Like
26

Thanks for your helping work but the thing is, my code gives the correct answer for such test cases but shows WA due to some other edge case. Iā€™m unable to find the edge-case.

27

@rishup_nitdgp @enchom Pardon me if Iā€™m wrong but Iā€™ve read the Setterā€™s solution and i think itā€™s wrong. Vectors v1 and v2 store the elements which are going to participate in the swaps. For the time being letā€™s assume that all the elements in the array are greater than 2*min element. Then if I have the following vectors
v1 : 1 2 6 7 8
v2 : 9 4 5 3 3

then acc to setterā€™s way, the answer is
min(1,9) + min(2,4) + min(6,5) + min(7,3) + min(8,3) = 1 + 2 + 5 + 3 + 3 = 14

but the cost can be further minimized by swapping the following pairs
(1,5) (7,3) (8,3) (2,9) (6,4)
which gives the cost as 1 + 3 + 3 + 2 + 4 = 13

This cost can be arrived at by merging the v1 and v2 vectors, sorting them and then taking the sum of first half of the vector.

The reason is as follows: After sorting the combined (v1 + v2) vector, the elements which appear in the first half of this resulting vector can be either from v1 or v2 or both, but it doesnā€™t matter. If the initial length of vector v1 (or v2) was n and if in the combined array, letā€™s say only 2 elements that appear in the first half are from v1, then this implies that (n-2) elements are from v2.

The 2 elements from v1 can be combined with the 2 elements from v2 which are in the second half of the sorted array, and the (n-2) elements of v2 in the first half can be combined with (n-2) elements of v1 in the second half.

Correct me If Iā€™m wrong

28

Thanks for helping
I spend a lot of time for this question to solve but I didnā€™t get where I m wrong, really I completely unaware of this. Thanks a lot :blush:.

1 Like
30

The wording of the problem seems somewhat ambiguous to me. Are the swaps to be made after the two arrays are sorted, or are the swaps to be made before the sorting occurs. The algorithms are quite different for the two cases. The problem statement says " after they are sorted in non-decreasing order, the i-th element of one sequence is equal to the i-th element of the other sequence for each i (1 ā‰¤ i ā‰¤ N). I interpreted this to mean the two arrays were to be sorted before the swaps occurred. If the problem was to simply make the frequency of all numbers in both arrays identical, then the mention of sorting seems like a red herring (simply added to create confusion).

3 Likes
31

Bro, setter is reversing the vector 2
So according to setters way
V1 - 1 2 6 7 8
V2 - 9 5 4 3 3
Ans will be 9
Because the minimum element is 1
Therefore-
Min(2, min(1, 9)) = 1
Min(2, min(2, 5)) = 2
Min(2, min(6, 4)) = 2
Min(2, min(7, 3)) = 2
Min(2, min(8, 3)) = 2
Sum up all these answer is 9.

32 
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iterator>     // std::back_inserter
using namespace std;

int main() {
	long long int T;
	unsigned long long int N,X,Y,resZ,min_sum,val;
	vector<long long int> ArrX,ArrY,inter;
	cin>>T;
	while(T--)
	{
	  cin>>N;
	  ArrX.clear();
	  ArrY.clear();
	  inter.clear();
	  resZ= 0;
	  min_sum= 0;
	  for(long long int i=0;i<N;i++)
	   {
	    cin>>X;
	    ArrX.push_back(X);
	    resZ = resZ ^ ArrX[i];
	   }
	   for(long long int i=0;i<N;i++)
	   {
	    cin>>Y;
	    ArrY.push_back(Y);
	    resZ = resZ ^ ArrY[i];
	   }
	   if(resZ==0)
	   {
	      sort(ArrX.begin(), ArrX.end());
	      sort(ArrY.begin(), ArrY.end());
	      set_intersection(ArrX.begin(), ArrX.end(), ArrY.begin(), ArrY.end(), back_inserter(inter));
	      ArrX.erase(set_difference(ArrX.begin(), ArrX.end(), inter.begin(), inter.end(), ArrX.begin()), ArrX.end());
	      ArrY.erase(set_difference(ArrY.begin(), ArrY.end(), inter.begin(), inter.end(), ArrY.begin()), ArrY.end());
	      val = ArrX.size()-1;
          
          for(long long int i=0;i<ArrX.size();i++)
	      {
	        min_sum = min_sum + min(ArrX[i],ArrY[val-i]);
	      }
	      cout<<min_sum/2<<endl;
	   }
	   else
	     cout<<-1<<endl;
	}
	return 0;
}

my answer is coming 8 plz check even then only 1 test case was passed and I did not know where its failing.Can someone plz help.

33

ā€œFor the time being letā€™s assume that all the elements in the array are greater than 2*min element.ā€

34

The arrays (1, 2, 6, 7, 8) and (9, 5, 4, 3, 3) give 13 with authorā€™s approach as well. Your v2 wasnā€™t properly sorted in your example.

I believe what the author does is actually equivalent to your proposal of sorting the merged array and taking the first half. Itā€™s just a different way to implement / think about the same thing.

36

Ok, then answer will not be 9 but 13 according to setters solution. You v2 was not sorted before reversing.

37

hell of a question required pure programming.

38

I did the same thing and got only 15 points. Why so?
I think this algo should work for large values of N too.
https://www.codechef.com/viewsolution/35591715

39

why does you code have a condition for n <= 20 ?

40

Bro try to use long long int because the cost of swaps can be greater than 10^9.Hope it will help :innocent:

41

Oh sorry, I tried modifying a lot of things. When my code wasnā€™t working for n>20, I added this condition.
Check out this submission. CodeChef: Practical coding for everyone

43

Can anyone please tell me for which case does my solution fail. It failed in one of the sub tasks.

44

Can someone help me with optimizing my code I am getting TLE on 2nd task, here is my solution, Thanks in advance.

45

I think your time complexity is going upto O(n^2) by using pop in for loop. pop(0) has time complexity O(n).