htl wrote:I just read the data, separating them into 2 groups, one for i<j and i>j for the other. And I sort them and compare them. I got AC for such a long time. Could you share your method?
Hints for you:
I don't use any array or sorting to solve this problem
O(n log n ) is the best I can think of at this moment, someone with a better solution needs to try the next test case posted by Adrian. Getting AC means nothing cause at present judge data is simply too weak.
Last edited by Dreamer#1 on Wed Nov 24, 2004 9:43 pm, edited 1 time in total.
Well, you should think more than 10 minutes before you submit such a clearly wrong program. The test cases must be absolutely trivial in order to get accepted with this.
Consider following test case:
3
1 2
2 3
3 1
Its funny but guess what this is what got me AC during contest... but after reading your post when I read the problem again I just can't stop laughing... How did my solution get AC?
If you can't believe me please submit the solution and see what happens.
Anyways but I still find the problem very simple though can't think of a O(n) solution anymore.
Judge data should be made stronger. Thanks Adrian.
Hashing won't work here. You just don't have enough memory to stay at low number of collisions. If this got AC below second, then this is another case of weak test data. Imagine the case with 1'000'000 distinct locations.
No, that way is incorrect (but it got AC ). The incorrect method I told above is the following:
num(a>b) != num(a<b) -> NO
Otherwise make all 'a<b'
We want each pair to appear even number of times. The famous method I referred to was that a1 XOR a2 XOR ... XOR an = 0 and b1 XOR b2 XOR ... XOR bn = 0. But it works ONLY if there is exactly one pair occuring odd number of times. This is not the case with this problem. So, it will output YES even for this ridiculous test:
4
1 10
1 10
9 2
9 2
but it gets AC...
I ask those of you who got AC with O(N). What was your method?
Last edited by Destination Goa on Fri Feb 18, 2005 10:15 pm, edited 1 time in total.
It seems that the judge data for this problem is heavily weak!
I have already sent one critical case that was not included before... there seems to be many more..
I got AC using map<int,int> listsrc, listdes;
I simply counted the frequency, but an earlier post indicates that even this method is incorrect if judge data went to limit.
The most beautiful correct solution up to this point seems to me two sortings: one with priority on A, another with priority on B, and then checking that a1=b2, b1=a2 for each i=1...n. This way we actually make binary search for the pair, but the way arrays are sorted ensures that matching index in the 2nd array will be the same for the 1st array.
Though, it's about 2.2 or 1.5 seconds. I don't remember.
(just edited my invalid XORing sample (2nd one), I meant a little different situation).
I figured to read in the home and target destinations as 2 seperate arrays, sort them, then compare the results.
Ex:
3
1 2
2 3
3 1
YES
homeArray = {1, 2, 3}
targetArray = {3, 2, 1}
I sort them using merge sort and compare the elements in each, so homeArray == targetArray. Once I find a pair of elements which aren't equal the program stops and returns NO. It works for all the sample data, but when I submit to Judge I get WA.
I figure that if the arrays are equal, that means that an equal number of people are leaving and arriving at the same destination.
I'm not worried about the amount of time it takes to solve the problem, I just want the correct answer!
). The incorrect method I told above is the following: