Editorial (non ufficiale) Territoriali 2020
Pesci
Descrizione del problema
Ci sono N pesci in un lago.
Ogni giorno i pesci formano gruppi di K pesci e depongono un uovo. Un pesce fa parte di al più un gruppo.
I pesci che non riescono a formare un gruppo non depongono uova.
Al termine del giorno ogni pesce presente viene rimosso.
Il giorno seguente le uova presenti si schiudono e sì ripete lo stesso procedimeto.
Quanti pesci sono stati presenti nel lago?
Soluzione
Idea
Il problema è abbastanza banale, basta implementare ciò che è stato esplicitato nel problema.
- Contare quanti gruppi di K pesci si riesce a formare (basta una divisione).
- Si aggiunge alla risposta globale il numero di pesci presenti nel lago.
- Il numero di pesci del lago diventa il numero di gruppi formati.
- Ripetere dal primo punto se il numero di pesci è maggiore di zero.
- Stampare la risposta globale.
Codice
#include <bits/stdc++.h>
using namespace std;
int main(){
int tt;
cin >> tt;
for(int t = 1; t <= tt; t++){
// input
int n, k;
cin >> n >> k;
long long ans = 0;
do{
long long uova = n / k;
ans += n;
n = uova;
}while(n > 0);
// output
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
Analisi temporale e spaziale (per testcase)
Temporale: O(log_{K}(N))
Spaziale: O(1)
Social
Introduzione
In un social network ci sono N persone.
Di ogni persona si conosce quanti A_{i} follwer ha.
Ogni persona segue esattamente un’altra persona (che non sia se stessa). Ma non si sa quale.
Fornire una configurazione possibile in cui ogni persona segue esattamente un’altra rispettando il numero di follwer di ognuno.
Soluzione
Idea
Esistono molteplici configurazioni valide ma a noi interessa trovarne una qualsiasi.
Ipotizziamo inizialmente di avere un insieme S in cui sono presenti tutte le persone. Questo insieme rappresenta le persone che al momento non stanno seguendo nessuno.
Se non avessimo avuto la restrizione che una persona non può seguire se stessa, avremmo potuto far seguire a A_i elementi (non importa quali) la persona i e rimuoverli dal insieme. Ripetere per ogni persona.
Il procedimento esplicitato è abbastanza semplice, se riuscissimo a “rimuovere” questa restrizione abbiamo risolto il problema.
Per farlo basta eliminare dall’insieme S tutte le persone che abbiano almeno un follower.
Perchè? Se la persona i (con A_i > 0) non è presente, non possiamo erroneamente prenderla e assegnerla a se stessa.
Creiamo un insieme Z in cui sono presenti tutte le persone che abbiano almeno un follower. Di questo nuovo insieme dobbiamo far in modo tale che ogni persona venga seguita solotanto da un’altra.
Perché? Se ogni persona è seguita da solo un’altra diminiuiamo di 1 il numero di follwer di ognuno e ognuno seguirà esattamente un’altra persona.
Per farlo, un modo semplice è immaginare di disporre queste persone in cerchio e assegnare ad ognuna la persona alla propria destra.
Ora possiamo seguire il procedimento generale sottranedo a S l’insieme Z e ricordando di assegnare una persona in meno per ogni A_i positivo.
Codice
#include <bits/stdc++.h>
using namespace std;
int main(){
int tt;
cin >> tt;
for(int t = 1; t <= tt; t++){
// input
int n;
cin >> n;
vector <int> a(n, 0);
for(int &i : a){
cin >> i;
}
vector <int> f(n, -1);
vector <int> seguito;
for(int i = 0; i < n; i++){
if(a[i] == 0)continue;
seguito.push_back(i);
}
vector <bool> assegnato(n, false);
// Evito di far seguire alla persona se stessa
for(int i = 0; i < (int) seguito.size(); i++){
int persona = seguito[i];
int daSeguire = seguito[(i + 1) % (int) seguito.size()];
f[persona] = daSeguire;
assegnato[persona] = true;
// diminuisco il numero di follower della persona appena seguita
a[daSeguire]--;
}
// Ora posso assegnare a caso le restanti persone
for(int i = 0, j = 0; i < n; i++){
while(a[i] > 0){
// trova la prima persona che non segue
while(assegnato[j]){
j++;
}
assegnato[j] = true;
f[j] = i;
a[i]--;
}
}
// output
cout << "Case #" << t << ": ";
for(int i = 0; i < n; i++){
cout << f[i] << " ";
}
cout << '\n';
}
return 0;
}
Analisi temporale e spaziale (per testcase)
Temporale: O(N)
Spaziale: O(N)
Mostra
Descrizione del problema
Ad una mostra sono presenti due file: una con N turisti, ognuno con un grado di preprazione V_i; l’altra con M volontari e un grado di preparazione G_i.
Per ovvie ragioni le due file non possono essere riordinate e l’accesso alla mostra è consentito a una persona per volta oppure abbinando a un tursita un volontario.
L’abbinamento tra turista e volontario è possibile solo se V_i < G_j.
Se un turista entra da solo la mostra guadagnerà 1 euro; invece se entra accompagnato da una guida guadagnerà 2 euro.
Se entra semplicmente un volontario la mostra non guadagnerà niente.
Qual’è il guadagno massimo facendo entrare le persone in modo ottimale?
Soluzione
Idea
Già da come è posto il problema ci dovrebbe indurre a risolverlo con la tecnica della programmazione dinamica. Stiamo cercando la soluzione ottimale. Basta simulare tutte le mosse e prendere la migliore.
Sì procede identificando lo stato di un sottoproblema. In questo caso è molto semplice: in che punto è ferma la fila dei turisti e quella dei volontari in questo momento? Identificabile come la coppia (i,j) dove i rappresenta la posizione della fila dei turisti mentre j i volontari.
Sì decide quale informazione associare alla coppia (i, j). Siccome stiamo cercando il gudagano massimo tale coppia assumerà tale valore.
Deciso lo stato e l’informazione che contiene bisogna capire come calcolarle il valore da associare alla coppia. Si trovano i casi base e le transizioni.
Il caso base è quando entrambe le file sono vuote e il guadagno è pari a zero (i, j) = (N, M) \Rightarrow 0.
Mentre le transizioni possibili sono:
- Far avanzare un turista (i, j) \rightarrow (i + 1, j).
- Far avanzare un volontario (i, j) \rightarrow (i, j + 1).
- Abbinare turista e volontario (i, j) \rightarrow (i + 1, j + 1).
Trovate la transazioni come assegno il valore ottimale alla coppia (i, j)? Semplicmente assegnadole il massimo delle possibili scelte.
La risposta al problema sarà data dal cacolo della coppia (0,0).
Nella implementazione di questa soluzione, la coppia (i,j) la si può rappresentare come una matrice N \times M e il calcolo tramite una funzione ricorisva che memorizza i risultati nella matrice.
Per evitare problemi di “lentezza” di esecuzione basta non far richiamare la funzione con coppie già calcolate.
Codice
#include <bits/stdc++.h>
using namespace std;
int dp(int n, int m, int i, int j, vector < vector <int> > &memo, vector <int> &v, vector <int> &g){
if(i == n && j == m)return 0;
int &ret = memo[i][j];
if(ret != -1)return ret;
ret = 0;
// skippo il volontario
if(j < m)ret = max(ret, dp(n, m, i, j + 1, memo, v, g));
// mando da solo il turista
if(i < n)ret = max(ret, dp(n, m, i + 1, j, memo, v, g) + 1);
// combino i due
if(i < n && j < m && g[j] > v[i])ret = max(ret, dp(n, m, i + 1, j + 1, memo, v, g) + 2);
return ret;
}
int main(){
int tt;
cin >> tt;
for(int t = 1; t <= tt; t++){
// input
int n, m;
cin >> n >> m;
vector <int> v(n);
for(int &i : v){
cin >> i;
}
vector <int> g(m);
for(int &i : g){
cin >> i;
}
vector < vector <int> > memo(n + 2, vector <int> (m + 2, -1));
int ans = dp(n, m, 0, 0, memo, v, g);
// output
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
Analisi temporale e spaziale (per testcase)
Temporale: O(N \times M)
Spaziale: O(N \times M)
Interrutori
Descrizione del problema
Sono presenti N lampadine e 2 tipi di interruttori, il primo permette di invertire lo stato di una lampadina mentre il secondo inverte contemporaneamente lo stato di 2 lampadine. Esistono A interruttori del primo tipo e B interruttori del secondo tipo che regolano il comportamento delle N lampadine. L’obiettivo è trovare quale delle N lampadine, se fosse l’unica lampadina accesa, richiederebbe il numero massimo di interruttori per spegnere tutte le lampadine e quanti ne richiederebbe.
Soluzione
Idea
Per risolvere il seguente problema è molto comodo astrarre l’insieme di lampadine ed interruttori di tipo 2 e pensarli come se fossero un grafo, dove le lampadine formano N nodi e gli interruttori di tipo 2 formano B archi (se esiste un interruttore di tipo 2 che inverte contemporaneamente lo stato della lampadina x e quello della lampadina y allora creiamo un arco tra i nodi delle lampadine x e y), creiamo inoltre l’insieme T contenente tutte le lampadine a cui è associato un interruttore di tipo 1.
Cerchiamo ora di capire come utilizzare tale grafo per risolvere il seguente problema: dato il grafo e sapendo che solo 1 di quelle N lampadine (supponiamo la lampadina s) è accesa trovare il numero minimo di mosse (consideriamo l’utilizzo di un interruttore come una mossa) per spegnere tutte le lampadine.
È facile notare che se s \in T allora basterà premere il relativo interruttore. Altrimenti notiamo che per spegnere tutte le lampadine è necessario continuare a premere interruttori di tipo 2 che invertono lo stato della lampadina attualmente accesa e una delle sue “vicine” fino ad arrivare ad una lampadina che appartiene a T. Ma allora, riferendoci al grafo appena creato, quello che stiamo cercando è il percorso minimo che va dalla lampadina s ad una lampadina appartenente a T.
Cerchiamo quindi di risolvere il problema originale utilizzando i ragionamenti fatti prima, possiamo innanzitutto riformulare il problema in: dato il grafo descritto precedentemente trovare il nodo il cui percorso minimo verso un nodo di T è massimo. Siamo quindi interessati a ottenere per ogni nodo del grafo la distanza minima da un nodo di T. L’approccio più banale consiste nel eseguire una BFS a partire da ogni nodo e trovare la sua distanza minima da un nodo di T, tale approccio però ha complessità O(NB) che è decisamente troppo elevata.
Per velocizzare l’approccio la soluzione prevede una BFS che ha come sorgenti i nodi di T e che visita tutto il grafo, in questo modo possiamo sapere per ogni nodo la distanza dal nodo di T a lui più vicino, prendere la distanza maggiore trovata ed aggiungere 1 (deve essere premuto l’interruttore per spegnere l’ultima lampadina).
Codice
#include <bits/stdc++.h>
using namespace std;
int main(){
int tt;
cin >> tt;
for(int t = 1; t <= tt; t++){
// Input
int n, a, b;
cin >> n >> a >> b;
vector <int> z(a);
for(int &i : z){
cin >> i;
}
vector <int> x(b), y(b);
for(int i = 0; i < b; i++){
cin >> x[i] >> y[i];
}
// Costruisco il grafo
vector < vector <int> > adj(n);
for(int i = 0; i < (int) x.size(); i++){
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
// Multisource bfs
vector <int> dista(n, -1);
queue <int> q;
for(int i : z){
dista[i] = 1;
q.push(i);
}
while(!q.empty()){
int node = q.front();
q.pop();
for(int i : adj[node]){
if(dista[i] == -1){
dista[i] = dista[node] + 1;
q.push(i);
}
}
}
// Output
int ans = max_element(dista.begin(), dista.end()) - dista.begin();
cout << "Case #" << t << ": " << ans << " " << dista[ans] << '\n';
}
return 0;
}
Analisi temporale e spaziale (per testcase)
Temporale: O(N + B)
Spaziale: O(N + B)
Ringrazio @frakkiobello per aver contruibito all’editorial.
Mi era venuta voglia di farlo dopo aver letto un post recente lol
Ogni domanda è ben accetta.