## 562 - Dividing Coins

Moderator: Board moderators

### Re: 562 - Dividing Coins

why wa i have cant understand
Code: Select all
`//C++#include<iostream>#include<algorithm>using namespace std;#define max_(a,b)(a>b?a:b)int a[110];int mark[10000][10000];int store[10000][10000];int n,t;int dp(int i, int w){   if(i==0 || w==0)      return 0;   else if(mark[i][w]==t)      return store[i][w];   int res;   if(a[i]<=w)   {      res=max_(dp(i-1,w),dp(i-1,w-a[i])+a[i]);   }   else      res=dp(i-1,w);   mark[i][w]=t;   store[i][w]=res;   return res;}int main(){   int i,w,cs,tt,sum,x;   //freopen("1.txt","r",stdin);   cin>>tt;   for(cs=1;cs<=tt;cs++)   {      t++;      cin>>n;      sum=0;      for(i=1;i<=n;i++)      {         scanf("%d",&a[i]);         sum+=a[i];      }      w=sum/2;      x=dp(n,w);      printf("%d\n",(sum-2*x));   }}`

plz help me. im getting frustrated..
plz...
md_yusuf
New poster

Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 562 - Dividing Coins

you should get memory limit exceed.How much memory you used-

Code: Select all
`int mark[10000][10000];int store[10000][10000];`

Its a simple 1-dimentional DP problem.look at the sample input
4
1 2 4 6

Declare an array A[50000] because highest value may be 100*500=50000 and and fill it by 0.

as sum is odd you can't divide it evenly,so look for number closet to half-6.
so try to make sum=6 by adding some element.

For 1st element we have sum- 1. set A[1]=1;
For 2nd element we have sum-2,(2+1=3).set A[2]=1,A[3]=1.
For 3rd element we have sum-4,(1+4=5),(2+4=6) stop as you find 6 from element 2,4=6 and other set certainly contain=13-6=7.

SO diff is 1.

Hope you understand .
Experienced poster

Posts: 136
Joined: Sat Nov 29, 2008 8:01 am

### Re: 562 - Dividing Coins

thx via. i cant understand why im getting wa. I should get re or ce.. bt making the the arry mark[101][25001] and mark[101][25001] get accepted its too weird to me.
md_yusuf
New poster

Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 562 - Dividing Coins

I got a wa for a simple but tricky case.
Code: Select all
`10`

output is 0

Code: Select all
`1131 4 6 8 5 3 4 7 5 3 5 2 100`

ans: 47
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### Re: 562 - Dividing Coins

Can anyone help me?

#include<iostream>

using namespace std;

int main()
{
int n;
cin>>n;
int value=0;
int diff;

for(int i=1;i<=n;i++)
{
int coin_no;
cin>>coin_no;

for(int x=1;x<=coin_no;x++)
{
int val;
cin>>val;
value=value+val;
}
diff=value%2;
cout<<"\n"<<diff;

}

return 0;
}
mdpallob
New poster

Posts: 3
Joined: Wed May 18, 2011 4:11 pm

### Re: 562 - Dividing Coins

Hello
My code passing all the input found here in this board and also my hand-generated one's(compared with toolkit output).I used simple DP here.
I worked like..
1)Sum up all the coin first
2)Then set S=sum/2
3)Now I used 0-1 knapsack here.That is Fill knapsack with size S as maximum as possible
4)then output sum-2*p[n][S]
But I'm getting WA..Here is my code
Code: Select all
`//Got Accepted.`

Edit:
A silly Bug.Algorithm was okay.allocated memory less than program need..wondered to see no one here in this board to help....its dead one..
Imti
Learning poster

Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm

### Re: 562 - Dividing Coins

mr. mdpallob
What you did???You really understood what problem wants??I don't think so
Your algorithm is totally wrong.Your code always produce minimal difference as 0 or 1.But answer may be greater than 0 or 1 too. Read carefully problem statement again and try learning Dynamic programming technique.
Imti
Learning poster

Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm

### Re: 562 - Dividing Coins

I used 0-1 knapsack to solve this problem.
can anyone find any bug in my code:
Code: Select all
`removed after AC`
Last edited by mostafiz93 on Mon May 28, 2012 5:41 pm, edited 1 time in total.
mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 562 - Dividing Coins

see I/O #7 at http://ideone.com/XgQ97, AC output is 1.
brianfry713
Guru

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

### Re: 562 - Dividing Coins

thanks brianfry!
got AC.
mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 562 - Dividing Coins

Runtime error. Why????
Code: Select all
`AC`
Last edited by shopnobaj_raju on Sat Jun 16, 2012 2:55 pm, edited 1 time in total.
shopnobaj_raju
New poster

Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

### Re: 562 - Dividing Coins

For one thing, this declares more memory than you need to solve this problem.
long int coins[102],opt[102][25010];

for(i=0;i<103;i++)
for(j=0;j<25011;j++) opt[i][j]=-100;
brianfry713
Guru

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

### Re: 562 - Dividing Coins

Thanks
shopnobaj_raju
New poster

Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

### Re: 562 - Dividing Coins

I try your input and got right
but still get wa on oj
i don't know why==
plz help me
3ks

here is my codes:

#include<stdlib.h>
#include<stdio.h>
int min(int a,int b) {if(a>b)return b;return a;}
int abs(int a) {if(a>0)return a;return -a;}
int f(int sum,int a) {return abs(sum-a-a);}
int fmin(int a,int b,int sum)
{
int res=min(f(sum,a),f(sum,b));
if(res==f(sum,a))return a;
return b;
}
int main()
{
int k,z;
scanf("%d",&z);
for(k=1;k<=z;k++)
{
int m;
scanf("%d",&m);
int i,j,a[110],sum=0;
int dp[110][110];
for(i=1;i<=m;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for(i=0;i<=m;i++)for(j=0;j<=m;j++)dp[i][j]=0;
for(j=1;j<=m;j++)
{
int mm=a[1];
for(i=2;i<=j;i++)mm=fmin(mm,a[i],sum);
dp[1][j]=mm;
}
for(i=2;i<=m;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]=fmin(dp[i-1][j-1]+a[i],dp[i-1][j],sum);
}
}
int res=dp[m][1];
for(i=2;i<=m;i++)res=fmin(res,dp[m][i],sum);
printf("%d\n",f(sum,res));
}
// return main();
return 0;}
connor
New poster

Posts: 4
Joined: Wed Jan 09, 2013 1:41 pm

### Re: 562 - Dividing Coins

Input:
Code: Select all
`110500 499 500 488 467 500 499 488 499 487`
AC output 1
brianfry713
Guru

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

PreviousNext