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

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

Post by AdamP » Sat May 07, 2005 6:04 pm

thanks dan

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:

Post by chops » Wed Jun 15, 2005 10:23 pm

here is the code.it gets wrong answer.help please.


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define SIZE 500005

typedef struct{
long a,b;

}pair;

pair arr[SIZE];
int fnd[SIZE];

int comp(const pair * a,const pair *b)
{
if(a->a > b->a)return 1;
else if(a->a < b->a)return -1;
else if(a->a == b->a)
{
if(a->b > b->b)return 1;
else if(a->b < b->b)return -1;
}
return 0;
}



void main()
{
long N,ans,i,j,k;
pair *ptr;
pair key;


while(scanf("%ld",&N)==1 && N)
{
memset(fnd,0,sizeof(fnd));
for(i=0;i<N;i++)
{
scanf("%ld %ld",&arr.a,&arr.b);
}

qsort(arr,i,sizeof(pair),(int (*)(const void *,const void *))comp);
k=i;
ans=0;

for(i=0;i<N && !ans;i++)
{
if(!fnd)
{
key.a=arr.b;
key.b=arr.a;
ptr=(pair*)bsearch(&key,arr,k,sizeof(pair),(int (*)(const void *,const void *))comp);
if(!ptr)ans=1;
else
{
j=(ptr-arr);
if(fnd[j] && !fnd)ans=1;
else {fnd=fnd[j]=1;}
}
}
}
if(ans)printf("NO\n");
else printf("YES\n");
}
}

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Jul 05, 2005 3:19 pm

I can see there are about 600 accepted programs
for problem 10763. These about 600 accepted programs
are coming just from 200-250 people.

Well, I am wondering how many people have solved
this problem with a really ( with a logically ) correct solution.

I am pretty sure the Judge's test data
is very very weak.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Jul 05, 2005 4:58 pm

Sedefcho wrote:I can see there are about 600 accepted programs
for problem 10763. These about 600 accepted programs
are coming just from 200-250 people.

Well, I am wondering how many people have solved
this problem with a really ( with a logically ) correct solution.

I am pretty sure the Judge's test data
is very very weak.
For sure I contributed significantly to the high numbers.
I submitted around 20 programs and got maybe 10 AC.
I believe my solution is indeed logically correct, but I'm not entirelly satisfied with it since it's around 7x times slower that the fastest AC one!!!
My first one (using my own quicksort routine, marginally faster than builtin qsort) took 1.713 seconds.
I tried to tune this approach without much success shaving some tenth of second and then I compacted the data and halved the runtime.
Then I switched to a different approach using an hash table reaching a runtime of a half second and then shaved it a little bit more.

I don't know in which sense you think the judge data is weak. Can you give some example of data that would challenge weak solutions?

Ciao!!!

Claudio

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Jul 05, 2005 5:02 pm

I use some sort of hashing which is logically wrong, I know that :)

Even on a simple test case like this one:

Code: Select all

4
1 3
2 4
5 7
14 8
0
my ACC program says "YES" while it should say "NO".

That's why I think the test cases of the Judge are pretty weak.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Jul 05, 2005 5:23 pm

Sedefcho wrote:I use some sort of hashing which is logically wrong, I know that :)

Even on a simple test case like this one:

Code: Select all

4
1 3
2 4
5 7
14 8
0
my ACC program says "YES" while it should say "NO".

That's why I think the test cases of the Judge are pretty weak.
Probably you don't handle hash clashing.
My AC program uses a proper hash function, uses a big hash table (sized 1000000) and tolerates hash clashes. It correctly returns NO to your test case.

I hope you'll provide some strong test case to the OJ so that maybe my prog will gain some ranks against the faster ones ;)

Ciao!!!

Claudio

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Jul 05, 2005 5:31 pm

:) :) Well, I doubt it ... I am not that keen on
constructing test cases ... I just wanted to mention that
apparently the test cases of the Judge are not that strong.

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

