Vorrei condividere le mie soluzioni per gli ultimi due problemi di questo contest che mi sono piaciuti.
Produzione di panini
Per la risoluzione di panini ho realizzato una classica dp top-down in cui si salva il risultato migliore per ogni possibile transizione di stato memorizzando i risultati intermedi.
La prima osservazione da fare è che uno stato è sicuramente rappresentanto dalla quantità di grammi di impasto rimasti, ma per quanto riguarda il ripieno?
Se dovessimo rapprsentare la quantità di grammi di impasto rimasti più il ripieno di ogni tipologia dovremmo utilizzare una matrice di ben 1000 * 100^{10} interi che ovviamente risultata troppo grande da memorizzare e calcolare. Quindi la quantità ripieno per ogni tipologia di panino è da escludere.
L’ osservazione chiave è che se diamo un ordine alla produzione di panini per tipologia riusciamo a rendere indipendente i nostri stati dalla quantità di ripieno. Se preparo il panino della tipologia A è inutile sapere quanto ripieno ho della tipologia B perché non influisce sulla produzione di A.
Facendo ciò ogni volta che si cambia tipologia di panino da produrre la quantità di ripieno disponibile corrisponde esattamente a quella data in input.
In relazione a ciò il nostro stato è rappresentato dalla quantità di grammi di impasto disponibili e dalla tipologia del panino che stiamo producendo.
Per facilitarmi la vita nella scrittura del codice ho considerato il panino vuoto come una tipologia con ripieno infinito e quantità di ripieno neccessaria pari a 0.
complessità: O(N * M)
code:
#include <bits/stdc++.h>
using namespace std;
int N,M;
#define MAXM 12
#define MAXN 10000
int memo[MAXN][MAXN];
int A[MAXM],B[MAXM],C[MAXM],D[MAXM];
int dp(int n,int m){
if(n == 0 || m == M + 1)return 0;
if(memo[n][m] != -1)return memo[n][m];
int massa = 0, g = 0, ripieno = 0,ans = 0;
// la prima iterazione richiama la miglior soluzione non producendo nessun panino di questa tipologia
while(massa <= n && ripieno <= A[m]){
ans = max(ans,dp(n - massa,m + 1) + g);
massa += C[m];
g += D[m];
ripieno += B[m];
}
memo[n][m] = ans;
return ans;
}
int main(){
int T;
cin >> T;
for(int i = 1; i <= T; i++){
// N grammi di impsato
// M numero ripieni
cin >> N >> M >> C[0] >> D[0];
B[0] = 0;
A[0] = INT_MAX;
for(int j = 1; j <= M; j++){
// A grammi di ripieno rimasti
// B grammi di ripeino per fare un panino
// C grammi di impasto per quel panino
// D vendita
cin >> A[j] >> B[j] >> C[j] >> D[j];
}
memset(memo,-1,sizeof(memo));
cout << "Case #" << i << ": " << dp(N,0) << '\n';
}
}
Scambio culturale
Il problema richiede di calcolare la distanza massima tra un docente italiano e cinese nelle varie categorie.
L’ osservazione chiave per la risoluzione di questo problema è che le categorie formano un grafo, ma non uno a caso. Il grafo che formano è un albero quindi per ogni coppia di nodi esiste un solo cammino.
Quindi potendo sapere quanto distano due categorie e che tipo di docenti siano presenti possiamo scrivere una soluzione che per ogni docente verifichi la sua distanza da quelli a cui si può abbinare.
In gara ho optato per una per una soluzione M^2 in cui per ogni categoria provo a raggiungere tutte le altre calcolando la distanza pian piano attraverso una dfs.
Nella dfs pian piano che raggiungo una nuova categoria verifico che il nodo di partenza abbia un docente italiano e quello che sto esaimnando uno cinese (e anche il contrario), se si verifica salvo la distanza massima.
Alla fine di tutti i dati relativi ai docenti serve sapere se esiste almeno un docente italiano o cinese in una determianta categoria.
complessità: O(M^2)
code:
#include <bits/stdc++.h>
using namespace std;
int N,M;
#define MAXN 1000
#define MAXM 155
// 0 italiano 1 cinese
int tipo[MAXN][2];
vector <int> adj[MAXM];
int best = 0;
void dfs(int node,int p,bool ita,bool cina,int dista){
if(cina && tipo[node][0]){
best = max(dista,best);
}
if(ita && tipo[node][1]){
best = max(dista,best);
}
for(int &i : adj[node]){
if(i == p)continue;
dfs(i,node,ita,cina,dista + 1);
}
}
int solve(){
best = 0;
for(int i = 0; i <= M; i++){
dfs(i,-1,tipo[i][0],tipo[i][1],0);
}
return best;
}
int main(){
int T;
cin >> T;
for(int i = 1; i <= T; i++){
memset(tipo,false,sizeof(tipo));
for(int i = 0; i < MAXM; i++){
adj[i].clear();
}
cin >> N >> M;
for(int j = 0; j < N; j++){
int cat,naz;
cin >> naz >> cat;
tipo[cat][naz] = true;
}
for(int i = 1; i <= M; i++){
int p;
cin >> p;
adj[i].push_back(p);
adj[p].push_back(i);
}
cout << "Case #" << i << ": " << solve() << '\n';
}
return 0;
}
I problemi verrano caricati su cms?