10763 - Foreign Exchange

Cho · Post by **Cho** » Wed Nov 10, 2004 5:43 pm

should the output of the following input be YES?

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

sidky · Post by **sidky** » Wed Nov 10, 2004 7:30 pm

Output should be:
NO

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

prince56k · Post by **prince56k** » Thu Nov 11, 2004 8:15 pm

if u carefully read the problem description u will find that the range of location is not more than 500000.

misof · Post by **misof** » Thu Nov 11, 2004 8:32 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 · Post by **Michael Goldshteyn** » Fri Nov 12, 2004 12:05 am

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 · Post by **M A Hassan** » Tue Nov 16, 2004 7:12 am

any hint plz...

misof · Post by **misof** » Tue Nov 16, 2004 11:24 am

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.

Mohammad Mahmudur Rahman · Tue Nov 16, 2004 7:24 pm

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.

misof · Post by **misof** » Tue Nov 16, 2004 8:48 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).

Mohammad Mahmudur Rahman · Wed Nov 17, 2004 6:31 pm

Thanks for the reminder, Misof !

CodeMaker · Post by **CodeMaker** » Wed Nov 17, 2004 7:20 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.....

Mohammad Mahmudur Rahman · Wed Nov 17, 2004 7:51 pm

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.

Mohammad Mahmudur Rahman · Wed Nov 17, 2004 10:07 pm

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.

htl · Post by **htl** » Tue Nov 23, 2004 3:22 pm

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 · Post by **misof** » Tue Nov 23, 2004 11:17 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.