10954 - Add All

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

Moderator: Board moderators

tom76925
New poster
Posts: 2
Joined: Tue Aug 12, 2008 3:56 am

Re: 10954 - Add All

Post by tom76925 » Tue Aug 12, 2008 7:57 am

Oh~sorry... I just forgot to refresh the ans[]
It's so idiot...
If it add

Code: Select all

memset(ans,0,sizeof(ans));
will got AC

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

10954 - Add All Getting TLE !!

Post by kangroo » Fri Sep 19, 2008 8:28 am

problem solved...
used STL <map> and got AC...I think the "STL sort() algortihm" each time in the loop led to TLE...
thanks

Fluffymoo
New poster
Posts: 7
Joined: Wed Oct 15, 2008 5:05 pm

Runtime Error problem,

Post by Fluffymoo » Wed Oct 15, 2008 5:20 pm

Hello there,
i am new to the whole c++ language and now i hit a problem i am not able to figure out.
It appeared to me while i tried to solve 10954-Add All problem. Everything worked on my computer and my code solved all test cases i could think off in no time and correctly. But when i submitted that code i got "runtime error" message, and i am not able to figure out why.
-I do not use any array.
-I do not divide or multiply, only add.
-I use my own defined structure(class) and work with pointers.
My guess is there is some faulty behaviour with me using pointers, but because i am really new to this stuff i might not realize where that problem could be. It could also be caused by compiler differencies, in which case i might need to rework my solution completely.
I will describe how my program works:
-It reads numbers and put them into a binary tree(self defined), while adding numbers to the tree i keep stored the adress of the leaf with min value
-when i want to count what i am supposed to count i get min leaf, store its value, remove that leaf(after which i find new min leaf), remove one more min leaf, sum those two leaves, and put the sum as a new element to the tree while saving sum into a final output value. This continues until there are no leaves basically
So here is my code(dont laugh at it please:P)

Code: Select all

#include <stdio.h>

class ELEMENT
{
public:
	int value;
	ELEMENT *left,*right,*daddy;
	ELEMENT()
	{
		left=0;
		right=0;
		daddy=0;
		value=0;
	}
};

class TREE
{
public:
	void Put(ELEMENT *where_to_put_it,ELEMENT *branch)
	{
		if((where_to_put_it->value)>(branch->value))
		{
			if((branch->right)!=0)
			{
				Put(where_to_put_it,(branch->right));
			}
			else
			{
				branch->right=where_to_put_it;
				where_to_put_it->daddy=branch;
			}
		}
		else
		{
 			if((branch->left)!=0)
			{
				Put(where_to_put_it,(branch->left));
			}
			else
			{
				branch->left=where_to_put_it;
				where_to_put_it->daddy=branch;
				if(min->value>=where_to_put_it->value)
                {
                     min=where_to_put_it;
                }
			}
		}
		
	}
	void FindMin(ELEMENT *subtree)
	{
        delete min; 
		ELEMENT *horse;
		horse=subtree;
		while(horse->left!=0)
			horse=horse->left;
		min=horse;
	}
   	ELEMENT *root;
   	ELEMENT *min;
    int number_of_elements;
	TREE()
	{
		root=0;
		number_of_elements=0;
	}
	TREE(int in)
	{
		root=0;
		number_of_elements=0;
		Add(in);
	}
	void Add(int in)
	{
		ELEMENT *add;
		add=new ELEMENT;
		add->value=in;
		if(root!=0)
		{
			Put(add,root);
		}
		else
		{
       		root=add;
			min=add;
		}
		number_of_elements++;
	}
	int Min(void)
    {
        return (*min).value;
    }
	void RemoveMin()
	{
        if(number_of_elements==1)
        {
            root=0;
        }
        else
		if(root==min)
		{
            root=root->right;
			FindMin(root);
		}
		else
		{
			if(min->right!=0)
			{
				min->daddy->left=min->right;
				min->right->daddy=min->daddy;
				FindMin(min->right);
			}
			else
			{
				min->daddy->left=0;
				min=min->daddy;
			}
		}
		number_of_elements--;
	}
};

