Editorial for AND-Magedón

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Marco_Escandon

Problema:

Dada una secuencia $A$ ~A~ de tamaño $N$ ~N~ y un entero no negativo $K$ ~K~. Calcular el valor máximo de $S_1 \& S_2 \& \ldots \& S_K$ ~S_1 \& S_2 \& \ldots \& S_K~, donde $S$ ~S~ es una subsecuencia de $A$ ~A~ de tamaño $K$ ~K~.

Soluciones

Subtarea 1: $K = 1$ ~K = 1~

La subsecuencia tiene un solo elemento, por lo tanto, el operador $\&$ ~\&~ dará como resultado el mismo número. La respuesta es el máximo elemento de la secuencia. Complejidad: $\mathcal{O}(N)$ ~\mathcal{O}(N)~.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    int T; // Número de casos de prueba
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N;
        cin >> K;

        vector<long long> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        if (K == 1) {
            cout << *max_element(A.begin(), A.end()) << endl;
        }
    }

    return 0;
}

Subtarea 2: $K \leq \min(N,2)$ ~K \leq \min(N,2)~ y $\sum N \leq 10^3$ ~\sum N \leq 10^3~

La subsecuencia tiene dos elementos, como $\sum N \leq 10^3$ ~\sum N \leq 10^3~, se pueden probar todos los pares de elementos. Complejidad: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int T; // Número de casos de prueba
cin >> T;

while (T--) {
    int N, K;
    cin >> N;
    cin >> K;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    if (K == 1) {
        cout << *max_element(A.begin(), A.end()) << endl;
    } 
    else if(K == 2){
        long long max_val = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                max_val = max(max_val, A[i] & A[j]);
            }
        }
        cout << max_val << endl;
    }
}

return 0;
}

Subtarea 3: $\sum N \leq 20$ ~\sum N \leq 20~

Como $\sum N \leq 20$ ~\sum N \leq 20~, se pueden probar todos las subsecuencias de elementos de tamaño $K$ ~K~, usando una máscara de bits. Complejidad: $\mathcal{O}(2^n \cdot n)$ ~\mathcal{O}(2^n \cdot n)~.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

long long maxAndSubsequence(const vector<long long>& A, int K) {
    int N = A.size();
    long long max_val = 0;

    // Generar todas las posibles subsecuencias de tamaño K usando una máscara de bits
    for (int mask = 0; mask < (1 << N); mask++) {
        vector<long long> subseq;
        for (int i = 0; i < N; i++) {
            if (mask & (1 << i)) {
                subseq.push_back(A[i]);
            }
        }

        if (subseq.size() == K) {
            long long and_val = subseq[0];
            for (int j = 1; j < K; j++) {
                and_val &= subseq[j];
            }
            max_val = max(max_val, and_val);
        }
    }

    return max_val;
}

int main() {
    int T; // Número de casos de prueba
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N;
        cin >> K;

        vector<long long> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        cout << maxAndSubsequence(A, K) << endl;
    }

    return 0;
}

Subtarea 4: $\sum N^K \leq 10^6$ ~\sum N^K \leq 10^6~

Como $\sum N^K \leq 10^6$ ~\sum N^K \leq 10^6~, se pueden probar todos las subsecuencias de elementos de tamaño $K$ ~K~ (una posible implementación sería usar recursividad donde en cada nivel de la recursividad tomar un elemento nuevo). Complejidad: $\mathcal{O}(n^k \cdot n)$ ~\mathcal{O}(n^k \cdot n)~.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

void findSubsequences(const vector<long long>& A, int K, int index, vector<long long>& current, long long& max_val) {
    if (current.size() == K) {
        long long and_val = current[0];
        for (int i = 1; i < K; i++) {
            and_val &= current[i];
        }
        max_val = max(max_val, and_val);
        return;
    }

    if (index == A.size()) {
        return;
    }

    current.push_back(A[index]);
    findSubsequences(A, K, index + 1, current, max_val);
    current.pop_back();
    findSubsequences(A, K, index + 1, current, max_val);
}

long long maxAndSubsequence(const vector<long long>& A, int K) {
    long long max_val = 0;
    vector<long long> current;
    findSubsequences(A, K, 0, current, max_val);
    return max_val;
}

