Problema Slalom Nazionali 2006

sudden · 26 Luglio 2016, 11:27am

Salve a tutti,
Sto cercando di risolvere questo problema…senza troppo successo,temo proprio di aver bisogno del vostro aiuto!
La soluzione da me proposta è così strutturata:

ho costruito questa struct

struct st{vector gr;
int c,f;
bool t;
bool s;
st():t(false),s(false),gr(),c(1000000000),f(0){}
};

il vector gr serve a costruire il grafo,l’intero c a memorizzare il costo,l’intero f a memorizzare il padre di ciascun nodo. Bool t indica se è presente una telecamera o meno.

Ho costruito un vettore del tipo di questa struct. Successivamente ho dichiarato 4 vector: 2 servivano per fare visite in ampiezza, uno per memorizzare temporaneamente le foglie di un sottoalbero, uno per la soluzione finale.

Durante la prima visita, scendo dal nodo uno ed ogni volta che trovo una foglia, confronto la somma dei costi delle foglie coi costi del nodo padre. Salvo il padre o le foglie nella soluzione, salvo il nonno nell’altro vector per la visita in ampiezza e vado avanti.

Nella seconda visita,risalgo dai nonni. Controllo se almeno uno tra i figli e i padri di questi nonni contiene una telecamera,altrimenti la metto dove il costo è minimo. Poi metto il padre del nonno in coda al vector se non lo avevo già inserito e se il nonno non è il nodo 1.

Il caso d’esempio è corretto e rispetta la soluzione prevista su carta.

questo è il codice delle 2 visite. I vector si chiamano pila e coda, ma solo per aver 2 nomi diversi

1° visita:

   while(!pila.empty())
   {temp=pila[0];
    pila.erase(pila.begin());
    te=0;

    for(i=0;i<V[temp].gr.size();i++)
    {if(V[temp].gr[i]!=V[temp].f)
     {V[V[temp].gr[i]].f=temp;
      pila.push_back(V[temp].gr[i]);
      if(V[V[temp].gr[i]].gr.size()==1)
      {tem.push_back(V[temp].gr[i]);
       te=te+V[V[temp].gr[i]].c;
      }
     }
    }
    if(te!=0)
    {if(te<V[temp].c)
     while(!tem.empty())
     {sol.push_back(tem.front());
      V[tem.front()].t=true;
      tem.erase(tem.begin());
     }
     else 
     {sol.push_back(temp);
      V[temp].t=true;
      tem.clear();
     }
     if(temp!=1)
     {coda.push_back(V[temp].f);
      V[V[temp].f].s=true;
     }
    }
   }

2° visita:

while(!coda.empty())
{temp=coda.front();
coda.erase(coda.begin());
min=temp;
te=V[temp].c;
 for(i=0;i<V[temp].gr.size();i++)
 {if(V[V[temp].gr[i]].t==true)
  {ko=true;
   break;
  }
 if(V[V[temp].gr[i]].c<te)
 {te=V[V[temp].gr[i]].c;
 min=V[temp].gr[i];
 }
}
if(ko==false)
{sol.push_back(min);
V[min].t=true;
}
if(V[V[temp].f].s!=true&&temp!=1)
{coda.push_back(V[temp].f);
V[V[temp].f].s=true;
}
}

Grazie in anticipo!

wil93 · 28 Luglio 2016, 4:26pm

Ciao, non sono sicuro di capire esattamente la strategia che hai usato… inoltre il codice che hai postato utilizza vector senza specificare il tipo (come si farebbe ad esempio con vector<int>) quindi non è chiaro come interpretarlo…

In particolare, nel punto in cui dici:

stai dicendo che fai due visite (come mai?) e inoltre dici che quando trovi una foglia calcoli la somma dei costi delle foglie (quali?).

Se riesci a spiegarci meglio l’idea della soluzione (meno codice si usa per spiegare e meglio è ) possiamo provare ad aiutarti

sudden · 1 Agosto 2016, 9:49am

Ciao wil93,

nel codice della struct ho commesso un errore di trascrizione, si tratta di un vector gr. Anche tutti gli altri vector citati sono di tipo int.

Mi dispiace non essere riuscito ad essere abbastanza chiaro,ci riprovo… per quanto riguarda i costi delle foglie, mi riferisco alla somma dei costi che comporterebbe mettere una telecamera in ciascuno degli snodi privi di nodi “figli” collegati allo snodo che sto al momento visitando. Se mi costa di meno mettere una telecamera per ogni foglia che metterne una sola sul padre, ne metto una su ogni foglia, altrmenti la metto sul padre.

