Binary chess 70/100

Aiuto
1

Ciao, stavo provando a risolvere binary chess (Binary Chess), ma ottengo solo 70/100 perché ottengo output sbagliato in qualche testcase. La cosa strana è che quelli che non passano sono solo nelle prime due subtasck, mentre nelle ultime ottengo punteggio pieno.

Condivido il mio codice:

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

long long fastExp(long long base, long long exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent % 2 == 0) {
        long long temp = (fastExp(base, exponent / 2))%MOD;
        return (temp * temp)%MOD;
    } else {
        long long temp = (fastExp(base, exponent / 2))%MOD;
        return (((temp * temp)%MOD) * base)%MOD;
    }
}

int main() {
    int R, C, N;
    cin >> R >> C >> N;
    
    vector<pair<int, int>> posizioni(N);
    
    for (int i = 0; i < N; i++) {
        cin >> posizioni[i].first >> posizioni[i].second;
    }

    sort(posizioni.begin(), posizioni.end());
    
    long long K = 0;

    unordered_map<int, bool> righe, colonne, primaDiagonale, secondaDiagonale;

    for (int i = 0; i < N; i++) {
        int x = posizioni[i].first - 1;
        int y = posizioni[i].second - 1;

        int key1 = x-y;
        int key2 = x+y;

        if (!righe[x] && !colonne[y] && !primaDiagonale[key1] && !secondaDiagonale[key2]) {
            K++;
        }

        righe[x] = true;
        colonne[y] = true;
        primaDiagonale[key1] = true;
        secondaDiagonale[key2] = true;

    }

    long long res = fastExp(2, K);
    
    
    cout << res << endl;
    
    return 0;
}

In sostanza quello che faccio è cercare il numero di gruppi che non hanno interazioni tra di essi, per poi calcolare il risultato finale sapendo che ciascuno di questi può essere composto da alfieri o torri (perciò 2^k, dove k è il numero di gruppi).

Grazie.

2

Sei sicuro che aggiungendo un pezzo il numero di gruppi possa solo crescere?

3

Per rafforzare il concetto espresso da @fve5 con questo input:

10 10 8
2 6
3 7
4 9
5 2
6 3
7 8
8 5
9 4

il risultato è 8.

4

Grazie a entrambi, ho capito cosa sto sbagliando, ora provo a sistemare. Non capisco come abbia fatto a prendere comunque 70 punti :sweat_smile:

5

Ho aggiunto una nuova logica, in cui a ogni gruppo assegno un numero, che attribuirà alle righe colonne e diagonali che ricopre. Se un pezzo si trova in una casella non ancora coperta da altri pezzi assegno a questo un nuovo numero, altrimenti controllo se ci sono interazioni tra più gruppi e in tale caso riassegno lo stesso numero a tutti questi gruppi e poi decremento K di tanto quanti sono i gruppi in conflitto (-1). Purtroppo passano tutti i testcase tranne 4 e non riesco proprio a capire se ci sono casi che non sto considerando…

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

long long fastExp(long long base, long long exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent % 2 == 0) {
        long long temp = (fastExp(base, exponent / 2))%MOD;
        return (temp * temp)%MOD;
    } else {
        long long temp = (fastExp(base, exponent / 2))%MOD;
        return (((temp * temp)%MOD) * base)%MOD;
    }
}

int main() {
    int R, C, N;
    cin >> R >> C >> N;
    
    vector<pair<int, int>> posizioni(N);
    
    for (int i = 0; i < N; i++) {
        cin >> posizioni[i].first >> posizioni[i].second;
    }

    sort(posizioni.begin(), posizioni.end());
    
    long long K = 0;

    unordered_map<int, int> righe, colonne, primaDiagonale, secondaDiagonale;
    vector<int> gruppi;
    gruppi.push_back(0);

    int conta = 0;

    for (int i = 0; i < N; i++) {
        int x = posizioni[i].first - 1;
        int y = posizioni[i].second - 1;

        int key1 = x-y;
        int key2 = x+y;

        int val;

        if (!righe[x] && !colonne[y] && !primaDiagonale[key1] && !secondaDiagonale[key2]) {
            K++;
            conta ++;
            val = conta;
            gruppi.push_back(conta);
        } else {
            vector<int> ele;
            if (righe[x]) ele.push_back(gruppi[righe[x]]);
            if (colonne[y]) ele.push_back(gruppi[colonne[y]]);
            if (primaDiagonale[key1]) ele.push_back(gruppi[primaDiagonale[key1]]);
            if (secondaDiagonale[key2]) ele.push_back(gruppi[secondaDiagonale[key2]]);

            ele.erase(unique(ele.begin(), ele.end()), ele.end());
            sort(ele.begin(), ele.end());
            for (size_t j = 1; j<ele.size(); j++) {
                int v = gruppi[ele[j]];
                for (size_t e = 0; e<gruppi.size(); e++) {
                    if (gruppi[e] == v) {
                        gruppi[e] = ele[0];
                    }
                }
            }

            val = ele[0];

            int rep = ele.size();

            K -= (rep-1);
        }

        righe[x] = val;
        colonne[y] = val;
        primaDiagonale[key1] = val;
        secondaDiagonale[key2] = val;

    }

    long long res = fastExp(2, K);
    
    
    cout << res << endl;
    
    return 0;
}
6

Attento! unique comprime blocchi contigui di elementi uguali, quindi per ottenere solo un elemento per ogni valore devi sortare prima di usarlo.

Detto questo mi sembra che questa soluzione non prenda TLE solo perché i testcase del problema sono molto deboli. Ti consiglio di imparare una tecnica “standard” per contare le componenti connesse di un grafo, come la BFS o la DSU.

7

Grazie mi è bastato invertire le due righe per ottenere 100/100 …

Mi è venuto in mente dopo che avrei potuto considerarlo un grafo e non mi andava di rifare tutto. Chiaramente la mia soluzione non è quella ottimale, ma funziona haha

8

Prova a farla andare sul caso generato dal seguente programma:

R = C = 10 ** 9
N = 2 * 10 ** 5

print(R, C, N)

for i in range(N // 2):
    print(i, 2 * i)

for i in range(N // 2):
    print(N, 2 * i)
9

Effettivamente così ci mette un’eternità :weary: