Buongiorno, avrei bisogno di un aiuto per Episodio II: un lungo viaggio della gara di Biella dello scorso anno (esiste mica un editoriale con le soluzioni commentate?)
Sono riuscito a fare 49/100, ma ho degli degli output non corretti oltre ad altri che vanno fuori tempo massimo, quindi l’idea non è quella giusta.
Ho creato un grafo con nodi formati da coppie (fermata, linea) e costo degli archi 0 o 1 a seconda che sia possibile spostarsi da un nodo all’altro sullo stesso bus oppure no. Poi ho calcolato il costo minimo partendo dai nodi contenenti la fermata 0. Alla fine ho preso il minimo tra i costi di tutti i nodi che contengono la fermata finale.
C’è qualcuno che mi può accennare a quale potrebbe essere, invece, una strategia corretta per affrontare il problema?
Grazie!
Quello che dici sembra abbastanza sensato e vicino a una soluzione completa, però non è esattamente chiaro cosa stai facendo senza vedere il codice.
/Grazie per la risposta.
Ora carico il mio codice. Ho fatto alcune modifiche rispetto all’idea di ieri, arrivando sempre a 49/100 ma adesso ho molti meno errori (7) e nessun Timeout. C’è quindi ancora qualcosa che non considero.
L’idea:
Creo una lista con le fermate adiacenti ad ogni fermata, e nella lista metto anche la fermata precedente e la linea.
Faccio una visita del grafo formato dalle fermate, in ampiezza, a partire da 0.
Per ogni fermata adiacente a quella che sto considerando:
- se è su una linea diversa, o se è sulla stessa linea ma nell’ordine non corretto devo considerare che devo fare un cambio
- altrimenti non devo cambiare
A questo punto aggiorno il numero di cambi per arrivare alla fermata successiva e, nel caso abbia trovato un numero minore, reinserisco la fermata successiva tra quelle da analizzare, in ogni caso.
Ho cercato di commentare al meglio il codice (non sono molto esperto di C++)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
#include <string>
using namespace std;
int pianifica(int N, int L, vector<vector<int>> F){
vector <int> LL(N); //in questa lista memorizzo il numero di cambi minore per ogni fermata
vector <vector <vector <int > > > A; //lista delle fermate adiacenti
vector <int> V(N); //segno se la fermata è stata analizzata
queue <vector <int> > Q; //serve per fare il BFS sul grafo
//assegnamenti iniziali
for (int i=0;i<N;i++){
vector <vector <int> > temp;
A.push_back(temp);
LL[i] = INT_MAX;
V[i]=0;
}
//riempio la lista A ed anche LL
//per ogni fermata adiacente memorizzo anche quella precedente e la linea
for (int i=0; i<L; i++) {
bool zero= false;
int n = F[i].size();
for (int j=0;j<n;j++){
int prec = -1;
int succ = -1;
int linea = i;
if (j>0) prec = F[i][j-1];
if (j<n-1) succ = F[i][j+1];
A[F[i][j]].push_back({prec,succ,linea});
if (F[i][j]==0) {
zero = true;
}
if (succ!=-1 && zero) LL[succ] = 0;
}
}
Q.push({0,-1,-1});
LL[0]=0;
V[0] = 1;
while (Q.size()>0){
vector <int> q = Q.front();
Q.pop();
int fermata = q[0]; //la fermata che sto visitando
int provenienza = q[1]; //la fermata da cui provengo
int linea = q[2]; //la linea nella quale sono
//controllo tutte le fermate collegate a fermata
for (int i=0;i<A[fermata].size();i++){
int provenienza_vicino = A[fermata][i][0]; //la fermata precedente alla nuova nella linea
int fermata_vicino = A[fermata][i][1]; //la nuova fermata
int linea_vicino = A[fermata][i][2]; //la linea con cui arrivo alla nuova fermata
int f_v = fermata_vicino; //per semplificare la scritta
//controllo di non essere arrivato alla fine di una linea
if (f_v!=-1){
//Aggiorno il numero di cambi per arrivare a fermata_vicino
//caso particolare: vale solo per la partenza
if (provenienza==-1 && linea==-1) LL[f_v]=0;
/*
calcolo se ho bisogno di fare un cambio oppure no;
se trovo una situazione con meno cambi per f_v, aggiorno il valore di LL e
devo togliere f_v dalle fermate già analizzate (se lo è)
in modo da ricontrollare a cascata tutte le fermate a partire da essa
*/
else {
//se sono sulla stessa linea, controllo la sequenza delle fermate
if (linea==linea_vicino){
//se l'ordine è corretto non faccio cambi
if (provenienza_vicino==provenienza){
if (LL[f_v]>LL[fermata]){
V[f_v]=0;
LL[f_v]=LL[fermata];
}
}
else {
//faccio il cambio
if (LL[f_v]>LL[fermata]+1){
V[f_v]=0;
LL[f_v]=LL[fermata]+1;
}
}
}
else {
//su linee diverse devo fare un cambio per forza
if (LL[f_v]>LL[fermata]+1){
V[f_v]=0;
LL[f_v]=LL[fermata]+1;
}
}
}
//Decido se aggiungere la fermata_vicino a quelle ancora da analizzare
if (V[f_v]==0){
Q.push({f_v,fermata,linea_vicino});
V[f_v]=1;
}
}
}
}
if (LL[N-1]==INT_MAX) LL[N-1]=-1;
return LL[N-1];
}
Intanto non mi pare che il problema permettesse di prendere autobus in direzione opposta a quella data in input (anche perché renderebbe il problema abbastanza più facile).
Non mi addentro troppo nel resto della logica per ora perché mettere a posto questo dovrebbe semplificare un po’ la tua implementazione.
Poi hai dei seri problemi di implementazione che rendono la tua soluzione terribilmente lenta. In particolare, se vuoi salvare un numero fissato di elementi, un vector non è la struttura adatta per via dell’overhead gigantesco dovuto alle allocazioni sull’heap, ai resize… Due alternative pressoché equivalenti tra di loro sono std::array e std::tuple.
Grazie! Controllo tutto.
Prendendo spunto dal subtask4 che non viene pienamente superato ho provato questo input:
10 5
4 0 3 6 8
3 1 3 7
2 2 4
3 4 5 9
4 2 3 4 5
il tuo codice restituisce come numero minimo di cambi 1, mentre il risultato corretto è 2.
Controlla se questo esempio ti può essere d’aiuto a completare tutti i subtask.
Grazie! Non ero riuscito a trovare un caso adeguato!
Con i suggerimenti che mi avete dato sono arrivato a 70/100, ma rimangono ancora dei testcase che vanno oltri il tempo massimo …quindi credo di non avere preso la strada giusta.
Allego comunque il codice, ma vi chiedo se potete darmi un suggerimento per trovare quella che dovrebbe essere la strategia ottimale. Grazie
#include <queue>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <climits>
#include <string>
using namespace std;
//questo serve per creare una uonorderd map con una tupla come key
typedef tuple<int, int, int> MyTuple;
// define a hash function for this tuple
struct KeyHash : public std::unary_function<MyTuple, std::size_t> {
std::size_t operator()(const MyTuple& k) const {
// the magic operation below makes collisions less likely than just the standard XOR
std::size_t seed = std::hash<int>()(std::get<0>(k));
seed ^=(std::hash<char>()(std::get<2>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
return seed ^ (std::hash<char>()(std::get<1>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
};
// define the comparison operator for this tuple
struct KeyEqual : public std::binary_function<MyTuple, MyTuple, bool> {
bool operator()(const MyTuple& v0, const MyTuple& v1) const {
return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) &&
std::get<2>(v0) == std::get<2>(v1));
}
};
typedef unordered_map<MyTuple, int, KeyHash, KeyEqual> myMap;
int pianifica(int N, int L, vector<vector<int>> F){
myMap LL; //in questa lista memorizzo il numero di cambi minore per ogni tupla formata da (fermata, fermata precedente, linea)
unordered_map <int,vector <array<int,3> > > A; // fermate adiacenti
int V[N]; //segno se la fermata è stata analizzata
deque <array<int,3> > Q; //serve per fare il BFS sul grafo
int ris = INT_MAX;
//riempio la lista A
//per ogni fermata adiacente memorizzo anche quella precedente e la linea
for (int i=0; i<L; i++) {
bool zero= false;
int n = F[i].size();
for (int j=0;j<n;j++){
int fermata = F[i][j];
V[fermata]=0;
int prec = -1;
int succ = -1;
int linea = i;
if (j>0) prec = F[i][j-1];
if (j<n-1) succ = F[i][j+1];
A[F[i][j]].push_back({prec,succ,linea});
}
}
Q.push_back({0,-1,-1});
LL[make_tuple(0,-1,-1)]=1;
V[0] = 1;
while (Q.size()>0){
array <int,3> q = Q.front();
Q.pop_front();
int fermata = q[0]; //la fermata che sto visitando
int provenienza = q[1]; //la fermata da cui provengo
int linea = q[2]; //la linea nella quale sono
MyTuple f_t = make_tuple(fermata,provenienza,linea);
//controllo tutte le fermate collegate a fermata
for (int i=0;i<A[fermata].size();i++){
int provenienza_vicino = A[fermata][i][0]; //la fermata precedente alla nuova nella linea
int fermata_vicino = A[fermata][i][1]; //la nuova fermata
int linea_vicino = A[fermata][i][2]; //la linea con cui arrivo alla nuova fermata
int f_v = fermata_vicino; //per semplificare la scritta
//controllo di non essere arrivato alla fine di una linea
if (f_v!=-1){
bool cambio =false;
MyTuple f_v_t = make_tuple(f_v,fermata,linea_vicino);
//Aggiorno il numero di cambi per arrivare a fermata_vicino
//caso particolare: vale solo per la partenza
if (provenienza==-1 && linea==-1) LL[f_v_t]=1;
/*
calcolo se ho bisogno di fare un cambio oppure no;
se trovo una situazione con meno cambi per f_v, aggiorno il valore di LL e
devo togliere f_v dalle fermate giàanalizzate (se lo è)
in modo da ricontrollare a cascata tutte le fermate a partire da essa
*/
else {
if (LL[f_v_t]==0) LL[f_v_t] = INT_MAX;
//se sono sulla stessa linea, controllo la sequenza delle fermate
if (linea==linea_vicino){
//se l'ordine è corretto non faccio cambi
if (provenienza_vicino==provenienza){
if (LL[f_v_t]>LL[f_t]){
V[f_v]=0;
LL[f_v_t]=LL[f_t];
}
}
else {
//faccio il cambio
cambio = true;
if (LL[f_v_t]>LL[f_t]+1){
V[f_v]=0;
LL[f_v_t]=LL[f_t]+1;
}
}
}
else {
//su linee diverse devo fare un cambio per forza
cambio = true;
if (LL[f_v_t]>LL[f_t]+1){
V[f_v]=0;
LL[f_v_t]=LL[f_t]+1;
}
}
}
if (f_v == N-1) ris = min(ris,LL[f_v_t]);
//Decido se aggiungere la fermata_vicino a quelle ancora da analizzare
if (V[f_v]==0){
if (cambio) Q.push_back({f_v,fermata,linea_vicino});
else Q.push_front({f_v,fermata,linea_vicino});
V[f_v]=1;
}
}
}
}
if (ris==INT_MAX) return -1;
return ris -1;
}
è possibile che il problema sia solo il fattore costante. Perché usi un’unordered map quando un vector di vector è più che sufficiente?
in effetti modificando la variabile A in un vector di vector arrivo a 82/100!
Buonasera, sto provando anche io a risolvere il problema bus, sono arrivato a fare 70/100 con il codice allegato. La mia strategia è quella di eseguire una sorta di BFS partendo dalla fermata 0. Esploro tutte le linee che passano per la fermata, cominciando dal capolinea e rimuovendo le fermate ad una ad una (per evitare, se dovesse essere ripercorsa la linea, di ripassare da fermate già esplorate). Queste, nel caso non fossero state esplorate, vengono aggiornate come già viste, si modifica il numero minimo di scambi per raggiungerle nel vettore visited e si inseriscono nel queue del BFS. I test case che hanno output errato sono: 21, 23, 24, 26, 41, 42. Qualche suggerimento? Grazie!
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
int pianifica(int N, int L, vector<vector<int>> f)
{
//Converti F in double ended queue (basterebbe queue)
vector<deque<int>> F(L);
//Salva le linee che passano da (i) e rimuovi
//quelle già esplorate
vector<unordered_multiset<int>> el(N);
//Queue per eseguire la bfs
queue<int> bfs;
//Vettore per salvare la distanza minima
vector<int> visited(N, -1);
for(int i = 0; i < L; i++)
{
F[i].push_back(f[i][0]);
for(int k = 1; k < f[i].size(); k++)
{
el[f[i][k-1]].insert(i);
F[i].push_back(f[i][k]);
}
}
//0 non richiede neanche di salire sul bus, indicato con -1
//visited[0] = -1;
//inserisci 0 nella bfs per iniziare l'esplorazione
bfs.push(0);
//Continua fino a fine bfs o quando il risultato è stato trovato
while(!bfs.empty() && visited[N-1] == -1)
{
int fermata = bfs.front();
int cambi = visited[fermata]; //Garantito che sia già visitata(tranne 0 = -1)
bfs.pop();
//esplora tutte le linee inesplorate che passano dalla fermata
while(el[fermata].size() > 0)
{
//per ogni linea, percorrila al contrario rimuovendo dalla coda
//le fermate esplorate
auto linea = el[fermata].begin();
while(F[*linea].back() != fermata)
{
//ultima fermata della linea
int t = F[*linea].back();
F[*linea].pop_back();
//Elimina questa linea dalle linee che passano per t
auto it = el[t].find(*linea);
if(it != el[t].end())
el[t].erase(it);
//NOTA: Se è già stata visitata visited[t] <= cambi+1 (BFS)
if(visited[t] != -1) continue;
//Se è una nuova fermata, inseriscila nella bfs e imposta gli scambi
visited[t] = cambi+1;
bfs.push(t);
}
}
}
return visited[N-1];
}
Credo che il problema sia che uno stesso bus può passare più volte dalla stessa fermata. Eliminando dal fondo e fermandoti all’ultima occorrenza della fermata ignori eventuali occorrenze precedenti che sarebbero più vantaggiose
Sono riuscito a sistemare il codice, fixando l’errore 2 prende 88/100, fixando anche l’errore 1 prende 100/100. Il problema era che quando una linea terminava con la fermata del BFS, il ciclo che esplorava le linee veniva interrotto precocemente, generando soluzioni subottimali. Grazie per l’aiuto!
Codice:
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
int pianifica(int N, int L, vector<vector<int>> f)
{
//Converti F in double ended queue
vector<deque<int>> F(L);
//Salva le linee che passano da (i) e rimuovi
//quelle già esplorate
vector<unordered_multiset<int>> el(N);
//Queue per eseguire la bfs
queue<int> bfs;
//Vettore per salvare la distanza minima
vector<int> visited(N, -1);
for(int i = 0; i < L; i++)
{
F[i].push_back(f[i][0]);
for(int k = 0; k < f[i].size(); k++)
{
//Errore 1: Aggiungere questa linea a tutte le fermate tranne l'ultima,
//quando invece andava inclusa.
el[f[i][k]].insert(i);
F[i].push_back(f[i][k]);
}
}
//0 non richiede neanche di salire sul bus, indicato con -1
//visited[0] = -1;
//inserisci 0 nella bfs per iniziare l'esplorazione
bfs.push(0);
//Continua fino a fine bfs o quando il risultato è stato trovato
while(!bfs.empty() && visited[N-1] == -1)
{
int fermata = bfs.front();
int cambi = visited[fermata]; //Garantito che sia già visitata(tranne 0 = -1)
bfs.pop();
//esplora tutte le linee inesplorate che passano dalla fermata
while(el[fermata].size() > 0)
{
//per ogni linea, percorrila al contrario rimuovendo dalla coda
//le fermate esplorate
auto linea = el[fermata].begin();
//Errore 2: Se il bus fosse passato due volte sulla stessa linea,
//questo ciclo si sarebbe interrotto prima del previsto
while(el[fermata].count(*linea) > 0)
{
//ultima fermata della linea
int t = F[*linea].back();
F[*linea].pop_back();
//Elimina questa linea dalle linee che passano per t
auto it = el[t].find(*linea);
if(it != el[t].end())
el[t].erase(it);
//NOTA: Se è già stata visitata visited[t] <= cambi+1 (BFS)
if(visited[t] != -1) continue;
//Se è una nuova fermata, inseriscila nella bfs e imposta gli scambi
visited[t] = cambi+1;
bfs.push(t);
}
linea++;
}
}
return visited[N-1];
}
Per completare il task senza TLE dovresti cercare il numero minimo di cambi senza ricorrere alla struttura unordered_map.
Il dato di cui puoi fare a meno è la fermata di provenienza e pertanto risolvere il task solo con linea e fermata.
In questo modo invece di un unordered_map puoi tranquillamente utilizzare una matrice LxF.
L’unica accortezza è di non utilizare una matrice NxN ma una a lunghezza variabile delle righe = Ki.