ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1005. Stone Pile

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
Posted by Artem Khizha [DNU] 8 Jul 2012 00:40
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
Posted by Artem Khizha [DNU] 8 Jul 2012 19:27
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
Artem Khizha [DNU] wrote 8 July 2012 19:27
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
Posted by Artem Khizha [DNU] 8 Jul 2012 20:39
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
Posted by Alexey Dergunov [Samara SAU] 9 Jul 2012 00:22
All polynomial algorithms are wrong, don't even try to write them, WA will be yours.
Re: Help to Understand DP algortihm
Posted by Artem Khyzha 9 Jul 2012 01:26
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.