# Tournament Planning(Poker)

**URL:** <https://forum.olinfo.it/t/tournament-planning-poker/5422>\
**Category:** Aiuto\
**Created:** [20 Novembre 2018, 12:03am UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422 "2018-11-20T00:03:26Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![LorenzoM](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/e495f1/32.png) [@LorenzoM](https://forum.olinfo.it/u/LorenzoM)\
**Post date:** [20 Novembre 2018, 12:03am UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/1 "2018-11-20T00:03:26Z")

</div>

Ottengo 10/100…  
Le subtask falliscono principalmente per output non corretti e, in parte, anche per execution timed out

```
#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;

    ifstream leggi("input.txt");ofstream scrivi("output.txt");
    int N,M;
    int Dtemp,temp;
    vector<int>D;
    int u,v;
    
    struct poker{
    	int S,E,B,P;
	};
	
	bool sortByEnd(const poker &a,const poker &b)
	{
		return(a.E<b.E);
	}
	
	int maxVal(const int &a, const int &b)
	{
		return (a>b?a:b);
	}
	
	int max_win(poker match[],int u,int v){
		sort(match+u,match+v+1,sortByEnd);
		int lim=v-u+2;//indica la dimensione delle righe della matrice, corrisponde al numero di match 
		int m[match[v].E+1][lim];
		for(int i=0;i<=match[v].E;i++)
		{
			m[i][0]=0;
			
// cout<<i<<") "<<m[i][0]<<" ";
			for(int k=1;k<lim;k++){//una colonna sarà sempre inizializzata a 0
				
				if((match[u+k].E<=i)&&(M+m[match[u+k].S][k-1]>=match[u+k].B))
				{
					m[i][k]=maxVal(m[i][k-1],m[match[u+k].S][k-1]+(match[u+k].P-match[u+k].B));
				}else{
					m[i][k]=m[i][k-1];
				}
// cout<<m[i][k]<<" ";
			}
// cout<<"\n";
		}
		return m[match[v].E][lim-1];
	}
int main(){
    leggi>>N>>M;
	poker match[N];
    Dtemp=-1;
    poker *x;
    for(int i=0;i<N;i++)
    {
    	x=&match[i];
        leggi>>temp;
        leggi>>x->S>>x->E>>x->B>>x->P;
        if(Dtemp==temp){
            D.back()++;
        }else
        {
		    Dtemp=temp;
	        D.push_back(1);
        }      
    }
    u=0;v=-1;
    for(int i=0;i<D.size();i++)
	{
		u=v+1;
		v=u+D.at(i)-1;
    	if(D.at(i)==1){
    		if(M>=match[u].B)
    			M+=(match[u].P-match[u].B);
		}else{
			M+=max_win(match,u,v);
		}

	}
	scrivi<<M;
       
    
}
```

---

<div class="post-metadata">

**Author:** ![LorenzoM](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/e495f1/32.png) [@LorenzoM](https://forum.olinfo.it/u/LorenzoM)\
**Post date:** [23 Novembre 2018, 11:49am UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/2 "2018-11-23T11:49:45Z")

</div>

Che approccio mi consigliate di utilizzare per risolvere il problema Tournament Planning?  
link: [https://training.olinfo.it/#/task/ois\_poker/statement](https://training.olinfo.it/#/task/ois_poker/statement)  
Ho provato a risolverlo con la bottom up ma ottengo solo 10/100…  
Qui ho postato il mio codice: [Tournament Planning(Poker)](https://forum.olinfo.it/t/tournament-planning-poker/5422/2)

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [23 Novembre 2018, 12:28pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/3 "2018-11-23T12:28:16Z")

</div>

L’ approccio da usare è la programmazione dinamica.  
Prova a spiegare l’ idea che hai in mente e quello che fa il codice.  
Leggendolo non si capisce che fa 😅

---

<div class="post-metadata">

**Author:** ![LorenzoM](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/e495f1/32.png) [@LorenzoM](https://forum.olinfo.it/u/LorenzoM)\
**Post date:** [24 Novembre 2018, 5:13pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/4 "2018-11-24T17:13:03Z")

</div>

Mi consiglieresti di utilizzare la top down o la bottom up?  
In pratica cerco di utilizzare la bottom up, almeno credo 😅 .  
Le variabili u e v rappresentano la posizione nel vettore “match” della prima e dell’ultima partita partita svolta nello stesso giorno.  
Ogni volta che in un giorno ci sono più di una partita la funzione “max\_win” verrà chiamata.  
All’interno della funzione la prima cosa che faccio è ordinare la parte del vettore “match” corrispondente alle partite del giorno in questione basandosi sulla fine di ogni match(in ordine crescente).  
Successivamente creo una matrice di match[v].E+1 righe, cioè in questo modo ci saranno 0,1,2… m[v].E righe(m[v].E sarebbe la partita con l’orario di fine più grande) in modo tale da poter andare a risolvere i casi in ogni limite di tempo.Mentre l’ascissa è compost dal numero di partite+1(così per ogni riga della tabella il primo valore sarà 0).  
Per ogni cella della nostra tabella andrò a vedere se “giocare o non giocare la partita in questione”, nel caso in cui io decida di giocarla devo tener conto di due cose:

1. (match[u+k].E\<=i) = cioè se il match in questione finisce prima del limite di tempo i.
2. (M+m[match[u+k].S][k-1]\>=match[u+k].B) se il badget è sufficiente per giocare la partita.

Se entrambe le condizioni sono vere faccio una somma tra il guadagno di questa partita e il guadagno che potrei ottenere dall’inizio della giornata fino all’inizio della partita a cui facciamo riferimento, la somma fatta la confronto con il valore della cella alla mia sinistra(che corrisponde al caso in cui decido di non giocare la partita) e prendo il valore più grande.  
Se le condizioni risultano false copio il valore della cella precedente m[i][k]=m[i][k-1].  
E così “dovrei” ottenere il risultato migliore della giornata che poi, sommato con i risultati delle altre giornate e con il budget iniziale, mi dovrebbe dare il risultato finale.  
Mi scuso ma purtroppo non sono molto bravo a spiegare…

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [24 Novembre 2018, 8:01pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/5 "2018-11-24T20:01:39Z")

</div>

> [@LorenzoM](#):
>
> Mi consiglieresti di utilizzare la top down o la bottom up?

In bottom up è più semplice a parer mio.

> [@LorenzoM](#):
>
> Mentre l’ascissa è compost dal numero di partite+1(così per ogni riga della tabella il primo valore sarà 0).

Considerando il caso peggiore in cui ci sono _100 000_ parite in un giorno e crei una matrice _100 000 x 1 000_ hai bisogno di _100 000 000_ interi che trasfromati in megabyte sono circa 400.  
Quindi anche se il tuo ragionamento è giusto non prenderebbe mai il 100/100 per i limiti di memoria.  
Hai bisogno di rivedere la strategia risolutiva, ordinare e dividere la dp su più giorni è già un buon inizio.  
Inizia col non complicarti la vita leggendo gli input cosi, puoi salvare benissimo i valori in un vettore e quando il giorno non coincide con il precedente fai partire la dp.  
Ordinando per fine (come hai fatto) ti permette di creare l’ ordine con cui potresti giocare le varie partite, quindi considerando una partita in posizione _i_ essa può essere giocata se il budget di inizio giorno te lo permette oppure esitono delle partite _j con j \< i_ precedenti da cui potresti ricavarti la somma da poter usare nella _i-esima_ partita.  
Il budget per il giorno successivo è dato dal massimo che puoi ricavare per ogni partita e il budget iniziale di giornata.  
Prova a scrivere una soluzione O(N^2) dove per ogni posizione _i_ provi a combinarla con le precedenti.  
Se tutto va bene dovresti riuscire a ottenre 85/100.  
Immagino che a questo punto hai intuito che struttura usare per conservare i risultati per ogni partita.  
Per il 100 su 100 ci sono due ottimizzazioni che si potrebbero fare ma l’ importante ora è arrivare ad avere output corretti.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 12:07am UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/6 "2018-11-26T00:07:29Z")

</div>

Molte **grazie** per il suggerimento, ero fermo da un pezzetto a 85/100 ma utilizzando le tue considerazioni sono arrivato in fondo. Tutto considerato era imparentato con la “Dieta di Poldo”.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 11:06am UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/7 "2018-11-26T11:06:38Z")

</div>

A quale complessità sei arrivato?

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 12:55pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/8 "2018-11-26T12:55:47Z")

</div>

Non ho molta esperienza con questi conti ma direi O(nlogn).  
Per memorizzare il massimo che posso fare per ogni torneo e recuperare il massimo guadagno utilizzabile che precede il torneo i uso un segment tree.  
Inoltre Il vettore dei tornei di una giornata viene ordinato prima della scansione.  
n è il numero di tornei di una giornata.  
Il tutto ripetuto per tutte le giornate.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 1:03pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/9 "2018-11-26T13:03:57Z")

</div>

In realtà si può migliorare.  
La complessità minima è data dall’ordinamento del quale non si può fare a meno, ma se invece di ordinare tutto il vettore iniziale lo si divide in giorni si possono fare N/giorni ordinamenti e la complessità è inferiore rispetto ad un unico ordinamento.  
Successivamente si può notare come ordinando i tornei in base alla loro fine possiamo fare in modo di calcolare il miglior budget per ogni singolo attimo solamente una volta.  
Senza ricorrere a segment o fenwick che aggiungono un fattore logaritmico.

Fabio.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 1:38pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/10 "2018-11-26T13:38:43Z")

</div>

> [@frakkiobello](#):
>
> La complessità minima è data dall’ordinamento del quale non si può fare a meno, ma se invece di ordinare tutto il vettore iniziale lo si divide in giorni si possono fare N/giorni ordinamenti e la complessità è inferiore rispetto ad un unico ordinamento.

Questo è ciò che faccio già e anch’io ordino per fine.

> [@v.bizzarri](#):
>
> Inoltre Il vettore dei tornei di una **giornata** viene ordinato prima della scansione.  
> **n è il numero di tornei di una giornata.**  
> Il tutto ripetuto per tutte le giornate.

> [@frakkiobello](#):
>
> Successivamente si può notare come ordinando i tornei in base alla loro fine possiamo fare in modo di calcolare il miglior budget per ogni singolo attimo solamente una volta.

Al momento non vedo chiaramente come ottenere questo senza un segment tree ma ci penserò su.  
Comunque grazie per l’idea.

Vittorio.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 1:45pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/11 "2018-11-26T13:45:12Z")

</div>

Pensala così, ogni torneo, stando a ciò che fai tu, aggiorna un suffisso dei possibili momenti, quindi , per esempio l’ultima cella del vettore viene aggiornata N volte, anche se ciò potrebbe essere fatto un’unica volta.

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [26 Novembre 2018, 1:52pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/12 "2018-11-26T13:52:43Z")

</div>

> [@v.bizzarri](#):
>
> Tutto considerato era imparentato con la “Dieta di Poldo”.

Io direi che è più un [piano degli studi](https://training.olinfo.it/#/task/pianostudi/statement) in versione semplificata.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 3:08pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/13 "2018-11-26T15:08:07Z")

</div>

> [@frakkiobello](#):
>
> Pensala così, ogni torneo, stando a ciò che fai tu, aggiorna un suffisso dei possibili momenti, quindi , per esempio l’ultima cella del vettore viene aggiornata N volte, anche se ciò potrebbe essere fatto un’unica volta.

Non mi pare che il mio algoritmo funzioni così, come dicevo lavora stile “La dieta di Poldo” e non è ricorsivo.  
Nell’ambito dei tornei di una giornata (ordinati crescenti per orario di fine torneo):  
vado dal primo fino all’ultimo  
ad ogni torneo mi guardo indietro per capire se posso farlo e se si quanto al massimo mi trovo in saccoccia dopo aver vinto quel torneo, facendo attenzione a quei tornei che terminano tutti allo stesso istante e memorizzando il totale delle vincite fin li +la posta di partenza.  
Il valore memorizzato ad un certo istante viene elaborato tante volte per quanti sono i tornei che terminano in quell’istante e così anche per il valore superiore dell’ultima cella.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 3:15pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/14 "2018-11-26T15:15:14Z")

</div>

Ad intuito penso che usi il segment tree per controllare quale sia il maggior numero di soldi con il quale puoi iniziare ogni torneo.  
Se è come penso:

1. Se usi un fenwick dovrebbe essere leggermente più veloce.

2. In questo modo per ogni torneo controlli quanto è il massimo prima del suo inizio avendo poi una complessità log(1000). Modificando leggermente l’algoritmo puoi conoscere quel valore in O(1), ma ovviamente devi cambiare l’aggiornamento che non sarà più O(1) ma O(1000) per ogni giornata:  
Quindi per ogni singolo giorno, dove hai K tornei, invece di di avere O(Klog(1000) +K) puoi avere O(2K).

Se non è come penso allora rispiega please.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 4:03pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/15 "2018-11-26T16:03:42Z")

</div>

> [@frakkiobello](#):
>
> Ad intuito penso che usi il segment tree per controllare quale sia il maggior numero di soldi con il quale puoi iniziare ogni torneo.  
> Se è come penso:

Si l’algoritmo lavora così.  
Il suggerimento N1 mi è chiaro e ci posso provare quasi subito  
Sul secondo devo meditare, tra l’altro con il calcolo della complessità ho problemi.  
Un’ultima cosa:

> [@frakkiobello](#):
>
> ovviamente devi cambiare l’aggiornamento che non sarà più O(1)

Ma il mio aggiornamento è O(1)?

grazie per i suggerimenti

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 4:29pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/16 "2018-11-26T16:29:18Z")

</div>

Quali istruzioni esegui per aggiornare?

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 4:35pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/17 "2018-11-26T16:35:32Z")

</div>

My bad, point update nel segment ha ovviamente complessità O(logN). Sorry

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Novembre 2018, 4:39pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/18 "2018-11-26T16:39:07Z")

</div>

Un update del valore del segment tree relativamente alla fine di quel torneo.  
Supponendo che:

1. il torneo i termini al momento y
2. che potendolo fare mi trovi in tasca z
3. che questo z sia maggiore w cioè di quanto mi farebbe incassare un altro torneo già analizzato e che terminava sempre all’istante y (sempre che ce ne sia uno prima)  
allora vado a mettere z nel segment tree in posizione y.

Scusa ripensandoci non vedo cosa mettere dentro Fenwick a meno di ripensare il tutto.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Novembre 2018, 4:49pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/19 "2018-11-26T16:49:42Z")

</div>

Sapendo che ogni momento y appartiene a logN intervalli l’update è in O(logN).

---

<div class="post-metadata">

**Author:** ![LorenzoM](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/e495f1/32.png) [@LorenzoM](https://forum.olinfo.it/u/LorenzoM)\
**Post date:** [26 Novembre 2018, 6:09pm UTC](https://forum.olinfo.it/t/tournament-planning-poker/5422/20 "2018-11-26T18:09:15Z")

</div>

Grazie!!! Finalmente sono riuscito ad ottenere 100/100.  
Senza i tuoi “input” non credo sarei riuscito ad ottenere 100/100 😂😂

Vorrei sapere come poter vedere il tempo di esecuzione del mio programma sul portale, sai se possibile/come fare?

[Pagina seguente](https://forum.olinfo.it/t/tournament-planning-poker/5422.md?page=2)