Enigma 2026 — Editorial

Positions don't matter, only character frequencies matter.

Try building the final string by placing several copies of "ENIIGMA" one after another. Each time you place one full copy, certain characters get consumed. So how many full copies can you place before at least one required character runs out?

Because the string can be rearranged in any order, we can construct the final string in the most optimal way by placing the substring "ENIIGMA" repeatedly. Each occurrence of "ENIIGMA" requires exactly one E, one N, two I's, one G, one M, and one A. Therefore, the maximum number of times this substring can appear is limited by the character with the smallest available supply relative to its requirement.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin>>n;
        string s;
        cin>>s;
        int cntE = 0, cntN = 0, cntI = 0;
        int cntG = 0, cntM = 0, cntA = 0;
        for (char c : s) {
            if (c == 'E') cntE++;
            else if (c == 'N') cntN++;
            else if (c == 'I') cntI++;
            else if (c == 'G') cntG++;
            else if (c == 'M') cntM++;
            else if (c == 'A') cntA++;
        }
        int ans = min({
            cntE,
            cntN,
            cntI/2,
            cntG,
            cntM,
            cntA
        });
        cout<<ans<<"\n";
    }
    return 0;
}

If a[i] is known (not -1), then every element to its left cannot have any bit that is not present in a[i].

To maximize freedom and avoid contradictions, fill -1 values from the right side using the current allowed limit.

After filling, just verify the OR-prefix condition directly.

For any fixed array after replacing all -1, let the prefix OR up to index i be pi = a1 | a2 | ... | ai; the array is good iff pi = ai for every i, which immediately implies the sequence must be bitwise non-decreasing (once a bit becomes 1 in some prefix, it can never disappear later).

Using this fact, we can construct a candidate solution greedily from right to left: maintain suffix_limit, the nearest fixed value on the right (initially the maximum allowed value), and whenever we see -1 we set it to suffix_limit (choosing the largest safe value), while when we see a fixed number we update suffix_limit to that number, ensuring unknown elements never introduce bits that would contradict a future fixed value.

After reconstruction, we validate the result in one left-to-right pass by computing current_or |= a[i] and checking current_or == a[i] at every position; if any position fails, no valid filling exists and we print -1, otherwise we output the reconstructed array.

This solution runs in O(n) per test case with constant extra memory.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
 
    // Pass 1: Fill -1s backwards
    // Initialize suffix_limit to 511 (max possible value) for any trailing -1s
    int suffix_limit = 511; 
    
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == -1) {
            // Replace -1 with the limit imposed by the right side
            // maximizing the value by taking the limit itself
            a[i] = suffix_limit;
        } else {
            // Found a fixed number, this becomes the limit for elements to the left
            suffix_limit = a[i];
        }
    }
 
    // Pass 2: Validate the reconstructed array
    int current_or = 0;
    for (int i = 0; i < n; ++i) {
        current_or |= a[i];
        // The condition implies a[i] must contain all bits of the prefix OR
        if (current_or != a[i]) {
            cout << -1 << endl;
            return;
        }
    }
 
    // Pass 3: Output result
    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}
 
int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Analyze the condition $$$a_1 \mid a_2 \mid \dots \mid a_i = a_i$$$. What does this tell you about the relationship between the previous prefix OR ($$$P_{i-1}$$$) and the current element $$$a_i$$$? It implies $$$P_{i-1} \subseteq a_i$$$. Consequently, we are looking for a chain of elements where each is a submask of the next.

To minimize modifications, we must maximize the number of elements we keep. The problem transforms into finding the Longest Chain of Subsets $$$x_1 \subseteq x_2 \subseteq \dots \subseteq x_k$$$ using elements from the array.

Since we are calculating the Maximum length, overlaps between subproblems do not result in overcounting (unlike Sum operations). Consider the numerical order of masks. If $$$A \subset B$$$, then $$$A \lt B$$$. How does this allow us to solve the problem with a simple linear iteration?

Let the sequence we construct be $$$b_1, b_2, \dots, b_k$$$. The condition $$$b_1 \mid \dots \mid b_i = b_i$$$ simplifies to the requirement that each element must be a supermask of the previous element:

where $$$A \subseteq B$$$ means (A & B) == A.

To minimize modifications, we maximize the length of this chain, $$$k$$$. The answer will be $$$N - k$$$.

DP State & Transition

We can use Dynamic Programming on the bitmasks.

Let $$$dp[mask]$$$ be the length of the longest valid chain ending with a value $$$v$$$ such that $$$v \subseteq mask$$$.

Let $$$cnt[mask]$$$ be the frequency of $$$mask$$$ in the input.

The transition is:

If $$$cnt[mask] = 0$$$, we set $$$dp[mask] = \max(\dots)$$$ without adding anything. This allows the mask to serve as a "bridge" in the chain for larger numbers.

For given Max problem, overlaps are harmless ($$$\max(x, x) = x$$$). Furthermore, since any submask is numerically smaller than its supermask ($$$S \subset M \implies S \lt M$$$), a simple linear iteration from $$$0$$$ to $$$2^{20}-1$$$ guarantees the necessary topological order. Checking only immediate submasks is sufficient.

Time Complexity: $$$O(V \log V)$$$ where $$$V = 2^{20}$$$.