int computeExp(TREE *tree)
{
    int out=0, help=0;
    while(tree->number_of_elements>1)
    {
           help=tree->Min();
           tree->RemoveMin();                       
           help+=tree->Min();
           tree->RemoveMin();
           out+=help;
           tree->Add(help);
           help=0;                       
    }
    return out;
}

int main()
{
	short in=1;
    int b;

    while(in>0)
	{
        TREE tree;
        scanf("%d",&in);
        if (in>0)
        {
            for (int a=(in-1);a>=0;a--)
            {
                scanf("%d",&b);
                tree.Add(b);
            }
            in=1;
            printf("%d\n",computeExp(&tree));
        }
        delete &tree;
    }
	return 0;
}
If there is anyone willing to help newbie out, thank you :D

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

Re: Runtime Error problem,

Post by mf » Wed Oct 15, 2008 6:07 pm

When I compile your program, I get this warning:
p.cc: In function ‘int main()’:
p.cc:149: warning: format ‘%d’ expects type ‘int*’, but argument 2 has type ‘short int*’
You probably should have used 'int' instead of 'short' on line 143.

When I fix that, and run your program on the sample input, it dies on line 160: "delete &tree;". Apparently you don't quite understand how C++ manages memory. 'tree' is a local variable, the compiler automatically allocates memory for it on the program's stack, and deallocates it when it goes out of scope (i.e. at the end of each iteration of the while loop). Operators new and delete work with heap memory which is very different from stack. You can do 'delete x;' if and only if x was the result of a previous 'new SomeType()'.

If you actually wanted that line to delete all the instances of class ELEMENT which you've allocated at line 78, well, you should've written a recursive procedure which will walk down your tree and delete every one of them individually. And you should call this procedure in the destructor of class TREE.

-I use my own defined structure(class) and work with pointers.
Don't reinvent the wheel, use the existing code when possible. In this problem, for example, you could've used STL's std::set instead of your own tree.

Fluffymoo
New poster
Posts: 7
Joined: Wed Oct 15, 2008 5:05 pm

Thank you

Post by Fluffymoo » Wed Oct 15, 2008 6:38 pm

Thanks mf,
Yes you are quite right i do not understand how memory works, i knew that functions free memory of their local variables when they finish, but didnt know it aplies to cycles aswell(and at the same time i use for(){} regularly, i am dumb :D)

About reinventing the wheel, you are right. But i know i need to practise and learn how things work and i wanted to be able to code a "dynamic" structure on my own. I just find it fun.

Thank you!

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

Re: 10954 - Add All

Post by Shafaet_du » Fri Oct 22, 2010 10:46 am

I used STL list and insertion sort and got accepted. this samples should help you:

Code: Select all

5
10 20 30 40 50
7
100 9999 2355 7777 8888 2345 1234
10
12 45 23 67 23 9 56 234 45 65
12
9999 9998 88888 0 88888 88898 66666 55555 4324 2356 5676 9988
6
9 9 9 9 9 9
40
99999 99999 99999 99999 99999 99999 99999 99999 99999 99999
99998 99998 99998 99998 99998 99998 99998 99997 99997 19998
99995 99995 99995 99995 99995 99995 99995 99995 99995 99995
59995 99995 99595 99995 39995 99995 99995 99995 99995 99995
0
output:

Code: Select all

330
76443
1612
1221996
144
20476861
happy programming!

Md. Mijanur Rahman
New poster
Posts: 9
Joined: Thu Nov 13, 2008 2:08 pm

Re: 10954 - Add All

Post by Md. Mijanur Rahman » Sat Jan 15, 2011 9:08 pm

Runtime Error why??? I'm just dying with this problem. Someone Plz help me !!! :(

Code: Select all

