• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
126 wizyt
pytanie zadane 10 grudnia 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

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?

1 odpowiedź

+1 głos
odpowiedź 10 grudnia 2020 przez Whistleroosh Maniak (56,900 p.)
wybrane 10 grudnia 2020 przez wojtek_suchy
 
Najlepsza

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

komentarz 10 grudnia 2020 przez wojtek_suchy Mądrala (6,880 p.)
Trochę mi to przypomina maskę bitową, a ty się idź potyczkować a nie noobom pomagasz :D
komentarz 10 grudnia 2020 przez Whistleroosh Maniak (56,900 p.)
No bo to jest taka maska bitowa. A dzisiejsze B i C już rozwiązałem także mam wolne na dzisiaj

Podobne pytania

0 głosów
0 odpowiedzi 266 wizyt
pytanie zadane 11 marca 2018 w PHP przez PolYGlok Pasjonat (19,450 p.)
0 głosów
0 odpowiedzi 127 wizyt
0 głosów
1 odpowiedź 362 wizyt
pytanie zadane 29 stycznia 2021 w PHP przez KrzysztofS Nowicjusz (170 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...