steelarm's blog

By steelarm, history, 5 years 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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Try with

5 5 5 7 8

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        4 years 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!

        • »
          »
          »
          »
          »
          4 years 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.

  • »
    »
    3 years 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?

    • »
      »
      »
      3 years 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

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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

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

      in two sets problem, the number are from 1 to n hence we used the fact that every 4 consucutive numbers are in {a1,a2,a3,a4} fashion where a1+a2==a3+a4

      here the numbers are randomly taken

»
4 years 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!

  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hi, I had initially thought of this solution, but wasn't able to convince myself that it would not TLE. If I'm right, 2^20 operations max on the loop comes out around 1e7. So, won't that lead to a TLE? (since only upto 1e6 time is the threshold?)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. Max operations allowed is more than 1e7 and less than 1e8 so around 1e7. That's why 1e7 is allowed in most of the circumstances.