L’idea è che ci sono solo 2 modi di coprire televisivamente le foglie del grafo, mettendoci una telecamera o mettendola sul padre. Durante la prima visita mi occupo solo di queste foglie, cercando di risolvere il problema con costo minimo. Chiaramente, se metto una telecamera sul padre anche il nonno è coperto, mentre se la metto solo sulle foglie il nonno potrebbe essere scoperto, e di questo mi occupo nella seconda visita.

Prendendo il caso d’esempio:

il nodo 1, da cui parte la prima visita, è collegato al nodo 2; questo è collegato ai nodi 3 e 4, ed infine quest’ultimo è collegato al nodo 5.

Il nodo 1 ha un unico figlio, 2, che non è una foglia, quindi vado avanti visitando i figli di 2 senza particolari modifiche.

Tra i figli di 2, 3 è una foglia mentre il nodo 4 no. Il costo di mettere una telecamera in 3 è 1, mentre per il nodo 2 sarebbe 2, come da input d’esempio, quindi metto una telecamera in 3, tengo in memoria che il nodo 3 ha una telecamera e aggiungo il nodo 1 in coda (vector seconda visita) in quanto nonno della foglia 3.

Scendendo dal nodo 4, il nodo 5 è l’ultimo da visitare. E’ una foglia ed ha lo stesso costo del nodo 4, per come ho impostato il codice in questo caso metto una telecamera nel nodo “padre” 4. Salvo il nonno della foglia 5 nella coda per la seconda visita,cioè il nodo 2.

La prima visita finisce ed inizia la seconda:

Il primo nodo presente nella coda è il nodo 1. Nel suo unico figlio, il nodo 2, non è stata inserita una telecamera. Il costo di mettere una telecamera nel nodo 1 è minore di quello del nodo 2, quindi metto una telecamera nel nodo 1. Il nodo 1 chiaramente non ha padre, quindi non metto suo padre in coda.

E’ la volta del nodo 2, ultimo elemento rimasto nella coda. Sia in suo padre 1 che in suo figlio 3 c’è una telecamera, quindi non devo aggiungere nessuna telecamera, ma sarebbe bastato anche solo che il padre o uno tra i figli contenesse una telecamera. Lo elimino dalla coda e di norma andrei avanti a sfogliare gli elementi presenti in questo vector, ma essendo l’ultimo la visita finisce.
Nel vector della soluzione sono presenti i numeri 3, 4, 1, una delle possibili soluzioni.

Forse mi sono dilungato un po’, ho cercato questa volta di fare del mio meglio per essere chiaro. Ovviamente si tratta di una soluzione che ha preso 0 punti, quindi sicuramente ci saranno delle operazioni insensate non proprio facili da interpretare. Ho notato anche che hai modificato il mio testo iniziale, mettendo parte del codice in un riquadro separato. Questo è il mio primo post e non ho idea di come si faccia, l’altra parte del codice era in un riquadro per puro caso.

Ringrazio te e chi altro proverà a darmi una mano per la pazienza

dp_1 · 1 Agosto 2016, 10:35am

Scusate se mi intrometto, ma non si tratta di un problema di colorazione di un albero?
Nel problema specifica che non sono presenti cicli, quindi (se non sbaglio) il grafo in input è un albero. Basterebbe poi colorare il grafo con due colori (telecamera presente/non presente) a partire da un nodo radice, che credo possa essere preso a piacimento, provare entrambe le possibili colorazioni (con il nodo radice di un colore o dell’altro) e prendere quella di costo minimo,
Essendo un albero e avendo due colori, la colorazione, dato il nodo radice e il suo colore, dovrebbe essere semplice da fare, ogni nodo ha colore opposto di quello del padre.

Dario

sudden · 1 Agosto 2016, 11:13am

Perché dovresti scusarti? Ogni intervento è d’aiuto, per le prove nazionali dei primi anni duemila non ho trovato booklet con soluzioni ufficiali.

Comunque, se ho capito bene, la soluzione che proponi non è poi così diversa dalla mia. Anche io tengo in memoria se una telecamera è presente oppure no e mi regolo di conseguenza, penso che scegliere il caso di costo minimo ogni volta che si arriva alle foglie debba portare a un costo minimo globale, poi magari mi sbaglio.
Il grafo non è ciclico, si tratta proprio di un albero. Io ho radicato dal nodo 1 ma si può scegliere a piacimento.

