discrepancies in voter list ...wrong ans ...why??

keshav_1994 · January 30, 2015, 8:16pm

http://www.codechef.com/viewsolution/6047657

#include <iostream>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int arr [50000] , final[50000];

struct NODE
{
	int data;
	NODE *node;
} *start = NULL , *end ;

void insert()
{
	NODE *new_node = (NODE*)malloc(sizeof( NODE ));
	
	scanf("%d",&new_node->data);
	if(start == NULL)
	{
		start = new_node;
		start->node = NULL;
		end = start ; 
	}
	else
	{
		//struct NODE *temp = start;
		//while( temp->node !=NULL)
		//	temp = temp->node;
		
		end->node = new_node;
		end=end->node;
		end->node = NULL;
	}
}

int main() {
	
	int n1,n2,n3 , test ,j=0 ,k=0 ,i;
	scanf("%d %d %d",&n1,&n2,&n3);

	
	for( i=0 ; i<n1; i++)
	{
		insert();
	}
	
	struct NODE *temp,*par ; bool found;
	
	par=start;
	temp =start->node;
	for(int i=0 ; i < n2 ; i++)
	{
		scanf("%d" , &test);
		
		found =false;
		if( start->data == test )
		{
			found = true;
			final[j] = test;
			j++;
			temp = start;
			start = start->node;
			delete temp;
			par=start;
			temp =start->node;
		}
		else if( test > start->data)
		{
			while( temp!=NULL && test >= temp->data)
			{
				if(temp->data == test)
				{
					//printf( " found \n");
					found = true;
					final[j] = test;
					j++;
					par->node=temp->node;
					delete temp;
					temp=par->node;
					break;
				}
				par=temp;
				temp = temp->node;
			}
		}
		//printf("%d\n", found == false);
		if(found == false)
		{
			//printf("not found\n");
			arr[k] = test;
			//printf("not found %d %d\n",arr[k],k);
			k++;
		}
		
	}
	
	int l=0;
	par=start;
	temp =start->node;
	for(int i=0 ; i < n3 ; i++)
	{
		scanf("%d" , &test);
		
		found =false;
		
		if(start != NULL && test >= start->data)
		{
			if( start->data == test )
			{
				found = true;
				final[j] = test;
				j++;
				temp = start;
				start = start->node;
				delete temp;
				par=start;
				temp =start->node;
			}
			else
			{
				while( temp!=NULL && test >= temp->data )
				{
					if(temp->data == test)
					{
						found = true;
						final[j] = test;
						j++;
						par->node=temp->node;
						delete temp;
						break;
					}
					par=temp;
					temp = temp->node;
				}
			}
		}
			
		if(found == false && arr[l] <= test)
		{
			while(l<k)
			{
					if(arr[l] == test)
					{
						//printf("found placed at %d\n",l);
						final[j] = test;
						j++;
						break;
					}
				
				
				l++;	
			}
		}
	}
	
	printf("%d\n",j);
	sort(final,final+j);
	for(int i=0;i<j;i++)
	{
		printf("%d\n", final[i]);
	}
	
	return 0;
}

damn_me · January 30, 2015, 10:40pm

Why are you doing so much in a very simple question? It can simply be done using this r refer this discussion here. The reason of your wrong answer is probably in this thread(the second link).

Your code gives wrong answer for cases like this:

2 3 2
500003 1234 
500002 500004 5999
500003 1234

i.e. cases in which id>50000, it’s given that n1,n2,n3<=500000, not the ids!!

keshav_1994 · January 31, 2015, 10:45am

i know , but before looking into the solution i chose this way … no doubt from now on i ll follow your way of doing it …
but still i want to know why my code is showing the wrong ans ??

i ran each test case … even i reviewd my code many times but nothing budged

keshav_1994 · February 5, 2015, 10:32pm

#include
#include <stdlib.h>
#include

using namespace std;

int arr [10000001] , final[10000001];

struct NODE
{
int data;
NODE *node;
} *start = NULL , *end ;

void insert()
{
NODE new_node = (NODE)malloc(sizeof( NODE ));

scanf("%d",&new_node->data);
if(start == NULL)
{
	start = new_node;
	start->node = NULL;
	end = start ; 
}
else
{
	//struct NODE *temp = start;
	//while( temp->node !=NULL)
	//	temp = temp->node;
	
	end->node = new_node;
	end=end->node;
	end->node = NULL;
}

}

