Nie rozumiem rozwiązania zadania Mecze z potyczek algorytmicznych (haszowanie)

Question

Mam takie zadanie: Mecze
i znalazłem rozwiązania w internecie, (tutaj podaje przerobione tak żeby było jak najbardziej czytelne):

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    vector<long long> hashed (10); //taka wielkosc zebym widzial co sie dziejej w tablicy w debuggerze
    int n, m, player_id;

    cin >> n >> m;

    while(m--){
        for (int i = 0; i < n; i++){
            cin >> player_id;
            hashed[player_id-1]*=2;
            if (i<n/2)
                hashed[player_id-1]++;
        }
    }

    sort(hashed.begin(),hashed.begin()+n);

    for (int i = 1; i < n; i++){
        if (hashed[i-1]==hashed[i]){
            cout << "NIE\n";
            return 0;
        }
    }

    cout << "TAK\n";
    return 0;
}

No i widzę że komórke dla każdego gracza podnosimy zawsze do kwadratu, i dla graczy z pierwszej drużyny dodajemy 1. na koniec sprawdzamy czy jakiś wynik się powtórzył, tylko co to wszytsko ma na celu i dlaczego działa?

Answer 1

W tym zadaniu obserwacja jest taka, że jeżeli jakaś para osób nigdy ze sobą nie zagra to znaczy, że zawsze będą w tej samej drużynie. 

Czyli wystarczy zapamiętać kto grał w której drużynie i jeżeli na koniec wyjdzie nam, że 2 lub więcej osób mają ten sam zbiór drużyn to wynikiem jest "NIE". 

Spamiętywanie drużyn można zrobić hashowaniem. To co jest w tym kodzie jest trochę nietypowe, bo przeważnie to się robi jakoś tak:

for (int i = 0; i < m; i++){
   for (int j = 0; j < n; j++){
       cin >> a;
       if (i < n/2) 
           hashed[a-1] |= (1 << i);
   }
}

Ale ten kod, który znalazłeś robi tak naprawdę to samo

Comments

Trochę mi to przypomina maskę bitową, a ty się idź potyczkować a nie noobom pomagasz :D

---

No bo to jest taka maska bitowa. A dzisiejsze B i C już rozwiązałem także mam wolne na dzisiaj