Help to Understand DP algortihm
Posted by
ashwin 7 Jul 2012 17:15
Can anyone explain the DP algorithm logic posted for this problem through examples??
Re: Help to Understand DP algortihm
If you want to get AC with DP, you can gain inspiration by reading about knapsack problem on wikipedia.
P.S. I suggest that you solve this problem without DP first. It has simple solution, that is why it got "problem for beginners" tag.
Re: Help to Understand DP algortihm
Posted by
ashwin 8 Jul 2012 18:37
Hi Artem Khizha
I have done some brute force code and i am able to get the answers but when i submit it i get WA #1 but i get the correct answer on my compiler. This is the code i have posted,
//timus ru programming problems
//stone pile
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
//void even_diff(int [],int);
//#define N 100000
int main(){
//clrscr();
int n;
int i,j;
int temp=0;
int sum_l=0,sum_r=0;
long cur_sum=0;
long old_sum=0;
long stones[100000];
//printf("\nenter n:");
scanf("%d",&n);
//printf("\nenter wts: ");
for(i=0;i<n;i++)
scanf(" %ld",&stones[i]);
for(i=0;i<n;i++)
cur_sum+=stones[i];
old_sum=cur_sum;
cur_sum=cur_sum/2;
if(n==1)
printf("\n%ld",stones[0]);
else if(n==2)
printf("\n%ld",abs(stones[0]-stones[1]));
else{
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(stones[i]<stones[j]){
temp=stones[i];
stones[i]=stones[j];
stones[j]=temp;
}
}
}
sum_l=stones[0];
sum_r=stones[1];
for(i=2;i<n;i++){
if(sum_l<sum_r){
if(sum_l+stones[i]<=cur_sum){
sum_l+=stones[i];
}
}
else
sum_r+=stones[i];
}
if(old_sum%2==0)
printf("\n%ld",abs(sum_l+sum_r-(2*cur_sum)));
else
printf("\n%ld",abs(sum_l-sum_r));
getch();
return 1;
}
Edited by author 08.07.2012 19:03
Re: Help to Understand DP algortihm
Posted by
ashwin 8 Jul 2012 19:07
Any help please??
Is it actually a Time Limit Exceeded error?? I dont understand!!
Re: Help to Understand DP algortihm
Try this test:
> 6
> 1 4 5 6 7 9
It will show you, why you get WA#1 first, and then you will see that your approach leads to WA#5. :-)
And yes, it is not guaranteed that 1st test is the one from the statement.
Re: Help to Understand DP algortihm
Posted by
ashwin 8 Jul 2012 20:13
Try this test:
> 6
> 1 4 5 6 7 9
It will show you, why you get WA#1 first, and then you will see that your approach leads to WA#5. :-)
And yes, it is not guaranteed that 1st test is the one from the statement.
Hi Artem
I get 0 as the answer as
(9+7)=16 and (1+4+5+6)=16
Is it not correct?? or does this correct answer lead to a wrong one for further tests?
What is WA#5?
So the first test need not be the sample given the problem, thanks for the info
Re: Help to Understand DP algortihm
Oh, I forgot that I run your solution first on:
> 4
> 1 3 9 27
Actually, I just do not understand the answer you print in cases of even N. :-)
P.S. I cannot prove that sorting doesn't help here, but don't be surprised if it really doesn't. :-)
Edited by author 08.07.2012 21:40
Re: Help to Understand DP algortihm
Posted by
ashwin 8 Jul 2012 21:37
Hi Artem
i get 0 for this which is wrong,
This is because for even sum i print left+right-2*sum.
I did this because for even sums i thought the answer would be 0 as most of the cases i tried were like that
eg:3,1,1,1
total sum=6
here first half of the sum is 3 and next half is 1+1+1=3,so i add 3 and 1+1+1=3 and finally i subtract from 2*total sum/2.
It is a wrong process as shown by the test case you have given. I have to think of another way now!!
Re: Help to Understand DP algortihm
Posted by
ashwin 9 Jul 2012 00:14
Hi Artem
I have modified the code and now i am getting the proper answer for your test case:
27,9,1,3 the min diff is 14
this is the code
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
//void even_diff(int [],int);
//#define N 100000
#define TRUE 1
#define FALSE 0
int main(){
//clrscr();
int n;
int i,j;
int temp=0;
long sum_l=0,sum_r=0;
long cur_sum=0;
long old_sum=0;
long stones[100000];
int left_out=0;
int isLeftOut;
//printf("\nenter n:");
scanf("%d",&n);
//printf("\nenter wts: ");
for(i=0;i<n;i++)
scanf(" %ld",&stones[i]);
for(i=0;i<n;i++)
cur_sum+=stones[i];
old_sum=cur_sum;
cur_sum=cur_sum/2;
//printf("\ncur_sum=%ld",cur_sum);
if(n==1)
printf("\n%ld",stones[0]);
else if(n==2)
printf("\n%ld",abs(stones[0]-stones[1]));
else{
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(stones[i]<stones[j]){
temp=stones[i];
stones[i]=stones[j];
stones[j]=temp;
}
}
}
sum_l=stones[0];
sum_r=stones[1];
isLeftOut=FALSE;
for(i=2;i<n;i++){
if(sum_l+stones[i]<=cur_sum)
sum_l+=stones[i];
else if(sum_r+stones[i]<=cur_sum)
sum_r+=stones[i];
else{
left_out=stones[i];
isLeftOut=TRUE;
}
}
/*if(old_sum%2==0)
printf("\n%ld",abs(sum_l+sum_r-(2*cur_sum)));
else*/
if(isLeftOut)
printf("\n%ld",abs(sum_l-sum_r-left_out));
else
printf("\n%ld",abs(sum_l-sum_r));
}
//printf("\nsum_l=%ld sum_r = %ld",sum_l,sum_r);
getch();
return 1;
}
I am getting WA#5. I dont know what more i should do as i feel i have taken a long long time to do this simple problem!!!
Re: Help to Understand DP algortihm
All polynomial algorithms are wrong, don't even try to write them, WA will be yours.
Re: Help to Understand DP algortihm
Well, as I said, I don't know how to prove that your solution is wrong.
But I know that you can get AC in two different ways: with backtracking in O(2^N) (quite easily) and with DP in O(N*W) (a bit trickier).
Re: Help to Understand DP algortihm
Posted by
ashwin 9 Jul 2012 21:20
Thank you Artem for your help
So it must be done either with backtracking or DP, gues ill have to start learning these two techniques for this problem
Re: Help to Understand DP algortihm
Posted by
Bogatyr 15 Sep 2012 19:06
Backtracking (with memo-ization) and DP are two techniques that make the 'try all possible combinations" more efficient, but they're still "try all combinations" solutions. For problem sizes like this one ( 1 <= N <= 20 ), explicitly enumerating and trying all possible partitions runs pretty quickly. Adding together 20 numbers a million times is nothing for a 3GHz processor.