280 - Vertex

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Fakhrul Abedin
New poster
Posts: 4
Joined: Sat Apr 02, 2005 3:10 pm
Location: Bangladesh

Runtime error for using malloc - how to do DMA in C

Post by Fakhrul Abedin » Sat Dec 27, 2008 9:13 pm

Hi,
I received Runtime error whenever I use malloc() for Dynamic memory allocation in C. The same code is accepted if I use static array. I don't know if I use malloc in wrong way. How can I do Dynamic memory allocation in C that won't yield RTL?

Here is a sample code of my malloc use

Code: Select all

	
#include<stdlib.h>
/*Allocating memory for graph*/
		G=(int **) malloc((size_t) sizeof(int *)*n);
		for(loop=1;loop<=n;loop++){
			G[loop]=(int *) malloc((size_t) sizeof(int)*n);
			nonaccessible[loop]=1;
		}
		/*End of allocation*/
Thanks.
Hopeless Programmer

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Runtime error for using malloc - how to do DMA in C

Post by mf » Sat Dec 27, 2008 9:19 pm

You allocate an array of size n (indexed 0 to n-1), but try to write to its elements with indexes 1 to n. The last one doesn't exists, and write to it probably corrupts some of allocator's internal data.
how to do DMA in C
Acronym DMA usually stands for "Direct Memory Access", a thing from OS and hardware worlds.

Fakhrul Abedin
New poster
Posts: 4
Joined: Sat Apr 02, 2005 3:10 pm
Location: Bangladesh

Re: Runtime error for using malloc - how to do DMA in C

Post by Fakhrul Abedin » Sun Dec 28, 2008 10:06 am

Thanks. Yes DMA is an OS staff, I can remember, but here I used it (erroneously) as a shortcut of dynamic memory allocation, not as the acronym of Direct Memory Access.

Your point is right but you will find the RTL even if you use index range between 0 - (n-1) or allocate memory n+1.

My question is if at all malloc funtion can be used in UVA online judege. Or what is the way of dynamic memory allocation in UVA O J.

Regards
Hopeless Programmer

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Runtime error for using malloc - how to do DMA in C

Post by mf » Sun Dec 28, 2008 11:19 am

Yes, malloc() is allowed.

The way you use it is correct, if you either fix your loop to go from 0 to n-1, or allocate n+1 elements.

Fakhrul Abedin
New poster
Posts: 4
Joined: Sat Apr 02, 2005 3:10 pm
Location: Bangladesh

Re: Runtime error for using malloc - how to do DMA in C

Post by Fakhrul Abedin » Mon Dec 29, 2008 6:56 pm

Thank you big brother for your great info.

I am posting here the code for 280 - Vertex where I used malloc, in Linux I don't find any runtime crash but after submission i got RTL. Would you kindly review and help me to find my fault?

Code: Select all


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

short nonaccessible[101];
int **G,count;

void  DFS_VISIT(int n,int i,int adj[]){
	int v;
	for(v=1;v<=n;v++){
		if( !(adj[v]^1) ){
			if( !(nonaccessible[v]^1) ){
				nonaccessible[v]=0;
				count++;
				DFS_VISIT(n,v,G[v]);
			}
		}
	}
}

main(){
	int n,loop,i,j,visited;
	while(scanf("%d",&n) && n){
		/*Allocating memory for graph*/
		G=(int **) malloc((size_t) sizeof(int *)*(n+1) );
		for(loop=1;loop<=n;loop++){
			G[loop]=(int *) malloc((size_t) sizeof(int)*(n+1) );
			nonaccessible[loop]=1;
		}
		/*End of allocation*/
		
		/*Generating Graph*/
		scanf("%d",&i);
group:
		while(scanf("%d",&j) && j){
			G[i][j]=1;
		}
		if(scanf("%d",&i) && i)
			goto group;		
		/*End Generating Graph*/

		/*Input of nodes for investigation*/
		scanf("%d",&j);
		/*Start of investigation*/
		while(j--){
			scanf("%d",&i);
			count=0;
			DFS_VISIT(n,i,G[i]);
			printf("%d",n-count);
			for(loop=1;loop<=n;loop++)
				if(nonaccessible[loop])
					printf(" %d",loop);
			printf("\n");
			for(loop=1;loop<=n;loop++)
				nonaccessible[loop]=1;
		}/*End of Investigation*/
	}
}
Hopeless Programmer

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Runtime error for using malloc - how to do DMA in C

Post by mf » Mon Dec 29, 2008 10:38 pm

You don't need malloc there, "int G[101][101];" will do just fine.

If you still want to use malloc, then don't forget that you have to free() every piece of memory that you've malloc()ed.

User avatar
theharshest
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

Re: 280 why TLE?

Post by theharshest » Sun Feb 22, 2009 12:57 am