10763 Foreign exchange (Hashing But what's incorrect here!!)

Post by murkho » Tue Sep 06, 2005 4:45 pm

Anyone pls tell me what mistake i did .

Code: Select all

//submit today...

#include<stdio.h>


	unsigned long store[500100],max = 0,count= 0;

void initialise()

{
	unsigned long i,j;
	for(i = 0;i<500009;i++)
		store[i] = 0;


}


int main()
{
	unsigned long  in,i;
	unsigned long  a,b;
	//freopen("10763.in","r",stdin);


	while(scanf("%lu",&in) ==1 && in)
	{
		initialise();
		count = 0;
		for(i = 0;i<in;i++)
		{
				scanf("%lu %lu",&a,&b);
				store[a] -=b ;
				store[b]+= a;
				if(store[a] == 0)
					count++;
				if(store[b]==0)
					count++;
		
		
		
		}	


		if(count == in )
			printf("YES\n");
		else 
			printf("N0\n");
	}



	return 0;
}



User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10763 Foreign exchange (Hashing But what's incorrect her

Post by Martin Macko » Wed Sep 07, 2005 7:27 pm

murkho wrote:

Code: Select all

				scanf("%lu %lu",&a,&b);
				store[a] -=b ;
				store[b]+= a;
a (and also b) are not guaranteed to be <=500000.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Tue Sep 27, 2005 8:07 pm

Destination Goa wrote: I ask those of you who got AC with O(N). What was your method?
If you mean O(N) expected time, then hashing is a correct solution.
I don't know why some of you seem to imply that it is "logically incorrect".
Just keep a hash table that can be indexed by an ordered pair of numbers and contains the number of times each pair has occurred in the input.
Then again, of course it's not O(N) worst-case, if that is what you mean. But the method above works fine and is accepted in about 1 second.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10763 - Wrong TESTS! Author, change tests!

Post by medv » Fri Nov 11, 2005 9:13 am

Hi! I solved this problem using trees,
BUT! Found absolutely stupid and incorrect solution
and it is ACCEPTED:

#include <stdio.h>
int i,n,a,b,_a,_b;

int main(void)
{
while(scanf("%d",&n),n>0)
{
_a = _b = 0;
for(i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
_a ^= a; _b ^= b;
}
if (_a == _b) printf("YES\n");
else printf("NO\n");
}
return 0;
}

To author:
The exchange of students is possible, then my program give YES - and
it's right because if (Ai, Bi) - pairs, then XOR(Ai) = XOR(Bi).

But sometimes exchange is impossible, my program also
gives YES. For example , on this test:

3
1 2
3 4
2 6

XOR(1,3,2) = XOR(2,4,6) but the answer must be NO.

Please, correct (change) TESTS!!!!!!

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10763 - Foreign Exchange(nice trick)

Post by kbr_iut » Thu Sep 18, 2008 5:12 am

there is a nice trick to solve the problem
1.take the first numbers in a vector v and 2nd numbers in another vector vv;
2.sort them with built in algorithm sort
3.compare the two vectors using bool operator==(v,vv);

in this way this problem can be solved within 6 lines though it is a bit slow.
i got AC in 1.290 sec. rank 174 over 547(not too bad).
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10763 - Foreign Exchange

Post by Shafaet_du » Sun Nov 21, 2010 12:06 am

I used i map like this:
map< pair<int,int> ,int >mymap;
to solve this problem.

lfmunoz
New poster
Posts: 1
Joined: Wed Jan 05, 2011 9:59 pm

Re: 10763 - Foreign Exchange

Post by lfmunoz » Sat Jan 08, 2011 1:46 am

Can someone tell what is wrong with my code or tell me under which input will it fail?


/* 10763 - Foreign Exchange */

#include <stdio.h>
#include <stdlib.h>

int compare (const void * a, const void * b)
{
return ( *( unsigned long*)a - *( unsigned long*)b );
}



void get2num(unsigned long *n1, unsigned long *n2) {
unsigned long x = 0;
char input1[10];


/* get both numbers */
while( (input1[x] = getchar()) != 32 ) { x++; }
input1[x] = '\0';
*n1 = atoi(input1);
x = 0;

while( (input1[x] = getchar()) != 10 ) { x++; }
input1[x] = '\0';
*n2 = atoi(input1);
/*
if(*n1 < *n2) {
x = *n1;
*n1 = *n2;
*n2 = x;
}
*/
}

unsigned long get1num(void){

unsigned long x = 0;
char input[10];

while((input[x] = getchar()) != 10 ) {

x++;
if(input[0] == 48) return 0;


} /*10 is line feed */


input[x] = '\0';
return atoi(input);
}

int main(void) {

unsigned long data;
unsigned long data1, data2;
unsigned long x;
unsigned long *ptr;
unsigned long fail = 0;

while( (data = get1num()) != 0 ) {

data = data * 2;

ptr = (unsigned long*) malloc((sizeof(unsigned long) * data));
for( x = 0; x < data; x++) {

get2num(&data1, &data2);
ptr[x] = data1;
x++;
ptr[x] = data2;
}

qsort (ptr, data, sizeof(unsigned long), compare);



for( x = 0; x < data; x = x + 2) {

if(ptr[x] != ptr[x+1]) {
fail = 1;
}

/*printf("%d %d\n", x, ptr[x]);*/

}


if(fail) {
printf("NO\n");
}
else {
printf("YES\n");
}

free(ptr);

}

}

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10763 - Foreign Exchange

Post by Imti » Mon Jun 13, 2011 1:14 pm

To:lfmunoz
I don't know whether you got accepted or not.Your code fail at this input:
Input:

Code: Select all

4
1 2
1 2
2 1
2 1
Output:

Code: Select all

YES
Your code produce NO.

Post Reply

Return to “Volume 107 (10700-10799)”