10954 - Add All

[tom76925]

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]

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

[Fluffymoo]

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

[mf]

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]

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 )

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]

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]

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]

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.

[DD]

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.

[shaon_cse_cu08]

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

[Hasselli]

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]

You're not printing any newlines.

[Hasselli]

You're not printing any newlines.

It's not important.I gave wrong answers in my own computer.

[brianfry713]

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

[Hasselli]

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.