Ciao a tutti, avevo bisogno di aiuto per risolvere christmas balls, perché riesco a risolvere tutti i testcase tranne l’ultimo, che va in exe timed out.
Questa era la soluzione originale che avevo pensato:
// NOTE: it is recommended to use this even if you don't understand the
// following code.
#include <bits/stdc++.h>
using namespace std;
// input data
int N;
vector<int> C;
vector<int> P;
// aggiunge gli elementi della seconda mappa alla prima
void add(unordered_map<int, int> &x, unordered_map<int, int> &y)
{
for (auto i = y.begin(); i != y.end(); i++)
{
x[i->first] += y[i->first];
}
}
unordered_map<int, vector<int>> tree;
unordered_map<int, int> post(int i);
// contiene il punteggio massimo globale
int ans = 1;
int main()
{
cin >> N;
C.resize(N);
P.resize(N);
for (int i = 0; i < N; i++)
{
// node i has color C[i]
cin >> C[i];
}
for (int i = 1; i < N; i++)
{
// there is a link P[i] -> i
// note: P[0] is undefined!
cin >> P[i];
tree[P[i]].push_back(i);
}
// insert your code here
post(0);
cout << ans << endl; // print the result
return 0;
}
// il concetto base della mia soluzione è:
// utilizzo una mappa per contare le occorrenze dei colori e di conseguenza poter
// trovare la frequenza massima e la frequenza della frequenza massima scorrendo la mappa.
// per ogni padre prendo le mappe dei figli e le unisco in una mappa nuova
// dopodiché trovo il risultato nella mappa nuova, e se è meglio del risultato massimo, aggiorno
unordered_map<int, int> post(int i)
{
unordered_map<int, int> m;
if (tree[i].size() == 0)
{
// e' una foglia
m[C[i]] = 1;
return m;
}
// recupero i figli di questo nodo
vector<int> neigh = tree[i];
// visito ogni figlio e unisco insieme tutte le mappe
for (int next : neigh)
{
unordered_map<int, int> figlio;
figlio = post(next);
add(m, figlio);
}
// aggiorno la mappa mettendo dentro il colore di questo nodo
m[C[i]]++;
// cerco la frequenza della frequenza massima
int high = 0;
int cont = 0;
for(auto i = m.begin(); i!=m.end(); i++)
{
int freq = i->second;
if(freq > high)
{
// se trovo una nuova frequenza massima, devo ricominciare a contare da 0
high = freq;
cont = 0;
}
if(freq == high)
{
cont++;
}
}
// utilizzo una variabile globale per semplicità
// se il punteggio di questo nodo è maggiore del massimo precedente, aggiorno
if(cont > ans) ans = cont;
// ritorno la mappa così il padre di questo nodo potrà usarla per calcolare il suo punteggio
return m;
}
Il problema di questa soluzione erano, ovviamente oltre all’ultimo testcase, tutti quelli con l’albero formato da una lista e con N abbastanza grande (in parole povere subtask 3).
Per risolvere ho semplicemente aggiunto un controllo sull’input che mi dice se l’albero è in realtà una lista, e nel caso lo fosse, utilizzo una funzione che più semplice che riesce a sfruttare le proprietà che ha una lista in questo problema.
int main()
{
cin >> N;
C.resize(N);
P.resize(N);
for (int i = 0; i < N; i++)
{
// node i has color C[i]
cin >> C[i];
}
// se true, indica che l'albero e' in realtà una linked list
bool notALine = false;
for (int i = 1; i < N; i++)
{
// there is a link P[i] -> i
// note: P[0] is undefined!
cin >> P[i];
if(P[i] != i-1) notALine = true;
tree[P[i]].push_back(i);
}
// insert your code here
if(notALine)
{
post(0);
}
else
{
unordered_map<int, int > m;
postLine(N-1, m, 0, 0);
}
cout << ans << endl; // print the result
return 0;
}
// questa funzione è pensata unicamente per quando l'albero è in realtà una lista.
// il concetto di base è che ad ogni nodo, il conteggio dei colori e delle frequenze è uguale a quello
// dell'unico figlio + il colore del padre.
// ecco quindi che non serve più iterare sulla mappa delle frequenze ogni volta, ma basta semplicemente
// aggiornare il punteggio di nodo in nodo in tempo costante
void postLine(int i, unordered_map<int, int>& c, int highest, int cont)
{
// aggiorno la mappa con il colore di questo nodo
c[C[i]]++;
// se utilizzando questo nodo raggiungo una nuova frequenza massima, devo ricominciare a contare
if(c[C[i]] > highest ) highest = c[C[i]], cont = 0;
// se utilizzando questo nodo raggiungo la frequenza massima con un altro colore, incremento il punteggio
if(c[C[i]] == highest ) cont++;
// aggiorno il punteggio massimo
if(cont > ans) ans = cont;
// se non siamo alla radice, passo i miei risultati al padre, che può aggiornare il suo punteggio
if(i > 0)
{
postLine(i-1, c, highest, cont);
}
}
Adesso riesco a risolvere tutti i testcase, tranne l’ultimo. Ho fatto qualche esperimento e ho capito che l’albero nell’ultimo testcase è un binary tree con buona parte dei nodi con un figlio unico (non so se può essere utile questo dettaglio).
In ogni caso non ho idea di quale sia il problema. Ho ipotizzato che ci potesse essere un bottleneck in due parti principali: le chiamate ricorsive (molto probabile) o nell’iterare sulla mappa (non molto probabile, ho anche pensato a qualche soluzione per ottimizzare, ma non ho avuto successo). Nel caso delle chiamate ricorsive presumo sia necessario fare un po’ di pruning, ma non ho idea di come farlo. Qualche idea? Oppure magari sto andando completamente fuori strada?