5. Odpad spoločnosti vzorové riešenie

2       // počet sád
3       // počet lavíc v prvej sade
2
1
2
2
2       // počet lavíc v druhej sade
1

3 1 2 3
2 1 2
2 3 4
2 3 5
0
1 2
3 6
4 5
2 1 2
0
1 2
4 3

Skúšanie všetkých dvojíc

Ako sa dá najjednoduchšie zistiť, kto s kým sedí? Spýtame sa na všetky dvojice študentov. Stačí klásť otázky typu \(1~2\), \(1~3\), … a vždy keď dostaneme odpoveď \(1\), čo znamená, že títo dvaja sedia v jednej lavici, zapamätáme si túto dvojicu. Ak sa na každú dvojicu spýtame len raz, položíme \({ 2n \choose 2 } = \frac{2n(2n-1)}{2}\) otázok. Časová zložitosť takéhoto riešenia je \(O(n^2)\) a mohli ste zaň dostať 2 body.

Pokiaľ neviete s úlohou pohnúť, je dobré skúsiť aspoň to prvé (správne), čo vás napadne. Navyše, na jednoduchom programe si viete vyskúšať spôsob komunikácie s testovačom – “flushovanie” výstupu, spracúvanie viacerých sád a formát otázok a odpovedí.

#include <cstdio>
#include <algorithm>
#include <vector>
#define For(i,N) for(int i=0; i<N; i++)
#define FOR(i,z,k) for(int i=z; i<k; i++)

using namespace std;

int N, T;
vector<pair<int,int> > pary;

int main(){
    scanf("%d", &T);
    For(t,T){
        pary.clear();
        scanf(" %d", &N);
        For(i,2*N)
            FOR(j,i+1,2*N){
                printf("2 %d %d\n",i+1,j+1); fflush(stdout);
                int odpoved;
                scanf("%d", &odpoved);
                if(odpoved==1) pary.push_back( make_pair(i+1, j+1) );
            }

        //vypis riesenia
        printf("0\n");
        For(i,N)
            printf("%d %d\n", pary[i].first, pary[i].second);
        fflush(stdout);
    }
    return 0;
}

Skúšanie všetkých rozumných dvojíc

Môžeme si všimnúť, že ak sedia spolu študenti \(1\) a \(2\), v predošlom programe sa dozvieme o tejto dvojici hneď v prvej otázke. Ďalších \(2n-2\) otázok ohľadom študenta \(1\) je teda úplne zbytočných. Preto sa dá vyššie popísaný program v praxi mierne zlepšiť, ak si budeme o každom študentovi pamätať, či už vieme, s kým sedí. Pred vypísaním otázky potom zvážime, či je zbytočná, alebo či sa ňou niečo nové dozvieme.

V najhoršom prípade môžu spolu sedieť žiaci \(1, 2n\); \(2, 2n-1\); … \(n, n+1\). Pre prvého sa tak spýtame \(2n-1\) otázok, pre druhého \(2n-3\), atď. Teda \(2(n)-1 + 2(n-1)-1 + 2(n-2)-1 + \dots + 2(n-(n-1))-1 = 2 \frac{n(n-1)}{2} - n = n(n-2)\) otázok. A hoci časová zložitosť zostáva stále \(O(n^2)\), aj v najhoršom prípade sa spýtame približne o polovicu otázok menej. Za takéto zlepšenie ste mohli dostať až 4 body.

Binárne vyhľadávnie

Viete, kadiaľ vedie cesta k lepšiemu riešniu¹? Ak ste bezradní, prečítajte si zadanie a zistite, čo z toho, čo ste mali k dispozícii, ste zatiaľ nevyužili.

V predošlých riešeniach sme totiž vôbec nepoužili to, že sa môžeme pýtať na ľubovoľnú podmnožinu študentov. Sústreďme sa na jedného študenta, napr. s číslom \(1\) a pokúsime sa zistiť jeho spolusediaceho. Ak sa spýtame, v koľkých laviciach sedí celá trieda, dostaneme neprekvapivú odpoveď \(n\). Spýtajme sa radšej:

Koľko lavíc bolo obsadených, ak bola v škole polovica žiakov spolu so žiakom \(1\)?

