10763 - Foreign Exchange

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Wed Nov 24, 2004 6:32 am

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 :lol:

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Wed Nov 24, 2004 11:03 am

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

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Wed Nov 24, 2004 8:07 pm

O(n) solution =>> Weak Judge Data :D

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. :oops:
Last edited by Dreamer#1 on Wed Nov 24, 2004 9:43 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Nov 24, 2004 8:40 pm

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.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Wed Nov 24, 2004 9:10 pm

oops.. sorry... :oops:

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? :D

If you can't believe me please submit the solution and see what happens. :lol:

Anyways but I still find the problem very simple though can't think of a O(n) solution anymore. :o

Judge data should be made stronger. Thanks Adrian.

regards...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 9:27 pm

A1, do you have AC now after appended test data?
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 9:29 pm

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.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 9:35 pm

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.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:10 pm

No, that way is incorrect (but it got AC :evil:). 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.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:11 pm

A1,

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

Was this your method?
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:14 pm

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
Last edited by Destination Goa on Sat Feb 19, 2005 11:43 am, edited 1 time in total.
To be the best you must become the best!

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Feb 19, 2005 8:29 am

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.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sat Feb 19, 2005 11:40 am

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).
To be the best you must become the best!

AdamP
New poster
Posts: 7
Joined: Sat May 07, 2005 5:20 am

10763 help!

Post by AdamP » Sat May 07, 2005 5:27 am

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!

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sat May 07, 2005 2:27 pm

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

Post Reply

Return to “Volume 107 (10700-10799)”