LTIME17 CSS2

This question appeared in today’s Lunchtime contest.

Question

My Solution

It is giving WA. Can somebody tell me what is wrong with my code?

I think the sorting the input array is a good idea, because when id,attribute and priority are equal we should consider the value which appeared last. Sorting may not keep them order of their appearance in the original array. So that might be one reason for the WA …

1 Like

You are sorting the elements in the array using the inbuilt sorting function which is an unstable sort so the relative ordering of the elements may not be in the same order as they appeared originally.

So the order in which the inputs were given might change, and you will assume the last input given to be a wrong one (for same priority).

Consider using stable_sort.

2 Likes

You are right. I got AC with stable_sort. But the comparison function that I implemented took care of that, in which case it shouldn’t give WA. Can you please explain??

No your comparison function makes no difference between objects that have same id, attribute and priority. Thus sort function will see no difference between 2 such objects and arrange them in any manner.

To maintain the relative ordering of the equivalent objects, you need a comparison function that order elements on their memory address. If you used stable_sort there would be no need for that.

1 Like

Wonderful explanation. Thanks for that!