DPAIRS - EDITORIAL

Can someone tell me why my solution didn’t work? I put A and B into vectors and sorted A and B. Then I took the smallest index of A which is 0 and paired with all indexes of B and then I took the largest index of B which is B.size() - 1 and paired it with all values of A starting from index 1 since 0 is smallest index of A.

Why didn’t this solution work?

https://www.codechef.com/viewsolution/22488614

Hello @michael_123,

I think your solution is failing because you’re printing the new indexes (the ones you have after the sort) instead of the previous ones. So your solution can only works when the smallest element of A is at index 0 and when the biggest element of B is at index m-1.

2 Likes

Can anyone help me out here…My solution is still getting WA for some test cases.

I have paired minsetA with all values of setB to get |B| values. Further I have paired maxSetB with all values of setA but first_(minsetA)_ hence getting another |A|-1 values, original indices have also been maintained.

Where I have possibly gone wrong?

https://www.codechef.com/viewsolution/22490725

why sorting of the vector is necessary for subtask 2.without sorting the vector code is working just for subtask 1.

@satheesh2k14 read the question again, it is already mentioned that all the elements of the array are distinct.

can someone help I’m failing only 1 test case in the first sub task remaining is ok click here

@officialnizam Try

3 4
1 2 3
2 3 4 6

You pick both (1, 6) and (3, 4) which have the same sum.

Unbelievably, you almost got an AC, showing test cases are so weak.

3 Likes

IT CAN BE SOLVED WITHOUT SORTING. JUST FIND THE MINIMUM ELEMENT OF ONE SEQUENCE AND THE MAXIMUM ELEMENT OF THE OTHER SEQUENCE.

All the test cases, except 3 in the first subtask, have n = m.

https://www.codechef.com/viewsolution/22515213

can this problem be solved using SET?
adding elements and then inserting in the set, if size increases then display indexes.

What does it mean “Ax+By for all pairs is pairwise distinct”? Anyone.

For the editorial solution to work, either sequence A or sequence B should be unique. But no where in the problem it was mentioned or is it mentioned in the problem?

4 Likes

exactly !!
just find index of minimum and maximum values…

Can you elaborate?

vector< pair< int,int > > B(n); - should be m.

I didn’t understand what you were trying to say, but no sorting is necessary for either subtask. :slight_smile:

Everybody has figured that out - no need to SCREAM. xD

i have a question that whats the logic behind using if n != 10 condition can u explain…plzz

No logic. The condition allows the test cases to be passed. That illustrates how weak they are.

could u tell how to know that for this reason i am getting the wrong aswer…plzz?