هل هايدورا أم لا هايدورا؟#12298

هل هايدورا أم لا هايدورا؟ (شرح الحلول)

مؤلف المشكلة:	هايدارا المكديد
أعدها:	هايدارا المكديد
حررها:	حسن صالح (نموذج رياضي)

الحل

نريد تعظيم قيمة

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

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

بعد اختيار $k$ فهارس مميزة بالضبط واستبدال كل $a_{i}$ a_i المختار بـ NOT الثنائي 32 بت $\sim a_{i}$ \sim a_i. بما أن $\sim$ يتم على 32 بت، يمكننا التفكير فيه كـ $\sim x = (2^{32} - 1) - x$ \sim x = (2^{32}-1) - x، أو بشكل مكافئ $\sim x = (MASK^x)$ \sim x = (\texttt{MASK} \,\hat{}\, x) مع $MASK = 2^{32} - 1$ \texttt{MASK} = 2^{32}-1.

دع الجواب النهائي يكون $X$ . لكل بت يكون $1$ في $X$ ، يجب أن يكون لكل عنصر في المصفوفة النهائية أيضًا تلك البتة تساوي $1$ ، وإلا سيكون AND في تلك الموضع $0$ . هذا يشير إلى بناء $X$ بشكل جشع بتًا بتًا من البت الأكثر أهمية إلى الأقل أهمية: نحن نحافظ على إجابة حالية ans، ولكل بت $j$ من $31$ إلى $0$ نحاول تعيينه إلى $1$ فوق ما قمنا بتثبيته بالفعل.

بشكل ملموس، عند البت $j$ نشكل قيمة مرشحة

cand = ans ∣ (1 ≪ j),

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

مما يعني أننا نريد أن يكون AND النهائي لديه جميع البتات التي هي $1$ في cand. للتحقق من إمكانية تحقيق cand، نقوم بفحص الجدوى على المصفوفة بأكملها. لكل عنصر $x = a_{i}$ x = a_i هناك حالتان فقط في التكوين النهائي: إما أن نحتفظ به كما هو $x$ ، أو نقلبه إلى $y =\sim x = (MASK - x)$ y = \sim x = (\texttt{MASK} - x). لكي تكون cand قابلة للتحقيق، يجب أن يغطي كل موضع $i$ على الأقل أحد هذه الخيارات جميع بتات cand:

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}) نقسم الفهارس إلى ثلاثة أنواع مفيدة:

إذا كان كلاهما خاطئًا، فإن لا $x$ ولا $\sim x$ يحتويان على جميع بتات cand، لذا لا يمكن لهذا الفهرس أن يحقق cand أبدًا. ثم cand نفسها مستحيلة ويجب علينا رفض هذه البتة.
إذا كانت $keep_ok = false$ \text{keep\_ok} = \text{false} و $flip_ok = true$ \text{flip\_ok} = \text{true}، فنحن مجبرون على قلب هذا الفهرس لتحقيق cand. دع $F$ يكون عدد هذه الفهارس المجبورة.
إذا كانت $keep_ok = true$ \text{keep\_ok} = \text{true} و $flip_ok = true$ \text{flip\_ok} = \text{true}، فإن هذا الفهرس مرن: كل من الاحتفاظ والقلب لا يزالان يحققان cand. دع $C$ يكون عدد هذه الفهارس المرنة.

(عندما تكون $keep_ok = true$ \text{keep\_ok} = \text{true} و $flip_ok = false$ \text{flip\_ok} = \text{false} يجب علينا ببساطة الاحتفاظ بالعنصر؛ فهو لا يستهلك أي قلب ولا يعطي أي مرونة.)

يجب علينا إجراء بالضبط $k$ قلبات بشكل عام. بالنسبة إلى cand الثابتة، يجب قلب جميع الفهارس المجبورة $F$ ، لذا نحتاج على الأقل إلى $F$ قلبات. من ناحية أخرى، يمكننا اختيارًا قلب أي مجموعة من الفهارس المرنة $C$ ، لذا فإن العدد الإجمالي للقلبات التي يمكننا تحقيقها مع الاستمرار في تحقيق cand يتراوح من $F$ (فقط المجبورة) إلى $F + C$ F+C (المجبورة بالإضافة إلى جميع المرنة). لذا فإن cand قابلة للتحقيق إذا وفقط إذا

F \leq k \leq F + C .

F \le k \le F + C.

إذا كانت هذه المعادلة صحيحة، نعلم أنه يوجد طريقة لاختيار بالضبط $k$ فهارس لقلبها بحيث تغطي كل عنصر نهائي جميع بتات cand. في هذه الحالة نقبل هذه البتة ونضبط $ans := cand$ \texttt{ans} := \texttt{cand}. إذا لم يكن، نترك البتة عند $0$ في ans وننتقل إلى البتة التالية الأقل.

لأننا نعالج البتات من الأكثر أهمية إلى الأقل ونقوم بتعيين بتة فقط عندما توجد بعض التكوينات من $k$ قلبات التي تدعم جميع البتات المختارة حتى الآن، فإن ans الناتجة هي الحد الأقصى النهائي الممكن لـ AND بشكل ترتيب (وبالتالي عدديًا). لكل من مواضع البت $32$ نقوم بفحص جميع العناصر $n$ مرة واحدة، لذا فإن التعقيد العام هو $O (32 n) = O (n)$ O(32n) = O(n) من حيث الوقت و $O (1)$ ذاكرة إضافية بخلاف مصفوفة المدخلات.

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