## 574 - Sum It Up

Moderator: Board moderators

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

### 574 - too slow

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,n,t,arr,flag;
vector <int> pr(20);
vector< vector<int> > v;

int check(vector<int> vi,int s)
{
int used={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;
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
plz help me out............. chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
almost 1 week and still cant seem to get it to work.pleasssssssssssseeeeeeeee i need some help !!!!!!!!! asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 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?

watershed wrote:

Code: Select all

``````INPUT:
999 1 999

CORRECT OUTPUT:
NONE

``````
That's totally WRONG!!!   the CORRECT OUTPUT should be 999

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

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:
I LIKE GN wrote:hello all...
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
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 ???

rana_cse_ruet
New poster
Posts: 7
Joined: Mon Mar 05, 2007 9:59 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
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
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,b,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
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

### Re: 574 - too slow

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``

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

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

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!!! 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.