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 most optimally 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 <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
 
    int suffix_limit = 511; 
    
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == -1) {
            a[i] = suffix_limit;
        } else {
            suffix_limit = a[i];
        }
    }
 
    int current_or = 0;
    for (int i = 0; i < n; ++i) {
        current_or |= a[i];
        if (current_or != a[i]) {
            cout << -1 << endl;
            return;
        }
    }
 
    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

For each row $$$i$$$, you have two choices: XOR it with $$$N$$$ or leave it. For each column $$$j$$$, you XOR it with $$$M$$$ or leave it. This gives $$$2^N$$$ row configurations and $$$2^M$$$ column configurations.

Let $$$r_i \in {0, 1}$$$ and $$$c_j \in {0, 1}$$$ represent the choice for row $$$i$$$ and column $$$j$$$. The value at any cell $$$(i, j)$$$ becomes $$$A_{i,j}' = A_{i,j} \oplus (r_i \cdot N) \oplus (c_j \cdot M)$$$. We need to count how many unique sets of $$$A'$$$ exist.

If $$$N \neq M$$$, a row operation (adding $$$N$$$) can never be canceled out or replicated by a column operation (adding $$$M$$$). Thus, every unique combination of choices $$$(r, c)$$$ produces a unique matrix.

If $$$N = M$$$, the operations become linked. XORing all rows and all columns simultaneously results in every cell being XORed by $$$N \oplus N = 0$$$. This means two different sets of choices produce the exact same matrix, halving the total count.

The total number of possible operation combinations is $$$2^N \times 2^M = 2^{N+M}$$$. We only care if different combinations result in the same matrix.

Case 1: $$$N \neq M$$$ Since $$$N$$$ and $$$M$$$ are distinct, the row-wise XORs and column-wise XORs are linearly independent. No combination of column flips can mimic a row flip. Every one of the $$$2^{N+M}$$$ combinations leads to a unique matrix.

Case 2: $$$N = M$$$ In this case, row operations and column operations use the same XOR value. If you flip every row ($$$N \oplus \dots \oplus N$$$) and every column ($$$N \oplus \dots \oplus N$$$), the total change at any cell $$$(i, j)$$$ is $$$N \oplus N = 0$$$. Because this "all-flip" results in the identity matrix, exactly half of the $$$2^{N+M}$$$ combinations are redundant.

#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;
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x; cin >> x;
        }
    }

    if (n == m) {
        cout << power(2, n + m - 1) << "\n";
    } else {
        cout << power(2, n + m) << "\n";
    }
}

int main() {
    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$$$.

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;
}

If you add an element to a set, the MEX can only stay the same or increase. Therefore, the MEX of $$$a[i \dots i+x-1]$$$ is monotonically non-decreasing with respect to $$$x$$$.

If the MEX of every single subarray is non-decreasing as $$$x$$$ increases, what does that mean for the average, $$$f(x)$$$? Try binary search.

For a window of size $$$x$$$, the maximum possible MEX is $$$x$$$. This happens if the subarray contains exactly the elements $$${0, 1, 2, \dots, x-1}$$$. Any value in the array $$$a_i \gt x$$$ can never be the MEX, nor can it influence the MEX.

The solution relies on the monotonicity of the Minimum Excluded value (MEX): as a subarray grows, its MEX can only stay the same or increase. This ensures that $$$f(x)$$$—the average MEX of all subarrays of length $$$x$$$—is also non-decreasing, allowing for a Binary Search to find the smallest $$$x \in [1, n]$$$ where $$$f(x) \ge k$$$. Once the search concludes, we simply verify if $$$f(ans)$$$ matches $$$k$$$ exactly.

To calculate $$$f(x)$$$ efficiently during each check, we employ a sliding window paired with a frequency vector and a std::set containing all "missing" integers in the range $$$[0, x]$$$. Since a subarray of length $$$x$$$ cannot have a MEX greater than $$$x$$$, we ignore all elements $$$a_i \gt x$$$. As the window shifts, we update the frequency of entering and exiting elements; if a count drops to zero, that number is added to the set, and if it increases from zero, it is removed. The current MEX is always the smallest element in the set, accessed via *missing.begin().

Each of the $$$O(\log n)$$$ binary search steps involves a single $$$O(n)$$$ pass over the array. Within that pass, set operations take $$$O(\log x)$$$ time, resulting in a total time complexity of $$$O(n \log n \log n)$$$. This is well within the 5-second time limit, providing a robust and efficient solution for the editorial.

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

ll compute_f(const vector<int>& a, int n, int x) {
    int windows = n - x + 1;
    if (windows <= 0) return 0;
    vector<int> freq(x + 1, 0);
    set<int> missing;
    
    for (int i = 0; i <= x; ++i) {
        missing.insert(i);
    }
    for (int i = 0; i < x; ++i) {
        if (a[i] <= x) {
            if (freq[a[i]] == 0) {
                missing.erase(a[i]);
            }
            freq[a[i]]++;
        }
    }
    ll sum_mex = *missing.begin();
    for (int i = 1; i < windows; ++i) {
        int old_val = a[i - 1];
        if (old_val <= x) {
            freq[old_val]--;
            if (freq[old_val] == 0) {
                missing.insert(old_val);
            }
        }
        int new_val = a[i + x - 1];
        if (new_val <= x) {
            if (freq[new_val] == 0) {
                missing.erase(new_val);
            }
            freq[new_val]++;
        }
        
        sum_mex += *missing.begin();
    }
    return sum_mex / windows;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        int lo = 1, hi = n, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (compute_f(a, n, mid) >= k) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (ans != -1 && compute_f(a, n, ans) == k) {
            cout << ans << "\n";
        } else {
            cout << -1 << "\n";
        }
    }
    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 interaction rules for the emotional states exactly follow the XOR ($$$\oplus$$$) operation if we map Happy (H) = 1 and Sad (S) / Neutral (N) = 0.

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).

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;
}