Блог пользователя steelarm

Автор steelarm, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Try with

5 5 5 7 8

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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!

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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?)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.