3. Stankova dilema vzorové riešenie

5
1 4 3 7 10

1

3
3 3 3

3

2
2 4

0

Bruteforce

Bruteforce sa väčšinou robí tak, že vyskúšame všetky možnosti. Keďže máme zistiť, koľko dvojíc predmetov je podobnejších ako rozdielnejších, stačí vyskúšať každú dvojicu a spraviť pre ne XOR a AND. Keď bude ich XOR väčší ako ich AND, zapamätáme si to. Všetkých dvojíc je \(\binom{n}{2}\). To znamená, že toto riešenie má časovú zložitosť \(O(n^2)\). Pamäťovú zložitosť má \(O(n)\), pretože si potrebujeme zapamätať všetky čísla zo vstupu, aby sme ich mohli navzájom porovnať.

Zaujímavá myšlienka

Dve čísla sú podobnejšie ako rozdielnejšie vtedy, keď ich najľavejší jednotkový bit je na “rovnakom mieste” (nasleduje za ním v oboch číslach rovnako veľa bitov). Majme dve čísla v binárnom tvare \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\) a \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\), kde \(k\) je počet bitov čísla a štvorček značí bit. Ich AND je \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\) a ich XOR je \(0\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\). Očividne platí, \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0} > 0\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\). To znamená, že sú podobnejšie ako rozdielnejšie. Naopak, ak máme dve čísla - \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\) a \(0\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\), ktoré nemajú najľavejší jednotkový bit na rovnakom mieste, tak ich AND je \(0\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\) a ich XOR je \(1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\). Očividne platí, že \(0\square_{k-2}\square_{k-3}...\square_{1}\square_{0} < 1\square_{k-2}\square_{k-3}...\square_{1}\square_{0}\). To znamená, že sú rozdielnejšie ako podobnejšie. Z toho vyplýva, že nám stačí o čísle vedieť jeho najľavejší jednotkový bit aby sme vedeli, koľko čísel je s ním podobnejších ako rozdielnejších.

Optimálne riešenie

Vytvoríme si pole s veľkosťou \(b\), kde \(b\) je počet bitov najväčšieho čísla. V tomto poli si budeme pamätať, koľko čísel s daným najľavejším bitom sme videli.

Najľavejší bit čísla vieme v C++ zistiť pomocou funkcie __builtin_clz(), ktorá spočíta počet nulových bitov na začiatku čísla (v \(O(1)\)!). V Pythone zasa môžeme využiť funkciu bin(), ktorá prevedie číslo do binárnej sústavy a vráti ho ako string. Pozíciu najľavejšieho jednotkého bitu zisíme ako len(bin(x)) - 2.

Keď už máme vstup prejdený a pole naplnené, zostáva nám spočítať počet dvojíc. Vieme, že ľubovoľné dve čísla s rovnakým najľavejším bitom sú viac podobné ako rozdielne. Na zistenie počtu dvojíc môžeme použiť vzorec \(\frac{n_i*(n_i - 1)}{2}\), kde \(n_i\) je číslo na i-tom mieste v našom poli. Alternatívne si vieme počet dvojíc počítať počas plnenia pola. Vždy pred tým, než zvýšime hodnotu pola o jedna k finálnemu výsledku pripočítame túto hodnotu pola. Zamyslite sa, že týmto postupom dostaneme rovnaký výsledok.

Časová zložitosť riešenia je \(O(bn)\) a pamäťová je \(O(b)\). Ale keďže \(b\) je vo všetkých vstupoch rovnaké a počet bitov sa väčšinou ako premenná vynecháva, môžeme povedať, že časová zložitosť je \(O(n)\) a pamäťová je \(O(1)\).

n = int(input())
v = map(int, input().split())

p = [0 for _ in range(32)]
res = 0
for x in v:
    for i in range(31, -1, -1):
        if (x & (1 << i)) != 0:
            res += p[i]
            p[i] += 1
            break
print(res)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, res = 0;
    cin >> n;
    vector<int> p(35, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        res += p[__builtin_clz(x)]++;
    }
    cout << res << '\n';
}