Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Se memorizziamo il grafo con una Matrice di adiancenza possiamo verificare se un certo gruppo di 4 persone forma un "gruppo vacanza perfetto" facendo una piccola osservazione.
Prendiamo ad esempio uno degli input forniti dal problema:
N=5 M=6
4 0
3 4
1 2
1 4
3 2
0 2
Convertendolo in una matrice di adiacenza, otteniamo:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | ☑️ | ☑️ | |||
| 1 | ☑️ | ☑️ | |||
| 2 | ☑️ | ☑️ | ☑️ | ||
| 3 | ☑️ | ☑️ | |||
| 4 | ☑️ | ☑️ | ☑️ |
Scegliamo ora un gruppo di 4 amici che indicheremo con [i, j, k, l]. Possiamo notare che verificare se questo è un "gruppo vacanza perfetto" vuol dire semplicemente verificare che ogni amico abbia un'adiacenza con esattamente 2 dei 3 altri membri del gruppo.
Indicando (come si fa di solito) le adiacenze con valori 0 e 1 nella matrice, quello che dobbiamo verificare è che la somma delle adiacenze sia pari a 2.
La condizione da verificare sarà qualcosa di questo tipo:
condizione = (
adj[i][j] + adj[i][k] + adj[i][l] == 2
&& adj[j][i] + adj[j][k] + adj[j][l] == 2
&& adj[k][i] + adj[k][j] + adj[k][l] == 2
&& adj[l][i] + adj[l][j] + adj[l][k] == 2
);
Una possibile soluzione (non ottimale) è quindi quella di eseguire questo controllo per tutte le possibili quadruple [i, j, k, l].
Il controllo si fa in tempo costante (sono una manciata di somme e confronti) ma le quadruple esistenti sono, naturalmente, dell'ordine di . Questa è quindi la complessità della soluzione proposta.
Nota che quando una soluzione quartica può impiegare molto tempo. Certo, è vero che in gara si aveva molto tempo a disposizione per calcolare l'output corretto (potenzialmente anche delle ore) però non è garantito che si riescano a risolvere tutti i testcase nel tempo disponibile.
Invece di provare tutte le quadruple di nodi () proviamo tutte le coppie di archi (). I vantaggi sono che:
Questa soluzione ha complessità ma richiede l'utilizzo delle Liste di adiacenza (in aggiunta alla Matrice di adiacenza che già usiamo) ed un po' più di attenzione nell'implementazione.
#include <iostream>
#include <cstring>
using namespace std;
bool adj[1500][1500];
int solve() {
// Azzera la matrice di adiacenza
memset(adj, 0, sizeof adj);
int N, M;
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
// Riempi la matrice di adiacenza
adj[a][b] = adj[b][a] = 1;
}
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
for (int k = j + 1; k < N; ++k) {
for (int l = k + 1; l < N; ++l) {
int c_i = adj[i][j] + adj[i][k] + adj[i][l];
int c_j = adj[j][i] + adj[j][k] + adj[j][l];
int c_k = adj[k][i] + adj[k][j] + adj[k][l];
int c_l = adj[l][i] + adj[l][j] + adj[l][k];
// Controlla che ogni membro abbia esattamente 2 amici
if (c_i == 2 && c_j == 2 && c_k == 2 && c_l == 2) {
ans += 1;
}
}
}
}
}
return ans;
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; ++t) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
#include <cstring>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;
bool adj[1500][1500];
void solve(int t) {
// Azzera matrice di adiacenza
memset(adj, 0, sizeof(adj));
int N, M;
cin >> N >> M;
vector<pair<int, int>> E;
E.reserve(M);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
// Salta archi "equivalenti"
if (adj[a][b]) continue;
// Riempi matrice di adiacenza
adj[a][b] = adj[b][a] = true;
// Popola anche lista di adiacenza
E.emplace_back(a, b);
}
int risposta = 0;
for (int i = 0; i < M; i++) {
auto [a1, b1] = E[i];
for (int j = i + 1; j < M; j++) {
auto [a2, b2] = E[j];
// Evita i casi in cui i due archi non identificano 4 persone diverse
if (a1 == a2 || a1 == b2) continue;
if (b1 == a2 || b1 == b2) continue;
// Controlla queste 4 persone
if (adj[a1][a2] && adj[b1][b2] && !adj[a1][b2] && !adj[b1][a2]) risposta++;
if (!adj[a1][a2] && !adj[b1][b2] && adj[a1][b2] && adj[b1][a2]) risposta++;
}
}
// Dobbiamo dimezzare perché abbiamo contato due volte ogni gruppo
risposta /= 2;
cout << "Case #" << t << ": " << risposta << "\n";
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
}