Aiuto "casino" 2WA

Aiuto
1

Nel problema casino, implementando string hashing buco esattamente due test case (uno nel 3o e uno nel 5o subtask).
Ho scritto due implementazioni che generano le hash di tutte le “rotazioni” di una stringa:

  • compute_hashes_naive computa la hash di ogni rotazione con l’algoritmo standard
  • compute_hashes_smart utilizza una prefix sum per computarle tutte in O(N)

La naive sbaglia uno di tc menzionati prima (nell’altro fa TLE).
Forse il problema potrebbe essere che per come ho scelto P e MOD piu’ stringhe potrebbero corrispondere alla stessa hash?
Grazie in anticipo!

source code:

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <map>

using namespace std;
using ll = long long;
constexpr ll P = 31;
constexpr ll MOD = 1e9 + 9;

vector<ll> compute_hashes_smart(vector<ll>& sv) {
    int M = sv.size();
    // init prefix sum of hash
    vector<ll> ps(M);
    ps[0] = sv[0];
    ll ppow = 1;
    for (int j = 1; j < M; j++) {
        ppow *= P;
        ppow %= MOD;
        ps[j] = ps[j-1] + sv[j]*ppow;
        ps[j] %= MOD;
    }
    vector<ll> hashes;
    ll pref = 0;
    ppow = 1;
    for (int j = M-1; j >= 0; j--) {
        hashes.push_back(((ps[j]*ppow)%MOD + pref) % MOD);
        pref *= P;
        pref += sv[j];
        pref %= MOD;
        ppow *= P;
        ppow %= MOD;
    }
    return hashes;
}

vector<ll> compute_hashes_naive(vector<ll>& sv) {
    int M = sv.size();
    vector<ll> hashes;
    for (int i = 0; i < M; i++) {
        hashes.push_back(0LL);
        ll ppow = 1LL;
        for (int j = 0; j < M; j++) {
            hashes.back() = (hashes.back() + sv[(i+j)%M] * ppow) % MOD;
            ppow = (ppow * P) % MOD;
        }
    }
    return hashes;
}

int main() {
    int N, M; cin >> N >> M;
    map<ll,ll> types;
    for (int i = 0; i < N; i++) {
        vector<ll> sv(M);
        for (auto& x: sv) {
            char c; cin >> c;
            x = c - 'a' + 1;
        }
        // compute all hashes
        // auto hnaive = compute_hashes_naive(sv);
        auto hsmart = compute_hashes_smart(sv);

        auto hashes = hsmart;

        // update current standings
        bool found = false;
        for (auto h: hashes) {
            if (types.count(h) > 0) {
                found = true;
                types[h]++;
                break;
            }
        }
        if (!found) types[hashes[0]] = 1;
    }
    // compute pairs
    ll tot = 0;
    for (auto[k,v]: types) tot += v * (v-1) / 2;
    cout << tot << endl;
}
2

Il fix era prendere per ogni stringa la hash minima in modo da minimizzare potenziali sovrapposizioni.
Si ringrazia @MatteoArcari per l’aiuto, molto piu’ rapido ed efficacie che quello di @BestCrazyNoob.

1 Mi Piace