Dostaneme odpoveď \(d\) a toto číslo môže byť v rozmedzí \(\langle n/2, n\rangle\). Skúsme sa ešte raz spýtať tú istú otázku bez študenta \(1\).

• Ak je odpoveď \(d-1\), študent \(1\) sedel v tento deň sám – v tejto polovici triedy jeho spolusediaci nie je, teda je v druhej polovici.
• Ak je odpoveď \(d\), v tejto polovici triedy musí byť aj spolusediaci študenta \(1\), lebo aj po odchode žiaka \(1\) zostala jeho lavica obsadená.

Čo sme dosiahli? Pomocou dvoch otázok sme rozhodli, či môže byť polovica študentov spolusediaca s \(1\). Ďalej nás bude zaujímať už len tá polovica študentov, medzi ktorými je aj jeho spolusediaci. Ďalšími dvoma otázkami vylúčime štvrtinu, potom osminu, atď. Po spýtaní sa \(2 \log 2n\) otázok bude možný spolusediaci len jeden. Ak sa pre každého študenta spýtame \(2 \log 2n\) otázok, pre \(n=1\,000\) sa spýtame približne \(20\,000\) otázok a za takéto riešnie ste mohli dostať 8 bodov. Spýtame sa teda \(O(n \log n)\) otázok.

Ak by vás zaujímala aj časová zložitosť, musíte zvážiť to, že pýtanie sa rôznych otázok vyžaduje rôzny čas. Ak sa napríklad pýtate na polovicu triedy, položenie jednej otázky si vyžiada čas \(O(n)\). Pri kladení otázok o jednom študentovi vypisuje program \(n, n/2, n/4 \dots\) čísel, čo sa nasčítava na približne \(2n\). Časová zložitosť zostáva stále \(O(n^2)\), no počet otázok sa nám podarilo efektívne znížiť, čo bolo, koniec koncov, to podstatné v tejto úlohe.

Toto riešenie sa dá tiež mierne zlepšiť, ak sa budeme pýtať len na študentov, o ktorých nevieme, s kým sedia. Na polovice, štvrtiny… nemusíme teda deliť celú triedu, stačí deliť len množinu neznámych študentov.

#include <cstdio>
#include <algorithm>
#include <vector>
#define For(i,N) for(int i=0; i<N; i++)

using namespace std;

int N, T;
vector<bool> neznamy;
vector<pair<int,int> > pary;

bool je_v_skupine(int x, int l, int r, vector<int> &V ){
    //ziak x, v intervale <l,r), v casti triedy V
    int bezx, sx;

    if(r-l == 1) bezx = 1;
    else{
        //vypis prvej otazky
        printf("%d", r-l);
        for(int i=l; i<r; i++)
            printf(" %d", V[i]+1);
        printf("\n");
        fflush(stdout);

        //nacitanie odpovede testovaca
        scanf("%d", &bezx);
    }

    //vypis druhej otazky
    printf("%d ", r-l+1);
    for(int i=l; i<r; i++)
        printf("%d ", V[i]+1);
    printf("%d\n", x+1);
    fflush(stdout);

    //nacitanie 2. odpovede testovaca
    scanf("%d", &sx);

    return (sx==bezx);
}

int main(){
    scanf("%d", &T);
    For(t,T){
        neznamy.clear();
        pary.clear();
        scanf("%d", &N);
        neznamy.resize(2*N,1);

        For(i,2*N)
            if(neznamy[i]){
                //chceme zistit, s kym je i v pare
                //pripravime si pole
                vector<int> mozno;
                For(j,2*N) if(neznamy[j] && j != i) mozno.push_back(j);

                //binarne vyhladame, v ktorej skupine je druhy
                int l=0, r=int(mozno.size());
                while(r-l > 1){
                    int piv = (l+r)/2;
                    if( je_v_skupine( i, l, piv, mozno ) )
                        r = piv;
                    else
                        l = piv;
                }

            //ulozime si 1 par do riesenia
            neznamy[i] = neznamy[mozno[l]] = 0;
            pary.push_back( make_pair(i, mozno[l]) );
        }

        //vypis riesenia
        printf("0\n");
        For(i,N)
            printf("%d %d\n", pary[i].first+1, pary[i].second+1);
        fflush(stdout);
    }
    return 0;
}