int main() {
    int T; // Número de casos de prueba
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N;
        cin >> K;

        vector<long long> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        cout << maxAndSubsequence(A, K) << endl;
    }

    return 0;
}

Subtarea 5: Todos los elementos de $A$ ~A~ son potencias de $2$ ~2~.

Observación 1: Sea $ans$ ~ans~ la respuesta al problema. Para que $ans$ ~ans~ en su representación binaria tenga encendido el $i-$ ~i-~ésimo bit, los $K$ ~K~ elementos deben tener encendido ese bit.

Como los números son potencias de $2$ ~2~, solo se puede tener encendido un bit a la vez. $ans$ ~ans~ será la mayor potencia de $2$ ~2~ que aparezca al menos $K$ ~K~ veces.

Solución 1: Llevar un arreglo de frecuencia para cada potencia. Complejidad: $\mathcal{O}(n)$ ~\mathcal{O}(n)~.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int T; // Número de casos de prueba
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N;
        cin >> K;

        vector<long long> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        // Llevar un arreglo de frecuencia para cada potencia de 2
        map<long long, int> frequency;
        for (int i = 0; i < N; i++) {
            frequency[A[i]]++;
        }

        long long ans = 0;
        for (const auto& [value, count] : frequency) {
            if (count >= K) {
                ans = max(ans, value);
            }
        }

        cout << ans << endl;
    }

    return 0;
}

Solución 2: Contar para cada potencia de $2$ ~2~ las ocurrencias. Complejidad: $\mathcal{O}(n \cdot 60)$ ~\mathcal{O}(n \cdot 60)~.

Subtarea 6: Sin restricciones adicionales.

Observación 2: Sea $i$ ~i~ el mayor bit que puede tener encendido $ans$ ~ans~ dado una secuencia $A$ ~A~. $ans$ ~ans~ siempre tendrá ese bit encendido, dado que si encendemos todos los bits menores que $i$ ~i~, seguirá siendo menor que $2^i$ ~2^i~.

Por lo visto en las observaciones 1 y 2, se puede llegar a la siguiente recurrencia, sea $F(i,A)$ ~F(i,A)~ como la respuesta usando solamente los primeros $i$ ~i~ bits tomando elementos de la secuencia $A$ ~A~.

$F(i,A)$ ~F(i,A)~ se dividirá en dos casos:

Se puede encender el $i-$ ~i-~ésimo bit. En ese caso, la respuesta será $F(i-1, A')$ ~F(i-1, A')~, donde $A'$ ~A'~ representa la subsecuencia formada por todos los elementos de $A$ ~A~ que tienen el $i-$ ~i-~ésimo bit encendido.
No se puede encender el $i-$ ~i-~ésimo bit. En ese caso, la respuesta será $F(i-1, A)$ ~F(i-1, A)~.

Complejidad: $\mathcal{O}(n \cdot 60)$ ~\mathcal{O}(n \cdot 60)~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long findMaxAns(int bit, const vector<long long>& A, int K) {
    if (bit < 0) {
        return 0;
    }

    vector<long long> A_prime;
    for (long long num : A) {
        if (num & (1LL << bit)) {
            A_prime.push_back(num);
        }
    }

    if (A_prime.size() >= K) {
        return (1LL << bit) | findMaxAns(bit - 1, A_prime, K);
    } else {
        return findMaxAns(bit - 1, A, K);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int T; // Número de casos de prueba
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N;
        cin >> K;

        vector<long long> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        long long ans = findMaxAns(60, A, K);
        cout << ans << endl;
    }

    return 0;
}

Implementación iterativa de la idea anterior:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("O3")
#define x first
#define y second
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ll t;
  cin >> t;
  while (t--) {
    ll n, k;
    cin >> n >> k;
    vector<ll> cad(n);
    for (int i = 0; i < n; i++) {
      cin >> cad[i];
    }
    ll ans = 0;
    for (int i = 59; i > -1; i--) {
      ll c = 0;
      ll t1 = (1LL << i);
      for (int j = 0; j < n; j++) {
        if ((t1 & cad[j]) != 0 && (cad[j] & ans) == ans) {
          c++;
          if (c == k) break;
        }
      }
      if (c >= k) {
        ans += t1;
      }
    }
    cout << ans << "\n";
  }
}

Nota: Todos los códigos excepto el último fueron generados a partir de la editorial con Copilot.

Comments

There are no comments at the moment.