Показать все сообщения Спрятать все сообщенияCan anyone explain the DP algorithm logic posted for this problem through examples?? 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. 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 Any help please??
Is it actually a Time Limit Exceeded error?? I dont understand!! 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.
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 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 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!! 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!!! All polynomial algorithms are wrong, don't even try to write them, WA will be yours. 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). 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 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. |
