Ordine Online (ristorante) 9/100

Sto cercando di risolvere Ordine Online delle OII 2020. Sto avendo problemi nel capire da che “menù” incominciare. Dato che non mi è venuto nulla in mente, ho messo un while loop che crea tutte le combinazioni possibili tra i menù (ad esempio la prima combinazione sarà antipasti, pizze, dessert la seconda sarà antipasti, dessert, pizze e così via) con la funzione next_permutation . La funzione solve ha due cicli: uno sul vettore di vettori (vettore di menù) e l’altro su i prezzi dei piatti del menù stesso. Se un piatto dello stesso prezzo non è già stato scelto (cioè non è contenuto nel set) allora aggiungo il prezzo al set, altrimenti passa al menù dopo.
Non è sicuramente una soluzione “elegante” ma non capisco perché non dovrebbe funzionare.
Il correttore non mi dà nessun TLE ma solo WA. Il codice è il seguente:

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<int>> vs)
{
	set<int> s; // uso un set per capire se il piatto dal prezzo vs[i][j] sia già stato preso o meno
	
	for(int i = 0; i < (int)vs.size(); ++i)
	{
		for(int j = 0 ; j < (int)vs[0].size(); ++j)
		{
			if(s.find(vs[i][j]) == s.end()) s.insert(vs[i][j]); // se non è già stato preso allora aggiungi il vassoio al set
			else break; // altrimenti passa al prossimo vettore
		}
	}
	return s.size(); // il risultato è il numero totale di vassoi presi, cioè la lunghezza del set
}

int conta(int N, vector<int> &A, vector<int> &P, vector<int> &D)
{
	int res = 0;
	vector<vector<int>> vs = { A, P, D }; // ho messo i vecttori dati in un vettore per poter generare tutte le permutazioni
	sort(vs.begin(), vs.end()); // sort necessario per next_permutations()
	
	do {
		res = max(res, solve(vs)); // il risultato è il massimo tra il risultato precedente e il risultato calcolato con solve()
	}while(next_permutation(vs.begin(), vs.end())); // genera tutte le permutazioni del vettore di vettori
	
	
	return res;
 }

Ciao!
Non l’ho effettivamente testato ma credo che dovrebbe sbagliare questo esempio:

5
1 2 3 4 5
5 6 7 8 1
1 1 1 1 1

Ho capito qual è il problema ma non so proprio come risolverlo. Potresti perfavore darmi un indizio per aiutarmi? Ti ringrazio in anticipo

In realtà sei molto vicino alla soluzione, il problema della tua sol è che è “troppo greedy” ossia cerchi subito di aggiungere il massimo numero di elementi del primo vettore, invece dovresti provare tutte le possibili scelte per il primo e poi prendere il massimo per gli altri due.
Questo si può fare efficientemente riadattando la tecnica dei two pointers.
Ad ogni modo se vuoi una soluzione completa ti consiglio l’editorial di @Mr_Brionix (prima di guardarlo è meglio se ci provi da solo).

Aggiungo solo che sulla wiki c’è anche la soluzione ufficiale: https://wiki.olinfo.it/it/2020/nazionali/ristorante

1 Mi Piace

Grazie! Non conoscevo questa tecnica dei two pointers

1 Mi Piace

Grazie per il link!