Tournament Planning 85/100


#1

Ciao a tutti, vi chiedo una mano per il problema Tournament Planning. Con la mia soluzione ottengo 85/100 (fallisce solo l’ultimo Testcase).

Ho usato bottom-up dynamic programming, dove la tabella m[DAY][TIME] contiene il massimo denaro che si puo’ avere in un determinato giorno/istante. Scorro la tabella in avanti e aggiorno ogni entry con il massimo tra valore della cella precedente e valore della cella corrente. Per ogni cella che visito faccio una ricerca binaria tra i tornei (array di tuple ordinato per giorno, inizio, fine, buy-in, premio) e, se trovo un torneo a cui posso partecipare, aggiorno la tabella nell’istante corrispondente alla fine del torneo con la nuova somma di denaro ($ attuali - buy-in + premio). Cosi’ facendo, in m[999][999] dovrebbe esserci la massima somma ottenibile.

#include<bits/stdc++.h>

// constraints
#define MAXN 100010
#define MAXT 1010

typedef long long ll;

// input data
int N, M, i, j;
int D, S, E, B, P;
ll m[MAXT][MAXT];

std::tuple<ll, ll, ll, ll, ll> t[MAXN];

int main()
{
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d %d %d %d", &D, &S, &E, &B, &P);
		t[i] = std::make_tuple(D, S, E, B, P);
	}

	std::sort(t, t + N);
	m[0][0] = M;

	for (i = 0; i < MAXT; i++)
		for (j = 0; j < MAXT; j++)
		{
			if (!j)
			{
				if (i) m[i][j] = std::max(m[i - 1][MAXT - 1], m[i][j]);
			}
			else m[i][j] = std::max(m[i][j - 1], m[i][j]);
			auto it = std::lower_bound(t, t + N, std::make_tuple(i, j, 0, 0, 0));
			while (std::get<0>(*it) == i && std::get<1>(*it) == j && std::get<3>(*it) <= m[i][j])
			{
				m[i][std::get<2>(*it)] = std::max(m[i][std::get<2>(*it)], m[i][j] + std::get<4>(*it) - std::get<3>(*it));
				it++;
			}
		}

	printf("%lld\n", m[MAXT - 1][MAXT - 1]);
	    return 0;
}

Potete darmi un input che faccia sbagliare il mio programma oppure un suggerimento su cosa ho sbagliato?

Grazie mille,
Marco


#2

In realtà fallisce tutti i testcase dell’ultimo subtask :joy:

L’idea di fondo (ordinamento e programmazione dinamica) mi sembra corretta. La mia sensazione è che qualcosa non vada quando ci sono parecchi tournaments nello stesso giorno.

Allego un testcase generato appositamente per far sbagliare il tuo programma (non è piccolissimo ma non sono riuscito a fare di meglio e sospetto che il bug si presenti solo su istanze non troppo ridotte). Prova a vedere se su questo esempio riesci a capire cosa non va…

input.txt.zip (2,3 KB)


#3

Giusto, ho confuso testcase e subtask :joy:

Grazie per la rapida risposta! Ci ho studiato un po’, ma non riesco a trovare il problema con un input così grande… e non sapendo neanche quale sia l’output corretto.

Forse è meglio se mi dici direttamente cosa sbaglio a livello di algoritmo :sweat_smile:


#4

Se lo avessi individuato al volo, lo avrei già scritto: ci ho dato solo un’occhiata sommaria :joy:

L’output corretto per l’esempio di sopra è 29362074, se può aiutare.


#5

D’accordo, provero’ ancora, grazie :grin: