Задача Натпревар (тест натпревар март 2012)

Можи малку помош околу решението на задачава?
Еве го кодот што го напишав:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool pogolem(int a,int b){return (a>b);}

int main()
{
    int i,j,tmp;
    int iPrvTim, iVtorTim;
    int iJacina1, iJacina2;
    int iBrUcesnici;
    vector<int> viNatprevaruvaci;

cin >> iBrUcesnici;

iPrvTim = 0; iJacina1 = 0;
    iVtorTim = 0; iJacina2 = 0;

for(i = 0; i < iBrUcesnici; i++)
    {
        cin >> tmp;
        viNatprevaruvaci.push_back(tmp);
    }

sort(viNatprevaruvaci.begin(),viNatprevaruvaci.end(),pogolem);
    iJacina1 += viNatprevaruvaci[0];
    viNatprevaruvaci[0] = 0;
    iPrvTim++;
    for(i = 1; i < viNatprevaruvaci.size(); i++)
    {
        if ((abs(iPrvTim - iVtorTim) < 2) && (iJacina1 > iJacina2))
        {
            iJacina2 += viNatprevaruvaci[i];
            iVtorTim++;
            viNatprevaruvaci[i] = 0;
        }
        else
        {
            iJacina1 += viNatprevaruvaci[i];
            iPrvTim++;
            viNatprevaruvaci[i] = 0;
        }
    }

if(iJacina1 > iJacina2)
        cout << iJacina2 << ' ' << iJacina1;
    else
        cout << iJacina1 << ' ' << iJacina2;
    return 0;
}

Zatoa shto ova e greedy i nema da raboti

eve ti primer na koj kje padne
6
10000000 10 10 10 1 1

Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев

Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

tStojkovski wrote:

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

Да, да, нема потреба од дополнително објаснување

Фала за идејата, немаше да ми текне вака да ја решам

tStojkovski wrote:

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

filip_bujaroski wrote:

tStojkovski wrote:

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна

tStojkovski wrote:

filip_bujaroski wrote:

tStojkovski wrote:

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна

Epa realno se drugo mi beshe jasno osven kako da znam deka ne sum go zemal 2 pati istiot natprevaruvac

tStojkovski wrote:

filip_bujaroski wrote:

tStojkovski wrote:

Vikjan94 wrote:

tStojkovski wrote:

Vikjan94 wrote:

obi1kenobi wrote:

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?

Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.

Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.

Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш

A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна

Овој пристап ти помина на сите тест-примери???
Јас ја направив и така, функционира на 19/20. Реално, може да се води сметка да не се додава неколку пати истиот човек, ама не може да се води сметка колкава ќе биде разликата помеѓу бројот на луѓе во групите.

Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.

Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.

Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...

bedzo wrote:Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.

Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.

Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...

Mene za ovoj slucaj mi teknuva samo bruteforce knapsack... :/
Da baras do kade mozes da stignes, i od tamu da go dodavas noviot chlen, shto najverojatno kje bide so ogromna slozenost