562 - Dividing coins

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

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

Re: 562 - Dividing Coins

Post by md_yusuf » Fri Jan 14, 2011 10:02 am

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 562 - Dividing Coins

Post by sazzadcsedu » Fri Jan 14, 2011 11:02 am

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.

now add all element .Sum=1+2+4+6=13.
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 .
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

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

Re: 562 - Dividing Coins

Post by md_yusuf » Fri Jan 14, 2011 11:49 am

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.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by Shafaet_du » Wed Feb 02, 2011 8:30 pm

I got a wa for a simple but tricky case.

Code: Select all

1
0
output is 0

:)

another case that may help you:

Code: Select all

1
13
1 4 6 8 5 3 4 7 5 3 5 2 100
ans: 47

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

Re: 562 - Dividing Coins

Post by mdpallob » Thu Jun 09, 2011 4:41 pm

got two times wrong answer.
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;
}

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by Imti » Wed Jun 15, 2011 8:26 pm

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.. :oops:

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by Imti » Sat Jun 25, 2011 4:12 pm

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.

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

Re: 562 - Dividing Coins

Post by mostafiz93 » Tue May 22, 2012 7:51 pm

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.

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

Re: 562 - Dividing Coins

Post by brianfry713 » Tue May 22, 2012 11:48 pm

see I/O #7 at http://ideone.com/XgQ97, AC output is 1.
Check input and AC output for thousands of problems on uDebug!

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

Re: 562 - Dividing Coins

Post by mostafiz93 » Mon May 28, 2012 5:40 pm

thanks brianfry!
got AC.

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

Re: 562 - Dividing Coins

Post by shopnobaj_raju » Fri Jun 15, 2012 12:38 am

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.

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

Re: 562 - Dividing Coins

Post by brianfry713 » Fri Jun 15, 2012 9:40 pm

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

Your RE is here:
for(i=0;i<103;i++)
for(j=0;j<25011;j++) opt[j]=-100;
Check input and AC output for thousands of problems on uDebug!

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

Re: 562 - Dividing Coins

Post by shopnobaj_raju » Sat Jun 16, 2012 2:53 pm

Thanks

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

562 - Dividing coins and Knapsack Algorithm

Post by MauriWilde » Tue Jan 22, 2013 3:30 am

This looks like an easy knapsack problem, but I don't know the knapsack algorithm. So, could anyone give me a pseudo-code for this problem? Or a pseudo-code for the knapsack algorithm?

Thank you very much. :D

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

Re: 562 - Dividing coins and Knapsack Algorithm

Post by brianfry713 » Tue Jan 22, 2013 10:41 pm

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 5 (500-599)”