#include <bits/stdc++.h>
using namespace std;
const int K = 20;
const int M = 1 << K;
int dp[M], cnt[M];
void solve() {
    int n;
    cin >> n;
    
    memset(dp, 0, sizeof(dp));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    for(int i = 0; i < M; i++) {
        int best_prev = 0;
        for(int j = 0; j < K; j++) {
            if((i >> j) & 1) {
                best_prev = max(best_prev, dp[i ^ (1 << j)]);
            }
        }
        
        if(cnt[i] > 0) dp[i] = best_prev + cnt[i];
        else dp[i] = best_prev;
        if(cnt[i] > 0) ans = max(ans, dp[i]);
    }
    cout << n - ans << "\n";
}
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

Using two minimum queries among three indices is enough to determine which index contains the smallest value.

Always keep exactly two unresolved indices. For every new index, compare it with the current pair and permanently determine one value. This guarantees at most 2(n−2) Type 1 queries.

Maintain two candidate indices l and r whose values are still unknown. Initially set l = 1 and r = 2. For each i from 3 to n, we compare the triple (l, r, i).

Ask: - x = min(p_l, p_r) - y = min(p_r, p_i)

From these two values we can deduce the smallest element among the three.

• If x < y, then p_l = x because both p_r and p_i are at least y > x. We fix l. Since both r and i are still unresolved, we keep them as the new candidates by setting l = r and r = i.
• If x > y, then p_i = y. The new index is immediately determined, so we keep the old pair (l, r) unchanged.
• If x = y, the common element in both queries is r. Since all values are distinct, this equality is only possible if p_r = x. We fix r and replace it with the new index by setting r = i.

Thus, every iteration fixes exactly one value while preserving two unknown indices. Each step uses two Type 1 queries, so the total number is 2(n-2) ≤ 2n.

After the loop, only l and r remain unknown. We use the single Type 2 query to obtain p_l exactly. The remaining unused value must belong to r.

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
 
    int n;
    cin >> n;
    int l = 1, r = 2;
    vector<int>ans(n+1, 0);
    int x, y;
    vector<int>done(n+1, 0);
    for(int i = 3; i<=n; i++){
        cout << "? 1 " << l << " " << r << endl;
        cin >> x;
        cout << "? 1 " << r << " " << i << endl;
        cin >> y;
        if(x<y){
            ans[l] = x;
            done[x] = 1;
            l = r;
            r = i;
        }
        else if(x==y){
            ans[r] = x;
            done[x] = 1;
            r = i;
        }
        else{
            ans[i] = y;
            done[y] = 1;
        }
    }
    cout << "? 2 " << l << endl;
    cin >> x;
    done[x] = 1;
    ans[l] = x;
    for(int i = 1; i<=n; i++){
        if(!done[i]){
            done[i] = 1;
            ans[r] = i;
            break;
        }
    }
    cout << "! ";
    for(int i = 1; i<=n; i++) cout << ans[i] << " ";
    cout << endl;
 
    return 0;
}

Ignore the "emotions" and look at the interactions as numerical transitions. Every state change is binary. Try assigning a value to H and a different value to S and N. Notice how two people interacting always results in a state that depends on whether their initial states were the same or different.

If you map Happy (H) = 1 and both Sad (S) and Neutral (N) = 0, the dating rules follow the XOR ($$$\oplus$$$) truth table: - $$$H(1) \oplus H(1) = S(0)$$$ - $$$H(1) \oplus S(0) = H(1)$$$ - $$$N(0) \oplus H(1) = H(1)$$$ - $$$N(0) \oplus N(0) = N(0)$$$

Because every group dates every other group in the subset exactly once, the final state of a group is effectively the XOR sum of every group mask included in that subset.

For a subset to be valid, every person must end up in state H (1).

This means for a chosen subset of masks $$${M_1, M_2, \dots, M_k}$$$, the following must hold for every single person:

Where the Target Mask is a bitmask of all ones ($$$2^m - 1$$$). The problem is now: find the number of non-empty subsets whose elements XOR together to equal this target.

The Solution

1. Binary Mapping

The interaction rules for the emotional states exactly follow the XOR ($$$\oplus$$$) operation if we map: - Happy (H) = 1 - Sad (S) / Neutral (N) = 0

2. Subset Invariance

In a subset of groups where every pair dates once, every group in that subset ends up with the same final state. This final state is the XOR sum of all initial masks in that subset. For every person to be Happy, the XOR sum must equal the Target Mask (all 1s).

3. Linear Basis

The problem becomes: Count how many subsets have an XOR sum of $$$(2^m - 1)$$$.

• Insert the $$$n$$$ masks into a Linear Basis of size $$$m$$$.
• Let $$$r$$$ be the rank (number of elements in the basis).
• Check if the Target Mask is in the span of the basis. If not, the answer is 0.
• If it is, there are $$$2^{n-r}$$$ valid subsets (mod $$$10^9+7$$$).

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> basis(m, 0);
    int rank = 0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int mask = 0;
        for (int j = 0; j < m; ++j) {
            if (s[j] == 'H') {
                mask |= (1 << j);
            }
        }
        for (int j = m - 1; j >= 0; --j) {
            if (!(mask & (1 << j))) continue;
            if (!basis[j]) {
                basis[j] = mask;
                rank++;
                break;
            }
            mask ^= basis[j];
        }
    }
    int target = (1 << m) - 1;
    for (int j = m - 1; j >= 0; --j) {
        if (!(target & (1 << j))) continue;
        if (!basis[j]) {
            cout << 0 << endl;
            return 0;
        }
        target ^= basis[j];
    }
    if (target == 0) {
        cout << power(2, n - rank) << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}