574 - Sum It Up

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

Moderator: Board moderators

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

574 - too slow

Post by chetan » Wed Mar 07, 2007 7:52 pm

here is my code for 574. i know it has to be done using backtracking. but its too slow.
i think it is because of my check () function. can anybody tell me how to make it faster ??

Code: Select all

# include <iostream>
# include <vector>
# include <cstdlib>

using namespace std;
int vis[20],n,t,arr[20],flag;
vector <int> pr(20);
vector< vector<int> > v;

int check(vector<int> vi,int s)
{
	int used[1500]={0};
	
	if(v.size() == 0){
		v.push_back(vi);
		return 1;
	}
	
	for(int i=0;i<v.size();i++)
	{
		
		memset(used,0,sizeof(used));
		for(int j=0;j<v[i].size();j++){
				used[v[i][j]]=1;
		}
		
		for(int j=0;j<s;j++){
			if(used[vi[j]])
				return 0;
		}
	}
	
	v.push_back(vi);
return 1;
}

	
	
	
void backtrack(int s,int sum,int su)
{
	if(su==sum)
	{
		if(check(pr,s)){
		cout<<pr[0];
		flag = 1;
		for(int i=1;i<s;i++)
			cout<<'+'<<pr[i];
		cout<<'\n';
		}
	}
	
	for(int i=0;i<n;i++)
	{
		if(!vis[i] && su+arr[i]<=sum)
		{
			vis[i]=1;
			pr[s]=arr[i];
			backtrack(s+1,sum,su+arr[i]);
			vis[i]=0;
		}
	}
}


int main()
{
		
	while(cin>>t)
	{
		cin>>n;
		
		if(n==0)	return 0;
		flag = 0;
		memset(vis,0,sizeof(vis));
		v.clear();
		
		for(int i=0;i<n;i++)	cin>>arr[i];
		
		cout<<"Sums of "<<t<<':'<<'\n';
		backtrack(0,t,0);
		if(!flag)
			cout<<"NONE\n";
	}
return 0;
}

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

Post by chetan » Thu Mar 08, 2007 6:57 pm

