OJ Board

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

I have thought about the binary search tree.... Do I get the answer?

O(n) solution =>> Weak Judge Data

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.

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

you output YES.

oops.. sorry...

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.

regards...

A1, do you have AC now after appended test data?

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.

There is a way without any arrays and without any sorting. A hint: num(a>b) != num(a<b) - NO. Otherwise one famous trick makes it solveable.

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?

A1,

Please check my reply on the other thread:
http://online-judge.uva.es/board/viewto ... 2070#32070

Was this your method?

That case was about invalid swapping. This one is about invalid XOR'ing:
6
0 1
0 2
0 3
4 0
8 0
12 0

I guess invalid_method XOR invalid_method gave me AC

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).

Trying to do the foreign exchange problem

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!

You misunderstood the problem.

if a student wants to go from A to B, there must be another student who wants to go from B to A

So no single exchange is allowed to include more than 2 students.
That means it should be:

3
1 2
2 3
3 1
NO