## 10763 - Foreign Exchange

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 10763 - Foreign Exchange

should the output of the following input be YES?

Code: Select all

3
1 2
1 2
2 1
And the is no specification for the range of the location. Can I assume it's within 32bit signed integer?

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
Output should be:
NO

my accepted code assumes that input data fits in 32bit integer.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
if u carefully read the problem description u will find that the range of location is not more than 500000.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
prince56k wrote:if u carefully read the problem description u will find that the range of location is not more than 500000.
Pardon me? I checked the problem statement again, but I couldn't find anything like this. The only limit I found was:

Locations will be represented by nonnegative integer numbers.

As far as I know, 500000 is only the limit on the number of students.

The only assumption my program makes is that the location numbers will fit into a 32-bit int. If there are only inputs with numbers <=500000, the test data is not sufficient.

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

### Once again I rule the roost

Once again I rule the roost! (0.074 s as of this writing)

And yes, the numbers can fit into a signed 32 bit integer (i.e. they are <=2 to the 31st minus 1). Nothing in the problem statement constrains the actual values. Only the total number of value sets in one exchange program is constrained, and is limited to 500,000, per the problem statement. There are no other constraints, including max number of exchange programs, which is unconstrained.

Michael Goldshteyn

M A Hassan
New poster
Posts: 3
Joined: Tue Nov 02, 2004 12:44 pm

### 10763 - Foreign Exchange

any hint plz...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Use hashing to reindex the countries, the new numbers will be from 1 do X, where X is at most 2N.

Now for each candidate (from, to) form two triplets: (from, to, 1) and (to, from, -1). We can sort the 2N triplets in O(N) using e.g. radixsort.

The answer is YES iff for all countries x,y the number of people leaving from x to y is the same as the number of people leaving from y to x. Using our triplets this is easy to check -- consider all triplets (x,y,?), sum the third coordinate and check, whether the result is zero.

Just for the record: you don't need a worst-case O(N) solution to get AC.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
I think it can be done without hashing. I've done it during the contest in an alternative way, probably using an extra bit of memory. I took the inputs in two different arrays (containg the same values. I used struct type containing x & y as its elements). The first array (Call it a[]) was ascendingly sorted by values of x, ties were broken by ascending values of y. The second array (Call it b[]) was ascendingly sorted by y while ties broken by x. Then I traverse through i = 0 to n-1 to see wheter a.x==b.y & a.y==b.x holds true. If the check fails on any i, the program will report NO & immediately terminate. Else if this is not true for any i, the program will report YES. Though I used quick sort during the contest which implies an O(n log n) worst case behaviour, I think it works in O(n) in the worst case if an O(n) sorting algorithm is used as Misof stated.
Last edited by Mohammad Mahmudur Rahman on Wed Nov 17, 2004 1:46 am, edited 1 time in total.
You should never take more than you give in the circle of life.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
The problem is that all O(N) sorting algorithms require the sorted data to be in some special form. For example, CountSort is not O(N), but O(N+|S|) in the general case, where S is the set from which the sorted numbers are chosen. I.e. CountSort is only linear if we are sorting elements that can have approximately N different values.

In this case the IDs of countries were not bounded, therefore you couldn't hope for a better sort algorithm than O(N log N).

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Thanks for the reminder, Misof !
You should never take more than you give in the circle of life.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Hi , Unfortunately I missed the contest for my exam , so couldn't solve it during contest time.....

now I solved it in UVA, I got Acc at 1.6 sec where contest time was 1 sec, I didn't try to reduce my time as here time is much more then I need....

I can make it more efficient by reducing sorting elements...I m sorting total n*2 elements, where I may need much less then that as there will be same values again and again.....

can anyone who got Acc in contest tell me...Is now UVA data larger then the contest or is it the same data size?

Thanks.....
Jalal : AIUB SPARKS

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
CodeMaker wrote:Can anyone who got Acc in contest tell me...Is now UVA data larger then the contest or is it the same data size?
Thanks.....
It is most likely that UVa dataset is larger than the one used during the contest. I got it AC during the contest using the algorithm stated above but the same code used about 3.6 seconds in the 24-hours judge.
You should never take more than you give in the circle of life.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
My teammate has just remind me that during the contest, the time limit was increased. If I am not wrong, the time limit for this problem was reset to 7 seconds during the contest. Sorry 4 the above post.
You should never take more than you give in the circle of life.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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?
There is another thread on this problem (http://online-judge.uva.es/board/viewtopic.php?t=6962), some possible O(N) solutions are mentioned there.