Non avevo mai sentito parlare di “colorazione”, perdonami, questo è il mio secondo anno alle olimpiadi ma il primo in cui riesco a raggiungere le fasi nazionali, ho seguito una preparazione piuttosto autonoma basata soprattutto sulla risoluzione delle tracce presenti nella piattaforma di allenamento e solo da pochissimo faccio qualche tentativo con i problemi delle nazionali…spesso mi viene difficile capire appieno le soluzioni ufficiali nei booklet. Se ho frainteso ciò che intendevi con colorazione ti prego di scusarmi

dp_1 · 1 Agosto 2016, 11:33am

Mi scusavo perchè magari dava fastidio introdurre una soluzione diversa in un thread che parla della tua.

Comunque, visto che non sembra essere il caso:
Da quello che ho capito della tua soluzione, è valida solo fino a tre livelli di nodi (nonno, padre e foglia), mentre se ce ne sono di più (il problema non li limita, potrebbero anche esserci tutti e 400000 i nodi uno dopo l’altro a formare 400000 livelli) non ho capito bene cosa fa.

La tua soluzione è di tipo greedy, prende i minimi locali invece che il minimo globale, e in questo problema questo approccio può dare risultati sbagliati, ad esempio con questo grafo (i numeri indicano il costo per mettere una telecamera in ogni nodo):
5--7--8--2--3--1
Se scegliessi di mettere una telecamera nel primo nodo, soluzione ottima per il primo segmento, saresti poi obbligato a prendere il nodo con costo 8 per coprire il secondo segmento, e poi il nodo con costo 3, per un costo totale di 16.
Se invece considerassi anche la seconda possibilità, cioè quella di prendere il nodo con costo 7, allora potresti prendere i nodi 2 e 1, per un costo totale di 10.

Dario

sudden · 1 Agosto 2016, 11:53am

Nel grafo di esempio, radicando dal nodo 1, il nodo 1 è bisnonno del nodo 5, quindi sono già 4 livelli…
Ad ogni modo, su più livelli durante la risalita della seconda visita i bisnonni vengono messi in coda se si verificano particolari condizioni, non sono esclusi a priori.

Nel caso da te proposto,dovrebbero essere presi i nodi 3,5 nella prima visita ed 1 nella seconda. 3 è foglia di 2,con costo 2 mentre 3 ha costo 8,quindi prendo il nodo 3 e metto in coda il nonno(coda è il vector della seconda visita).Poi il nodo 5 ha costo 1 ed è foglia di 4 che ha costo 3,quindi prendo 5 ed incodo 2.Ora non mi ricordo se venga valutato prima il nodo 1 o 2 nella seconda visita,ma è uguale,perché al 2 è collegata la telecamera del nodo 3 e non viene preso considerazione,mentre i figli di 1 non hanno telecamere e il padre non lo ha.
Appena posso testo il codice su questo caso

OK ho notato che i nodi 1-2-5, con costo totale 10, in questo caso non sarebbero il costo minimo, perché mettendo una telecamera su 2,con costo 8,e una su 5,con costo 1,il costo totale è 9.(Sto considerando il primo numero che mi hai dato,5,come il numero di nodi,perché si parlava di un grafo con 5 nodi). Questo decisamente mi mette in crisi…certo, se avessi radicato dal nodo 2 sarebbe venuta fuori la soluzione corretta, potrei pensare di radicare dal nodo con più collegamenti, ma non credo che sarebbe una soluzione ottima anche in questo caso.
Ripeto che per il codice che avevo postato se un nodo non ha foglie tra i suoi figli, durante la prima visita si va avanti, forse non ero stato chiaro in questo… il nodo uno non ha foglie tra i suoi figli.

Terza interpretazione tardiva all’esempio da te proposto:
mi sono reso conto che potevi anche intendere un grafo a forma di segmento, non è esattamente l’immagine che uso più frequentemente quando schematizzo i grafi e non l’ho notato immediatamente.

