steelarm's blog

By steelarm, history, 15 months ago, In English

The problem

I am trying out the following approach:

1.I sort the array of weights in decreasing order and "put" the largest weight in one group.

2.Then I keep adding weights to the other group until it becomes larger.

3.Then I start adding apples to the first group until this is one is larger and again start putting apples in the other group and keep on going like this until i reach the end of the array.

4.And then I print the difference between the total weights of the two groups.

My solution gives the correct answer with the sample test cases and a few others too but I am getting a WA, so can anyone suggest something I can do to correct my code. Code:

#include <bits/stdc++.h>
using namespace std;

#define B begin()
#define E end()
#define I iterator
using pii = pair < int , int >;
using vi = vector < int >;
using llu = unsigned long long int;
using ll = long long int;


//ofstream cout ("op.txt");
//ifstream fin("inp.in");
int main ()
{
    ll n;
    cin >> n;
    vector <ll> vec(n);
    ll val;
    for ( int i = 0 ; i < n ; i ++ ){
        cin >> val;
        vec[i] = val;
    }
    sort ( vec.B , vec.E , greater<ll>() );
    ll ansa = 0 , ansb = 0 ;
    ansa = vec[0];
    for ( int i = 1; i < n ; i++ ){
        if ( ansb < ansa )
            ansb += vec[i];
        else
            ansa += vec[i];
    }
    cout << max( ansa , ansb ) - min( ansa , ansb );
    return 0;
}



Any and all help is appreciated

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Try with

5 5 5 7 8

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With this testcase my program gives 4 but it is clear that the answer is 0. So it is obvious that my approach is wrong. So can you suggest an improvement.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      It's not that your code is wrong, your whole idea doesn't work. This problem is hard to solve in general, you'll have to use the fact that $$$n \leq 20$$$ and make an exponential time algorithm.

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        So I will need to try out all the possibilities of the two sums so that their difference is minimum ? Anyway, thanks for the tip and I will surely implement this now. Now I realize that I should have taken the n <= 20 limit to mean that an exponential time algorithm was required.

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Finally!! I was able to solve the problem by designing an exponential-time algorithm , so thanks for all the help mango_lassi. Now, I just wanted to ask that should I update the post to reflect the fact that I have solved the question.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exponential time works, but is there a more optimal solution to this problem? I have been trying to think but I cannot think of anything more efficient!

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This looks like a Knapsack but the fact that the range of numbers is big (aprox $$$2^{33}$$$) makes the algo slower than simply try all $$$2^n$$$ possible solutions.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what is an exponential time algorithm?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm. I can't help but see that this problem is similar to Two Sets — https://cses.fi/problemset/task/1092/ However, this approach works there and passes all test cases. Can someone prove why this works there? And why does it not work here?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      they are completely different problems that have different approaches? the solution for this problem should not work for Two Sets since the solution to this problem requires an exponential time solution while Two Sets requires a linear solution, and vice versa

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm sorry for not being clear. The approach that steerlam discussed in his blog, actually works for Two Sets. The problem of Two Sets itself is similar to this one in my opinion (disregarding the constraints and input size). The key difference is that the difference between the two groups should be zero instead of minimum.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          the greedy approach taken in the blog works because in Two Sets, the numbers are 1, 2, ... n. you can prove that they work by looking at the two cases that work (n = 4k or n = 4k+3 for integers k) and proving this greedy approach through induction

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you so much. I'm now working on a recursive solution to Apple Division.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

As N is maximum 20 you can take all possible combinations of elements and put them in one group and put others in another group and check their difference. Maximum complexity will be 2^20 which is acceptable. Something like this:-

for (ll i = 0; i < pow(2, n); i++) { ll sum1 = 0, sum2 = 0; for (ll j = 0; j < n ; j++) { if (i & 1 << j) sum1 += a[j]; else sum2 += a[j]; } min1 = min(min1, abs(sum1 - sum2)); }

Hope it helps!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have written the code snippet but its difficult to understand what this code is doing like why u have used two loops? why you have wriiten pow(2,n)? why you have used the bit manipulation i&1<<j? this will help those who are trying to understand the solution

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm just using all possible combinations of size N from 0000...N times to 111...N times in binary form and for each number I check if which bit(i) is set and put Ai in one group and all indexes where there is 0 in another group. And take there difference.

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

hi,can i use dp here because this sum is similar to subset sum with minimum difference?

i am using this concept but i am getting runtime error in 9 diff tc.

EDIT: got it. its done

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it