int main() {

int n1,n2,n3 ,j=0 ,k=0 ,i;
int test;
scanf("%d %d %d",&n1,&n2,&n3);


for( i=0 ; i<n1; i++)
{
	insert();
}

struct NODE *temp,*par ; bool found;

par=start;
temp =start->node;
for(int i=0 ; i < n2 ; i++)
{
	scanf("%d" , &test);
	
	found =false;
	if( start->data == test )
	{
		found = true;
		final[j] = test;
		j++;
		temp = start;
		start = start->node;
		delete temp;
		par=start;
		temp =start->node;
	}
	else if( test >= temp->data)
	{
		while( temp!=NULL )
		{
			if(temp->data == test)
			{
				//printf( " found \n");
				found = true;
				final[j] = test;
				j++;
				par->node=temp->node;
				delete temp;
				temp=par->node;
				break;
			}
			par=temp;
			temp = temp->node;
		}
	}
	//printf("%d\n", found == false);
	if(found == false)
	{
		//printf("not found\n");
		arr[k] = test;
		//printf("not found %d %d\n",arr[k],k);
		k++;
	}
	
}

int l=0;
par=start;
temp =start->node;
for(int i=0 ; i < n3 ; i++)
{
	scanf("%d" , &test);
	
	found =false;
	
	if(start != NULL && test >= start->data)
	{
		if( start->data == test )
		{
			found = true;
			final[j] = test;
			j++;
			temp = start;
			start = start->node;
			delete temp;
			par=start;
			temp =start->node;
		}
		else
		{
			while( temp!=NULL && test >= temp->data )
			{
				if(temp->data == test)
				{
					found = true;
					final[j] = test;
					j++;
					par->node=temp->node;
					delete temp;
					break;
				}
				par=temp;
				temp = temp->node;
			}
		}
	}
		
	if(found == false && arr[l] <= test)
	{
		while(l<k)
		{
				if(arr[l] == test)
				{
					//printf("found placed at %d\n",l);
					final[j] = test;
					j++;
					break;
				}
			
			
			l++;	
		}
	}
}

printf("%d\n",j);
sort(final,final+j);
for(int i=0;i<j;i++)
{
	printf("%d\n", final[i]);
}

return 0;

}

damn_me · January 31, 2015, 7:59pm

Check the edit above in the answer!!

keshav_1994 · February 1, 2015, 9:44am

i know , but before looking into the solution i chose this way … no doubt from now on i ll follow your way of doing it … but still i want to know why my code is showing the wrong ans ??

i ran each test case … even i reviewd my code many times but nothing budged

damn_me · February 1, 2015, 11:23am

Please see carefully, I am telling you the case above for which your code fails and gives RTE.

keshav_1994 · February 3, 2015, 9:43pm

i got u …that the range of int is till 32627… but when i changed it to unsigned int ie. to range 65255 >50000 … it is still showing RTE why???

keshav_1994 · February 3, 2015, 9:47pm

ans the link of solution you have given they are also using int but the solution is running good whyyyyyy ???

damn_me · February 3, 2015, 10:09pm

No, you’re understanding wrong. WHat does the declaration int a[10]mean? It means that we can access all elements frm a[0] to a[9], but accessing a[10] or any other index is not possible because we are accessing the memory we haven’t allocated. Similarly in your code, you are declaring an array of 50,000. In this manner you are assuming that ids are maximum upto 50,000 which is not true as per the question.

keshav_1994 · February 5, 2015, 8:25pm

so you mean to say is i should declare the array of 50001 size ???

keshav_1994 · February 5, 2015, 8:30pm

and in the question they have given any constraint on values of ID’s !!!
for such a large values like you have given 500004 it is showing run time error …

damn_me · February 5, 2015, 8:32pm

Can’t it be 50004 or 50005? Declare it to be of maximum size 10000001, it’ll work then. Declare globally

keshav_1994 · February 5, 2015, 8:33pm

can you please make corrections in my code and send it ??? it would be a great help …!!!1

damn_me · February 5, 2015, 8:34pm

The range of 50000 is given for the “Number of ids in the list”, not the range of id. You are getting rte because you are accessing an undefined location. See the comment by admin on the same page “No, ID can be any number that fits in a 4 byte signed integer.”

keshav_1994 · February 5, 2015, 10:32pm

I changed my array to 10000001 still it didnt work for the test cases you have given… see the code below in my comment