In questo caso, ancora una volta,dipende da dove parte la visita; il nodo con costo 2 e il nodo con costo 8 sono ugualmente centrali, ma se facessi partire la prima visita da 2 la soluzione sarebbe ottima; viene preso il nodo di costo 1, incodato il nodo di c. 2, viene preso il nodo di costo 5, incodato il nodo c. 8, il nodo di costo 2 viene messo nella soluzione e l’algoritmo termina con costo totale 8 (e non 10!) mentre se faccio partire dal n. c. 8, questo alla fine finirebbe nella soluzione al posto del nodo 2…per un risultato finale di 14.

Mi viene in mente che potrei far partire le visite descritte inizialmente per ciascun nodo che non sia una foglia, o per un insieme di altri nodi con caratteristiche particolari, ma sono soluzioni che neanche mi metterei ad implementare per via del tempo che impiegherebbero a trovare i nodi con caratteristiche particolari e a ripetere le visite tante volte.

Sono più interessato a capire meglio la soluzione da te proposta, se mi dicessi che l’hai già testata su piattaforma sarei ancora più interessato. Per quello che ho capito mi verrebbe di provare con una ricorsiva, mettere il costo finale in un vettore per ogni caso e fare una ricerca del minimo alla fine, ma vanno anche restituiti i nodi da visitare per ottenere il costo minimo, e questo non mi sembra facilissimo da gestire in termini di memoria… forse un vector struct che contenga un intero e un vector nella struct, non saprei.

MrBrionix · 2 Agosto 2016, 4:29pm

Non sempre il costo minimo si ottiene con il padre di colore diverso dal figlio, per esempio considera un grafo con 4 nodi dove c’è una pista tra il nodo 1 e il nodo 2, una pista tra il nodo 2 e il nodo 3 e una pista dal nodo 3 al nodo 4 e con i costi seguenti: nodo 1=10 nodo 2=1 nodo 3=1 nodo 4=10.
Il costo minimo è due e si ottiene colorando 2 e 3 di uno stesso colore anche se uno è il padre dell’altro.
Per quanto riguarda la soluzione, questo problema è in tutto e per tutto uguale al Maximum Weight Indipendent Set( ovvero trovare quell’insieme di nodi in modo tale che per ogni coppia di nodi collegati uno ed uno solo appartiene a quell’insieme e che la somma del peso dei nodi di quell’insieme sia massima) applicato a un albero solo che al posto di trovare quello con il costo massimo bisogna trovare quello con il costo minimo e al posto di avere per ogni pista uno e un solo nodo ne dobbiamo avere almeno uno. La tecnica applicata per la risoluzione di questo problema è quella della programmazione dinamica. Ecco un link che spiega come trovare il maximum indipendent set su un albero: Qua. Per adattarlo al nostro problema bisogna mantenere l’idea base cercando il minimo al posto del massimo cambiando i valori da considerare per ogni nodo. Ho preferito mettere il link piuttosto che scriverlo poiché avrei impiegato molto ma molto tempo (e tra poco iniziava l’HourRank11 ), comunque non esitare a chiedere spiegazioni o dubbi. Magari tra un giorno o due quando ho un’oretta o due libere scrivo il codice e posto

sudden · 3 Agosto 2016, 1:59pm

Grazie mille Brionix.
Pare proprio che la teoria da studiare sui grafi non finisca mai,eh?
L’altro giorno spulciavo le altre richieste d’aiuto sul forum, ho notato che una volta sì o una no i più esperti rispondevano linkando pagine con algoritmi vari (vertex cover, dominating set, range tree, segment tree), tutti rigorosamente spiegati in inglese e tutti da imparare prima di settembre… e io che credevo di essere apposto con l’algoritmo di dijkstra!
Però merito un premio per l’impegno dai, senza sapere la teoria ho comunque capito alcune delle difficoltà principali del problema (ma magari!) e ho proposto una soluzione macchinosa, piena di errori, ma di certo la più originale. Gli algoritmi corretti, in fondo, sono tutti uguali

Scherzi a parte, guardo spesso la sezione statistiche della piattaforma di allenamento, quando vedo quelle dieci soluzioni migliorate al limite del centesimo di secondo rimango sempre affascinato… a Catania magari arriverò ultimo, ma mi consola sapere che almeno potrò parlare con alcuni di questi talenti!

Ringrazio tutti ancora una volta per la pazienza, e provo a vedere cosa riesco a capire dal link che ha postato brionix… il tempo per prepararsi è tristemente agli sgoccioli

dp_1 · 3 Agosto 2016, 6:28pm

“Non sempre il costo minimo si ottiene con il padre di colore diverso dal figlio”