#include<stdio.h>
long int partition(long int m,long int p);
void interchange(long int i,long int j);
void quicksort(long int p,long int q);
long int a[5500],num;
int main()
{
  long int carry,sum,total,i; 
  while(scanf("%ld",&num)==1)
  {
	  if(num==0)
		        break;
	  for(i=1;i<=num;i++)
		       scanf("%ld",&a[i]);
	 quicksort(1,num);						   
     carry=a[1];
	 total=0;
	 for(i=2;i<=num;i++)
	 {
        sum=carry+a[i];
		a[i]=sum;
		quicksort(i,num);
	    carry=a[i];
		total+=sum;
	 }
	 printf("%ld\n",total);
		              
  }
return 0;
}
void quicksort(long int p,long int q)
   {        long int j;
	    if(p<q)
	    {
	     j=partition(p,q+1);
	     quicksort(p,j-1);
	     quicksort(j+1,q);
	     }
    }
  long int partition(long int m,long int p)
  {
     long int v,i,j,temp;
     v=a[m];i=m;j=p;
  do
  {   do
	 {
		i=i+1;
	 }while(a[i]<v);
	     do
		 {
		 j=j-1;
		 }while(a[j]>v);
		 if(i<j)
		 {
		  temp=a[i];
          a[i]=a[j];
          a[j]=temp; 
		 }
    }while(i<j);
    a[m]=a[j];
    a[j]=v;
    return j;
  }

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10954 - Add All

Post by zobayer » Tue Mar 15, 2011 1:26 pm

Hello,
This problem is commonly known as Huffman Coding (http://en.wikipedia.org/wiki/Huffman_coding)
I used simply a priority_queue to solve this one.
You should not always say what you know, but you should always know what you say.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10954 - Add All

Post by DD » Fri Apr 01, 2011 6:13 am

zobayer wrote:Hello,
This problem is commonly known as Huffman Coding (http://en.wikipedia.org/wiki/Huffman_coding)
I used simply a priority_queue to solve this one.
Thanks for your hint. I start to appreciate the clever cover of this problem. :)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 10954 - Tricky / Cheat

Post by shaon_cse_cu08 » Wed Aug 24, 2011 6:17 pm

The problem clearly state's..." N positive integers (all are less than 100000)"
But the Input file include's "0"... "There is a huge difference between POSITIVE & NON-NEGATIVE" I think problem setter had forgotten this fact...

Or Intentionally Cheated :P :-? :lol: :evil:
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Mon Apr 16, 2012 8:19 pm

Is there anyone can tell me why my code is wrong?

Code: Select all

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin >> n;
	while (!n == 0){
		int a[5001];
		int cost = 0;
		int sum = 0;
		for (int i = 1; i <= n; i++){
			cin >> a[i];
		}
		if (n == 2)
			cout << a[1] + a[2];
		else{
			sort(a, a + n);
			cost = a[1] + a[2];
			for (int i = 3; i<= n; i++){
				sum += cost;
				cost += a[i];
			}
			sum += cost;
			cout << sum;
		}
		cin >> n;
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Tue Apr 17, 2012 1:07 am

You're not printing any newlines.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Tue Apr 17, 2012 5:50 pm

brianfry713 wrote:You're not printing any newlines.
It's not important.I gave wrong answers in my own computer.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Tue Apr 17, 2012 10:36 pm

The proper placement of newlines are important if you want to get AC.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Wed Apr 18, 2012 8:28 am

brianfry713 wrote:The proper placement of newlines are important if you want to get AC.

Code: Select all

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
   int n;
   cin >> n;
   while (!n == 0){
      int a[5001];
      int cost = 0;
      int sum = 0;
      for (int i = 1; i <= n; i++){
         cin >> a[i];
      }
      if (n == 2)
         cout << a[1] + a[2];
      else{
         sort(a, a + n);
         cost = a[1] + a[2];
         for (int i = 3; i<= n; i++){
            sum += cost;
            cost += a[i];
         }
         sum += cost;
         cout << sum << endl;
      }
      cin >> n;
   }
   return 0;
}
And It doesn't work at all.

Post Reply

Return to “Volume 109 (10900-10999)”