10763 - Foreign Exchange

[AdamP]

thanks dan

[chops]

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");
}
}

Code: Select all

[Sedefcho]

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]

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

[Sedefcho]

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]

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

[Sedefcho]

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]

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;
}

[Martin Macko]

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]

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]

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!!!!!!

[kbr_iut]

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

[Shafaet_du]

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

[lfmunoz]

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]

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.