Già. Era proprio per questo problema che non ho risposto subito, cercavo un asoluzione migliore. Rileggendo il testo, non serve che ogni tratta sia coperta da una sola telecamera, ma da almeno una telecamera.

MrBrionix · 5 Agosto 2016, 8:00am

Ora, dato che sono riuscito a risolverlo personalmente, ora posto una spiegazione più chiara rispetto a un semplice link in inglese

Registro i costi dei nodi in un vector costo e l’albero nel vector<vector< long long> > grafo
Inizio a fare una prima visita partendo dal nodo 1, durante la quale assegno a ogni nodo il suo/ i suoi figli e la sua distanza rispetto al nodo 1.
faccio un esempio dato che non sono molto bravo a spiegare:

In questo caso 2 e 3 hanno distanza pari a 1 dal nodo 1, mentre 4 e 5 hanno distanza 2. (se il nodo 3 avesse avuto figli la loro distanza sarebbe stata 2, se il nodo 4 o 5 avesserero avuto figli la loro distanza sarebbe stata 3).
Nel mio codice (che scriverò in fondo) registro i figli di ogni nodo nel vector<vector > grafo2, mentre la loro distanza dal nodo 1 la registro nel vector valore(in modo tale che valore[i] sia il valore del nodo i) e nel vector<vector > lista(in modo che lista[i] sia un vector contenente tutti i nodi che hanno distanza i dal nodo 1). Per fare questa operazione uso una funzione ricorsiva che ho chiamato esplora(ha come parametri long long k che sarebbe il nodo che sto controllando e long long padre che è il nodo da cui sono arrivati e quindi che non devo includere nei figli).
Dopodichè parto a controlla il vector<vector > lista (quelo con le distanze dei nodi) partendo dai nodi più lontani e qua parte il pezzo di programmazione di dinamica (quella nel link), perchè dichiaro un long long dp[numero di telecamere][2] dove:
-dp[i][0] sta a significare il costo minimo per coprire di telecamere l’albero a partire dal nodo i in giù senza mettere una telecamera nel nodo i;
-dp[i][1] sta a significare il costo minimo per coprire di telecamere l’albero a partire dal nodo i in giù mettendo una telecamera nel nodo i;
Quindi se il nodo non ha figli dp[i][0]=0 e dp[i][1]=costo di quel nodo, mentre se li ha dp[i][0]=dp[i_0][1]+dp[i_1][1]+…+ dp[i_k][1]; dove i_0,i_1…i_k sono i suoi k figli e dp[i][1]=min(dp[i_0][1],dp[i_0][0])+min(dp[i_1][1],dp[i_1][0])+…+min(dp[i_k][1],dp[i_k][0]); dove i_0,i_1…i_k sono i suoi k figli (ho segnato questa parte con dei commenti nel programma per riuscire a individuarla)

Una volta assegnati tutti i valori di dp[][], faccio un seconda visita partendo dal nodo 1 attraverso la funzione esplora2 che ha come parametri long long ke long long mod dove:
-k è il nodo da analizzare;

-mod (qua arriva la parte difficile da spiegare) sta a significare in che modo sono arrivato a quel nodo:
se mod=0–>non ho vincoli, quindi confronto se cosa conviene tra dp[nodo][0] e dp[nodo][1] e se è meglio dp[nodo][1] aggiungo il nodo alla soluzione(vector sol) e chiamo la funzione esplora2 per ogni figlio con mod=0, altrimenti se è meglio (o uguale) dp[nodo][0] non aggiungo il nodo alla soluzione ma chiamo esplora2 per ogni figlio con mod=1;
se mod=1–>devo per forza prendere quel nodo per suo padre non è stato preso e ho la sicurezza che se non lo prendevo avrei avuto la situazione migliore, quindi aggiungo quel nodo a sol e per ogni suo figlio chiamo esplora2 con valore 0;

Una volta finita questa visita la soluzione al problema è nel vector sol, che stampo dopo aver scritto il numero dei suoi elementi (sol.size())

Il mio codice impiega 1,341 secondi e 67,4 Mib nel caso peggiore, non da top ten (e non saprei cosa fare per diminuire il tempo di esecuzione) ma funziona egregiamente, eccolo:

#include<fstream>
#include<vector>
using namespace std;
ofstream cout("output.txt");
ifstream cin("input.txt");
long long num,temp,temp1;
vector<long long> costo(400001),valore(400001);
vector<vector<long long> > grafo(400001),grafo2(400001),lista(400001);
long long dp[400001][2];
vector<long long> sol;
void esplora(long long k,long long padre){
	//cout<<"controllo "<<k<<endl;
	for(long long i=0;i<grafo[k].size();i++){
		if(grafo[k][i]!=padre){
		valore[grafo[k][i]]=valore[k]+1;//distanza dal nodo 1
		lista[valore[grafo[k][i]]].push_back(grafo[k][i]);//distanza dal nodo 1
		grafo2[k].push_back(grafo[k][i]);//assegno il figlio
		esplora(grafo[k][i],k);
		}
	}
}

void esplora2(long long k,int mod){
	if(mod==0){
		if(dp[k][0]>dp[k][1]){
			sol.push_back(k);
			for(long long i=0;i<grafo2[k].size();i++){
				esplora2(grafo2[k][i],0);
			}
		}
		else{
			for(long long i=0;i<grafo2[k].size();i++){
				esplora2(grafo2[k][i],1);
			}
		}
	}
	else{
	sol.push_back(k);
	for(long long i=0;i<grafo2[k].size();i++){
				esplora2(grafo2[k][i],0);
			}
	}	
}

int main(){
cin>>num;
for(long long i=1;i<=num;i++){
	cin>>costo[i];
}
for(long long i=0;i<num-1;i++){
	cin>>temp>>temp1;
	grafo[temp].push_back(temp1);//creo il grafo
	grafo[temp1].push_back(temp);
	}
	
//assegno ad ogni nodo il suo figlio e la sua distanza dal nodo 1
valore[1]=1;
lista[1].push_back(1);
esplora(1,0);
//-------


//inizio dp
long long val=0,val2=0;
for(long long i=400000;i>0;i--){
	for(long long j=0;j<lista[i].size();j++){
		for(long long z=0;z<grafo2[lista[i][j]].size();z++){
			val+=min(dp[grafo2[lista[i][j]][z]][0],dp[grafo2[lista[i][j]][z]][1]);// dp[i][1]=min(dp[i_0][1],dp[i_0][0])+min(dp[i_1][1],dp[i_1][0])+...+min(dp[i_k][1],dp[i_k][0]); dove i_0,i_1...i_k sono i suoi k figli
			val2+=dp[grafo2[lista[i][j]][z]][1];//dp[i][0]=dp[i_0][1]+dp[i_1][1]+...+ dp[i_k][1]; dove i_0,i_1...i_k sono i suoi k figli
		}
		dp[lista[i][j]][0]=val2;
		dp[lista[i][j]][1]=val+costo[lista[i][j]];
		val=0;
		val2=0;
	}
}
//fine dp

//seconda visita
esplora2(1,0);



//stampo la soluzione
cout<<sol.size()<<endl;
for(long long i=0;i<sol.size();i++)
cout<<sol[i]<<" ";
cout<<endl;

return 0;
}

p.s. approfitto per chiedere una cosa: ma è normale che io trovi i problemi delle nazionali per esempio 2011,2012(sono quelli più recenti che ho provati a risolverli, quelli dal 2013 in poi li proverò più avanti dopo essermi allenato a sufficienza) molto più facili di, per esempio, quelli del 2007 (di cui fatico a risolverne anche solo uno)?

sudden · 5 Agosto 2016, 9:20am

mmm sembra decisamente più chiaro, poi il codice me lo testo su carta con calma e dovrei essere a posto, grazie mille
Fammi capire bene… tu sarai a catania con me questo settembre? pensavo di avere a che fare con un veterano che aveva già seguito l’anno di preparazione per le IOI, molto bene,sono spacciato

Quanto alla tua teoria sulla difficoltà decrescente di anno in anno…secondo me non è vero. Nella prova regionale di quest’anno tra le tre tracce c’era il problema discesa, che era uguale ad un problema delle ioi di un’ annata precedente al 2000. A quanto ho capito l’Italia non partecipava nemmeno… sarà che noi abbiamo alzato il livello

Io mi aspetto un grafo ciclico, un range tree e un problema simile a taglialegna quest’anno, nessuno sconto quanto a difficoltà per noi rispetto agli anni precedenti. Che poi la soluzione di taglialegna mi ha confuso con tutti quei vettori per la dinamica, ancora devo capirla ahaha