1 тест
13+14+8-27-5=3
или
27+8-13+14+5=3

dp cant be applied to every problem

Только это называется не "ошибка в 8-м тесте" (сам тест корректен), а "ошибка *в решении* НА 8-м тесте".
Тест - просто случайный тест, направленный на убивание жадных решений. Эту задачу неверно решать жадным алгоритмом.

здесь надо делать перебор битовыми масками

Edited by author 28.01.2023 12:25

try this:
8
6 7 9 13 18 24 31 50

expected: 0

My program do this

#include <iostream>

int main()
{
    int temp = 0,  maxtemp=0, even = 0, midle = 0, different = 0, maxdifferent = 0;
    int arrayA[100];
    int sizeArray;
    std::cin >> sizeArray;
 for (int i = 0; i < sizeArray; i++)
 {
     std::cin >> arrayA[i];
 }
 for (int i = 0; i < sizeArray; i++)
    {
       for (int j = i; j < sizeArray; j++)
        {
            if (arrayA[i] < arrayA[j])
            {
                temp = arrayA[i];
                arrayA[i] = arrayA[j];
                arrayA[j] = temp;
            };

        };
    };
        for (int i = 0; i < sizeArray; i++)
        {
            midle += arrayA[i];
        };
        even = midle % 2;
        maxdifferent= different= midle = midle / 2 +even;
        if (sizeArray != 1)
         {
            for (int i = 0; i < sizeArray; i++)
            {
                different = midle;
                for (int j = i; j < sizeArray; j++)
                {
                    if (different >= arrayA[j])
                    {
                        temp += arrayA[j];
                        different -= arrayA[j];
                    };

                };
              if (maxdifferent > different)
                     {
                         maxdifferent = different;
                     };
            };
        };
        maxdifferent = 2* maxdifferent -even;
    std::cout << maxdifferent;
}

Try to use bitmasks instead of using recursion;)

Finally I could resolve the task on Python using DP for 0.65 sec.

So, long story short - do not use greedy algorithm, read and think more about dynamic programming.

If you can solve the question with DP, you should avoid Brute Force. Although, I could not come up with a Greedy algorithm. I solved it using DP.

try this:
8
6 7 9 13 18 24 31 50

expected: 0

6
1 2 3 4 100 100
Will fail this program

The solution is not correct

let me give you an example 13 14 27
if I understand your solution you are sorting it and then add to left or to the right. in this example the diff is 0 what your program returns?

Test Case :
5
5 5 4 3 3

Edited by author 06.11.2018 20:49

4
15 16 30 2

Answer 1

Hi !
Would you mind explaining the if on the second for ?
I mean, how is this putting all different combination of blocks on each pile ?
Thanks :D

man u're awesome :) solution is great for that kinda bruteforce! just made all those things in cpp myself and got ACd :D

but this problem's still far too hard for the "beginners" tag on which it is right now :)

Can anybody translate me this code on C++ or Pascal

Thanks, got AC converting it into C++.

Thank you very much))

Thanks, mate! Serves me right for being too impatient and not considering the basic corner cases! :-)

I don't know what is the second test
I have Accepted status
Because I am assuming that there is the only way to solve that task
And this is BRUTE FORCE