plz help me out.............:(

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

Post by chetan » Wed Mar 14, 2007 1:33 pm

almost 1 week and still cant seem to get it to work.pleasssssssssssseeeeeeeee i need some help !!!!!!!!!
:cry:

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Wed Mar 14, 2007 10:20 pm

I dont think that you need to use check() function. Just do the solution with the following recusive function. Its just a template.

Code: Select all

void f(int sum,int index)
{
	if(sum==0){
		//put those numbers which makes sum=0!!!
		return;
	}
	for(int k=index;k<n;k++){
		//store the num[k] into an array
		f(sum-num[k],k);
		//remove the num[k]
	}
}
Hope this will help you. (index is used for start from that index or next index....it will save time)
Btw, you can also sort the value with non-increasing order!

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Re: 574 Sum It Up. WA can you tell me some inputs?

Post by sjn » Sun Apr 29, 2007 7:04 am

watershed wrote:

Code: Select all

INPUT:
999 1 999

CORRECT OUTPUT:
NONE

That's totally WRONG!!! :evil: :evil: :evil:

the CORRECT OUTPUT should be 999

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Sun Apr 29, 2007 7:07 am

Code: Select all

Input:
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
6 1 2
7 1 7
131 12 99 80 70 60 50 40 30 20 10 10 10 2
18 12 3 3 3 3 3 3 3 3 3 3 3 3
24 12 2 2 2 2 2 2 2 2 2 2 2 2
11 4 4 3 2 1
999 1 999
4 1 4
4 3 4 1 1
12 6 4 4 4 4 3 1 
30 11 11 10 9 8 7 6 5 4 3 2 1
4 6 4 3 2 2 1 4 
0 0

Output:
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
Sums of 6:
NONE
Sums of 7:
7
Sums of 131:
99+30+2
99+20+10+2
99+10+10+10+2
Sums of 18:
3+3+3+3+3+3
Sums of 24:
2+2+2+2+2+2+2+2+2+2+2+2
Sums of 11:
NONE
Sums of 999:
999
Sums of 4:
4
Sums of 4:
4
Sums of 12:
4+4+4
4+4+3+1
Sums of 30:
11+10+9
11+10+8+1
11+10+7+2
11+10+6+3
11+10+6+2+1
11+10+5+4
11+10+5+3+1
11+10+4+3+2
11+9+8+2
11+9+7+3
11+9+7+2+1
11+9+6+4
11+9+6+3+1
11+9+5+4+1
11+9+5+3+2
11+9+4+3+2+1
11+8+7+4
11+8+7+3+1
11+8+6+5
11+8+6+4+1
11+8+6+3+2
11+8+5+4+2
11+8+5+3+2+1
11+7+6+5+1
11+7+6+4+2
11+7+6+3+2+1
11+7+5+4+3
11+7+5+4+2+1
11+6+5+4+3+1
10+9+8+3
10+9+8+2+1
10+9+7+4
10+9+7+3+1
10+9+6+5
10+9+6+4+1
10+9+6+3+2
10+9+5+4+2
10+9+5+3+2+1
10+8+7+5
10+8+7+4+1
10+8+7+3+2
10+8+6+5+1
10+8+6+4+2
10+8+6+3+2+1
10+8+5+4+3
10+8+5+4+2+1
10+7+6+5+2
10+7+6+4+3
10+7+6+4+2+1
10+7+5+4+3+1
10+6+5+4+3+2
9+8+7+6
9+8+7+5+1
9+8+7+4+2
9+8+7+3+2+1
9+8+6+5+2
9+8+6+4+3
9+8+6+4+2+1
9+8+5+4+3+1
9+7+6+5+3
9+7+6+5+2+1
9+7+6+4+3+1
9+7+5+4+3+2
9+6+5+4+3+2+1
8+7+6+5+4
8+7+6+5+3+1
8+7+6+4+3+2
8+7+5+4+3+2+1
Sums of 4:
4
3+1
2+2



sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Sun Apr 29, 2007 9:34 am

I LIKE GN wrote:hello all...
please give me some I/O
i know it's stupid mistake!!!!
one thing
for t=0 i print
0
0+0
0+0+0
...
depending on number of zeros in X1 up to Xn
there seems to be no such case where T = 0

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

Post by chetan » Sun Jun 03, 2007 2:50 pm

hi guyz
i finally got this problem AC.
but i had to use the check function again to see if a solution has been repeated.
thus it got accepted at 2.6 secs
can anybody teach me how to write the recursive function that the solution found is unique each time????
or is there any other optimiztions required ???
please help me

rana_cse_ruet
New poster
Posts: 7
Joined: Mon Mar 05, 2007 9:59 am

Post by rana_cse_ruet » Mon Jul 16, 2007 11:06 am

PLZ give me sum critical inputs.....
I have tested all found in the board. But still WA...... :(

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Mon Jul 16, 2007 7:23 pm

input

Code: Select all

4 5 1 2 3 4 1
100 3 50 50 4
3 3 1 1 1
500 12 40 20 30 99 60 90 80 20 19 10 1 10
6 6 1 1 1 1 1 1
1 6 1 1 1 1 1 1
0 0
output

Code: Select all

Sums of 4:
4
3+1
2+1+1
Sums of 100:
50+50
Sums of 3:
1+1+1
Sums of 500:
NONE
Sums of 6:
1+1+1+1+1+1
Sums of 1:
1

rana_cse_ruet
New poster
Posts: 7
Joined: Mon Mar 05, 2007 9:59 am

Post by rana_cse_ruet » Wed Aug 15, 2007 11:33 am

Thnkx. My Program passes all those. But still WA.
Can Anybody Find any bug in my code:

Code: Select all

#include<iostream.h>
#include<stdio.h>
int sum,n,a[200],b[200],count;



int place(int k,int i)
{
	int j,s=0;
	b[k]=a[i];
	for(j=0;j<=k;j++)
	   s+=b[i];
	if(s>sum)
		return 0;
	else
		return 1;
}


int sumf(int k,int i)
{
	if(k>=n)
		return 0;

	int s,j,c=0,f;
	for(;i<n;i++)
	{
		
		if(place(k,i))
		{
		
			  
			s=0;
			for(j=0;j<=k;j++)
				s+=b[j];
			

			if(s==sum)
			{	for(j=0;j<k;j++)
				cout<<b[j]<<"+";

			cout<<b[j]<<endl;
			
			count++;
				
            c++; 
				
			s=a[i+1];
		while(s==a[i]&&i<n&&a[i]!=0)
		{	i++;s=a[i+1];}
				
			 f=0;

			if(k<n)
				f=sumf(k+1,i+1);
				

			}
            else 
			f=sumf(k+1,i+1);
		
		}
//		if(f)
		{
		s=a[i+1];	
		while(s==a[i]&&i<n)
		{i++;
		s=a[i+1];}
		}
		
		 
	}
	 
	return c;
}


void main()
{
	//freopen("574.txt","r",stdin);
	int i,j,k;
	while(cin>>sum>>n&&n)
	{
		cout<<"Sums of "<<sum<<":\n";
		count=0;
		for(i=0;i<n;i++)
			cin>>a[i];
		
		for(i=0;i<n;i++)
			for(j=i;j<n;j++)
				if(a[i]<a[j])
				{
					k=a[i];
					a[i]=a[j];
					a[j]=k;
				}

	 


		sumf(0,0);
		if(count==0)
			cout<<"NONE\n";

	}

}

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Fri Aug 24, 2007 8:30 am

in the problem statement , we can see xi>0 && xi<100,but when i test the data in the judege using :
if(xi>=100 || xi<=0){int x = 0;int y = 1/x;}

the judge tell me runtime error.


can anyone give some explanation.

I have wa for 13 times.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 574 - too slow

Post by Obaida » Sat Jan 09, 2010 7:22 am

n will be an integer between 1 and 12 (inclusive), and x1, ....., xn will be positive integers less than 100.
So i think there is no such case as:-

Code: Select all

999 1 999
I think it should be:-

Code: Select all

999 1 99
Some one please help me to get Accepted. I can't find that stupid mistake.

Code: Select all

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

bool check(vector<string>res,string st){
	for(int i=0;i<res.size();i++)if(res[i]==st)return 0;return 1;
}
void print(string res){
	for(int j=0;j<res.size();j++){
		if(res[j]=='+')printf("%c",res[j]);
		else{int p=res[j];printf("%d",p);}
	}puts("");
}

void find_set(vector<int>n,int s){
	int i,j;vector<string>res,d;vector<int>use;string temp;char t;
	for(i=n.size()-1;i>=0;i--){int k=0;
		for(j=0;j<use.size()-k;j++){
			if(use[j]+n[i]==s){
				t=n[i];temp=d[j]+t;if(check(res,temp)){res.push_back(temp);use.push_back(s);d.push_back(temp);d[d.size()-1]+="+";k++;}
			}else{use.push_back(use[j]+n[i]);t=n[i];d.push_back(d[j]+t);d[d.size()-1]+="+";k++;}
		}
		if(n[i]==s){temp=s;if(check(res,temp)){res.push_back(temp);use.push_back(s);temp=s;d.push_back(temp);d[d.size()-1]+="+";}}
		else{use.push_back(n[i]);temp=n[i];d.push_back(temp);d[d.size()-1]+="+";}
	}sort(res.begin(),res.end());printf("Sums of %d:\n",s);
	if(res.size()){
		for(i=res.size()-1;i>=0;i--){
			stack<string>stk;
			while(i>=0&&res[i][res[i].size()-1]==0){
				stk.push(res[i]);i--;
			}if(i>=0)print(res[i]);while(stk.size()){print(stk.top());stk.pop();}
		}
	}
	else puts("NONE");
}

int main(){
	int m,n;
	while(scanf("%d %d",&m,&n)==2&&n){
		vector<int>num;int t,i;
		for(i=0;i<n;i++){scanf("%d",&t);num.push_back(t);}
		sort(num.begin(),num.end());find_set(num,m);
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

sandra770
New poster
Posts: 1
Joined: Sat Jan 09, 2010 12:26 pm

6hello

Post by sandra770 » Sat Jan 09, 2010 1:23 pm

Hello.. I am baby janlac from the land of Philippines...
______________________
http://tvboxset.jimdo.com

formbit
New poster
Posts: 1
Joined: Thu Feb 11, 2010 11:30 am

Re: 574 - too slow

Post by formbit » Fri Feb 12, 2010 10:55 am

Please paste other I/O....especially those with t=0....uvatoolkit give me outuput very odd!! I'm going crazy...my program seems to work well...but the compiler tell me...WA!!! :evil:
For example...for the input:

0 2 0 0
0 5 0 0 0 0 1

What is the correct output?
Last edited by formbit on Fri Feb 12, 2010 12:32 pm, edited 2 times in total.

Post Reply

Return to “Volume 5 (500-599)”