I am getting TLE for following code :(
Please help

Code: Select all

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int main()
{
	int n,t,k,x,y;
	vector< vector<int> > mat; // adjacency matrix
	vector<bool> vis; // visited nodes

	cin>>n;

	while(n!=0)
	{
		vis.resize(n,0);
		scanf("%d",&t);
		mat.resize(n);
		for(int i=0;i<n;i++)
			mat[i].resize(n,-1);	


		while(t!=0)
		{
			scanf("%d",&k);
			while(k!=0)
			{
				mat[t-1][k-1]=1;
				scanf("%d",&k);
			}
			scanf("%d",&t);
		}

		scanf("%d",&x);

		while(x--)
		{
			for(int i=0;i<n;i++)
				vis[i]=0;	

			scanf("%d",&y);

			stack<int> s;

			for(int i=0;i<n;i++)
				if(mat[y-1][i]==1)
				{
					s.push(i);
					break;
				}

			// applying dfs
			while(!s.empty())
			{				
				int tmp=s.top();
				vis[tmp]=1;
				s.pop();
		
				for(int i=0;i<n;i++)
					if(mat[tmp][i]==1 && !vis[i])
						s.push(i);	
			}

			vector<int> ans; // stores all unvisited nodes

			for(int i=0;i<n;i++)
				if(!vis[i])
					ans.push_back(i);

			printf("%d",(int)ans.size());

			sort(ans.begin(),ans.end());

			for(int i=0;i<ans.size();i++)
				printf(" %d",ans[i]+1);
			printf("\n");
		}	
		
		scanf("%d",&n);
	}
}
"if u r goin thru hell, keep goin"

shreyarora
New poster
Posts: 1
Joined: Sat Feb 28, 2009 10:24 pm

there is runtime error(SIGSEGV) is coming in my code how can

Post by shreyarora » Sat Feb 28, 2009 10:43 pm

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
int main()
{
int n,i,*c,l,x,k,w=0,j;
long int p,q,args;
char *a,*b,temp;
scanf("%d",&n);
a=(char *)malloc(1000*(sizeof(char)));
b=(char *)malloc(1000*sizeof(char));
c=(int *)malloc(10000*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%s",a);
scanf("%s",b);
l=strlen(a);
q=l/2;
x=strlen(b);
p=x/2;
for(j=0,k=(l-1);j<q;j++,k--)
{
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
for(j=0,k=(x-1);j<p;j++,k--)
{
temp=b[j];
b[j]=b[k];
b[k]=temp;
}

p=atol(a);
q=atol(b);
args=(p+q);
while(args!=0)
{
k=(int)args%10;
c[w]=k;
args=args/10;
w++;
}
c[w]='^';
w++;

}
c[w]='$';
for(i=0;;)
{
if(c==0)
i++;
else
break;
}
for(i=i;c!='$';i++)
{
if(c=='^')
printf("\n");
else
printf("%d",c);
}
return 0;
}

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 280 Vertex TLE Help!!

Post by calicratis19 » Fri Aug 14, 2009 8:05 pm

AC
Last edited by calicratis19 on Mon Aug 24, 2009 8:07 pm, edited 1 time in total.
Heal The World

looserdgr8
New poster
Posts: 5
Joined: Sun Aug 23, 2009 2:07 am
Location: Sust, Sylhet

Re: 280 Vertex WA Help!!

Post by looserdgr8 » Sun Aug 23, 2009 2:23 am

Please someone help me. I have run every I/O in this forum. Every thing seems okay. But still i get wrong answer. I use BFS algorithm.
Here is my code:

Code: Select all


Accepted. Array size upgraded to 500
Last edited by looserdgr8 on Sun Sep 06, 2009 4:13 am, edited 2 times in total.

looserdgr8
New poster
Posts: 5
Joined: Sun Aug 23, 2009 2:07 am
Location: Sust, Sylhet

Re: 280 Vertex WA Help!!

Post by looserdgr8 » Tue Aug 25, 2009 4:36 pm

Please anyone H-E-L-P me. I am now frustrated. Anyone check my code please............>>>

looserdgr8
New poster
Posts: 5
Joined: Sun Aug 23, 2009 2:07 am
Location: Sust, Sylhet

Re: 280 Vertex WA Help!!

Post by looserdgr8 » Fri Aug 28, 2009 11:38 pm

Anyone please help me.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 280 Vertex WA Help!!

Post by calicratis19 » Wed Sep 02, 2009 3:38 pm

@looserdgr8 increase the size of the defined constant 'size'. u will get ac.
Heal The World

looserdgr8
New poster
Posts: 5
Joined: Sun Aug 23, 2009 2:07 am
Location: Sust, Sylhet

Re: 280 Vertex WA Help!!

Post by looserdgr8 » Fri Sep 04, 2009 12:38 am

Thanx calicratis19. Its AC

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 280 Vertex WA Help!!

Post by calicratis19 » Fri Sep 04, 2009 7:59 pm

@looserdgr8, u should remove your code.thanks.
Heal The World

Post Reply

Return to “Volume 2 (200-299)”