Haidora, yoxsa Haidora deyil?#12298

Haidora, yoxsa Haidora deyil? (Həll təhlili)

Problem Müəllifi:	Haidara Al Makdid
Hazırlayan:	Haidara Al Makdid
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Biz

a_{1} & a_{2} & \dots & a_{n}

a_1 \,\&\, a_2 \,\&\, \dots \,\&\, a_n

dəyərini maksimuma çatdırmaq istəyirik, dəqiq $k$ fərqli indeks seçdikdən sonra və hər seçilmiş $a_{i}$ a_i-ni onun $32$ -bit bitwise NOT $\sim a_{i}$ \sim a_i ilə əvəz edirik. $\sim$ 32 bit üzərində götürüldüyü üçün bunu $\sim x = (2^{32} - 1) - x$ \sim x = (2^{32}-1) - x kimi düşünə bilərik, ya da bərabər olaraq $\sim x = (MASK^x)$ \sim x = (\texttt{MASK} \,\hat{}\, x) ilə $MASK = 2^{32} - 1$ \texttt{MASK} = 2^{32}-1.

Son cavabı $X$ adlandıraq. $X$ -də $1$ olan hər bit üçün, son massivdəki hər elementin də həmin bitinin $1$ olması lazımdır, əks halda AND həmin mövqedə $0$ olacaq. Bu, $X$ -i ən əhəmiyyətli bitdən ən az əhəmiyyətli bitə qədər tədricən bit-bitə qurmağı təklif edir: biz cari cavabı ans saxlayırıq və $31$ -dən $0$ -a qədər hər bit $j$ üçün onu artıq düzəltdiyimiz bitlərin üzərinə $1$ qoymağa çalışırıq.

Müəyyən olaraq, bit $j$ -də biz bir namizəd dəyər yaradırıq

cand = ans ∣ (1 ≪ j),

\texttt{cand} = \texttt{ans} \,\vert\, (1 \ll j),

yəni son AND-in canddə $1$ olan bütün bitləri olmasını istəyirik. Bu düzəldilmiş cand üçün, bütün massivdə bir uyğunluq yoxlaması aparırıq. Hər bir element $x = a_{i}$ x = a_i üçün son konfiqurasiyada yalnız iki vəziyyət var: ya biz onu $x$ kimi saxlayırıq, ya da onu $y =\sim x = (MASK - x)$ y = \sim x = (\texttt{MASK} - x)-ə çevrilirik. candin əldə olunması üçün, hər mövqedə $i$ üçün bu seçimlərdən ən az biri candin bütün bitlərini tamamilə əhatə etməlidir:

keep_ok ⟺ (x & cand) = cand, flip_ok ⟺ (y & cand) = cand .

\text{keep\_ok} \iff (x \,\&\, \texttt{cand}) = \texttt{cand}, \qquad \text{flip\_ok} \iff (y \,\&\, \texttt{cand}) = \texttt{cand}.

$(keep_ok, flip_ok)$ (\text{keep\_ok}, \text{flip\_ok})-ya baxaraq, indeksləri üç faydalı növə ayırırıq:

Hər ikisi də yanlışdırsa, nə $x$ , nə də $\sim x$ candin bütün bitlərinə malikdir, buna görə də bu indeks candi heç vaxt təmin edə bilməz. Beləliklə, cand özü mümkün deyil və bu biti rədd etməliyik.
Əgər $keep_ok = false$ \text{keep\_ok} = \text{false} və $flip_ok = true$ \text{flip\_ok} = \text{true}-dirsə, bu indeksi candi təmin etmək üçün çevrilməyə məcburuq. Beləliklə, $F$ belə məcburi indekslərin sayını olsun.
Əgər $keep_ok = true$ \text{keep\_ok} = \text{true} və $flip_ok = true$ \text{flip\_ok} = \text{true}-dirsə, bu indeks esnekdir: həm saxlamaq, həm də çevirmək hələ də candi təmin edir. Beləliklə, $C$ belə esnek indekslərin sayını olsun.

(Əgər $keep_ok = true$ \text{keep\_ok} = \text{true} və $flip_ok = false$ \text{flip\_ok} = \text{false}-dirsə, biz sadəcə elementi saxlamaq məcburiyyətindəyik; bu, heç bir çevrilmə tələb etmir və heç bir esneklik vermir.)

Biz dəqiq $k$ çevrilmə etməliyik. Düzgün cand üçün, bütün $F$ məcburi indekslər çevrilməlidir, buna görə də ən azı $F$ çevrilməyə ehtiyacımız var. Digər tərəfdən, $C$ esnek indekslərin istənilən alt dəstini çevirmək imkanı var, buna görə də candi hələ də təmin edərkən reallaşdıra biləcəyimiz çevrilmələrin ümumi sayı $F$ (yalnız məcburi olanlar) ilə $F + C$ F+C (məcburi olanlar və bütün esnek olanlar) arasında dəyişir. Beləliklə, cand yalnız aşağıdakı şərtlə mümkündür:

F \leq k \leq F + C .

F \le k \le F + C.

Bu bərabərlik doğru olarsa, bilirik ki, candi təmin edən dəqiq $k$ indeksini seçmək üçün bir yol var. Bu halda bu biti qəbul edirik və $ans := cand$ \texttt{ans} := \texttt{cand} olaraq təyin edirik. Əks halda, bu biti $0$ olaraq ans-da saxlayırıq və növbəti aşağı bitə keçirik.

Biz bitləri ən əhəmiyyətli bitdən aşağıya doğru işləyirik və yalnız bir bit seçdiyimiz bütün bitləri dəstəkləyən dəqiq $k$ çevrilmə konfiqurasiyası olduğu zaman bir bit təyin edirik, nəticədə əldə olunan ans leksik olaraq (və beləliklə, ədədi olaraq) maksimum son AND-ı əldə edir. $32$ bit mövqeyi üçün biz bütün $n$ elementlərini bir dəfə skan edirik, buna görə də ümumi mürəkkəblik $O (32 n) = O (n)$ O(32n) = O(n) vaxt və giriş massivindən başqa $O (1)$ əlavə yaddaşdır.

n,k=map(int, input().split())
a=list(map(int, input().split()))

MASK=(1<<32)-1
ans=0

for j in range(31, -1, -1):
    p=1<<j
    cand = ans | p
    forced = 0
    flex = 0
    ok = True
    for x in a:
        keep = (x & cand) == cand
        flipped = (~x) & MASK     
        flip = (flipped & cand) == cand

        if not keep and not flip:
            ok = False
            break
        if not keep and flip:
            forced += 1       
        elif keep and flip:
            flex += 1         

    if not ok:
        continue

    rem = k - forced
    if rem < 0 or rem > flex:
        continue

    ans = cand

print(ans)

Python