Page 3 of 4
574 - too slow
Posted: Wed Mar 07, 2007 7:52 pm
by chetan
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;
}
Posted: Thu Mar 08, 2007 6:57 pm
by chetan
plz help me out.............
Posted: Wed Mar 14, 2007 1:33 pm
by chetan
almost 1 week and still cant seem to get it to work.pleasssssssssssseeeeeeeee i need some help !!!!!!!!!
Posted: Wed Mar 14, 2007 10:20 pm
by asif_rahman0
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!
Re: 574 Sum It Up. WA can you tell me some inputs?
Posted: Sun Apr 29, 2007 7:04 am
by sjn
watershed wrote:Code: Select all
INPUT:
999 1 999
CORRECT OUTPUT:
NONE
That's totally WRONG!!!
the CORRECT OUTPUT should be 999
Posted: Sun Apr 29, 2007 7:07 am
by sjn
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
Posted: Sun Apr 29, 2007 9:34 am
by sjn
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
Posted: Sun Jun 03, 2007 2:50 pm
by chetan
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
Posted: Mon Jul 16, 2007 11:06 am
by rana_cse_ruet
PLZ give me sum critical inputs.....
I have tested all found in the board. But still WA......
Posted: Mon Jul 16, 2007 7:23 pm
by ayeshapakhi
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
Posted: Wed Aug 15, 2007 11:33 am
by rana_cse_ruet
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";
}
}
Posted: Fri Aug 24, 2007 8:30 am
by lena
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.
Re: 574 - too slow
Posted: Sat Jan 09, 2010 7:22 am
by Obaida
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:-
I think it should be:-
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;
}
6hello
Posted: Sat Jan 09, 2010 1:23 pm
by sandra770
Hello.. I am baby janlac from the land of Philippines...
______________________
http://tvboxset.jimdo.com
Re: 574 - too slow
Posted: Fri Feb 12, 2010 10:55 am
by formbit
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?