10763  Foreign Exchange
Moderator: Board moderators
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=(ptrarr);
if(fnd[j] && !fnd)ans=1;
else {fnd=fnd[j]=1;}
}
}
}
if(ans)printf("NO\n");
else printf("YES\n");
}
}
#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=(ptrarr);
if(fnd[j] && !fnd)ans=1;
else {fnd=fnd[j]=1;}
}
}
}
if(ans)printf("NO\n");
else printf("YES\n");
}
}
Code: Select all
I can see there are about 600 accepted programs
for problem 10763. These about 600 accepted programs
are coming just from 200250 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 problem 10763. These about 600 accepted programs
are coming just from 200250 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.Sedefcho wrote:I can see there are about 600 accepted programs
for problem 10763. These about 600 accepted programs
are coming just from 200250 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.
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
I use some sort of hashing which is logically wrong, I know that
Even on a simple test case like this one:
my ACC program says "YES" while it should say "NO".
That's why I think the test cases of the Judge are pretty weak.
Even on a simple test case like this one:
Code: Select all
4
1 3
2 4
5 7
14 8
0
That's why I think the test cases of the Judge are pretty weak.
Probably you don't handle hash clashing.Sedefcho wrote:I use some sort of hashing which is logically wrong, I know that
Even on a simple test case like this one:my ACC program says "YES" while it should say "NO".Code: Select all
4 1 3 2 4 5 7 14 8 0
That's why I think the test cases of the Judge are pretty weak.
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
10763 Foreign exchange (Hashing But what's incorrect here!!)
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;
}

 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
a (and also b) are not guaranteed to be <=500000.murkho wrote:Code: Select all
scanf("%lu %lu",&a,&b); store[a] =b ; store[b]+= a;
If you mean O(N) expected time, then hashing is a correct solution.Destination Goa wrote: I ask those of you who got AC with O(N). What was your method?
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) worstcase, if that is what you mean. But the method above works fine and is accepted in about 1 second.
10763  Wrong TESTS! Author, change tests!
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!!!!!!
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!!!!!!

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 10763  Foreign Exchange(nice trick)
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).
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...............................
It is more tough to become a good person.
I am trying both...............................

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 10763  Foreign Exchange
I used i map like this:
map< pair<int,int> ,int >mymap;
to solve this problem.
map< pair<int,int> ,int >mymap;
to solve this problem.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 10763  Foreign Exchange
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);
}
}
/* 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);
}
}
Re: 10763  Foreign Exchange
To:lfmunoz
I don't know whether you got accepted or not.Your code fail at this input:
Input:
Output:
Your code produce NO.
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
Code: Select all
YES