salve a tutti, per risolvere waterslide in gara ho usato una bfs ma andava fuori tempo in un caso dell’ultimo testcase e ho ottenuto 45/100 dovuto anche ad un caso errato nel penultimo testcase. Quando hanno spiegato la soluzione ufficiale parlavano di una Topological-sort, mi sono informato su cosa fosse ma non ho capito come crearla in O(N) e come utilizzarla per risolvere questo problema.
grazie in anticipo.
Ciao, utilizzando una dfs non fai altro che provare tutti i possibili percorsi che credo abbia complessità \mathcal O (|V|\cdot |E|^2).
Possiamo migliorare tale complessità utilizzando la programmazione dinamica.
Il grafo in questione è un DAG, quindi possiamo “ordinare” i nodi in modo che prendendo due indici i e j se esiste un percorso da G_i a G_j allora j deve venire dopo di i.
In questo modo evito di ripassare su un qualsiasi nodo di cui ho già calcolato la probabilità, quindi invece di eseguire una dfs, mi limito a calcolare la probabilità dei figli, portando la complessità a \mathcal O (|V|+|E|).
Per poter poter eseguire l’ordinamento topologico in tempo lineare si usa uno stack, qui è spiegato bene, comunque se a qualcuno dovesse servire lascio il mio codice:
vector<int> stk;
bool vis[MAXN];
vector<int> grafo[MAXN];
double prob[MAXN];
void dfs(int p)
{
vis[p]=true;
for(int& i : grafo[p])
if(!vis[i])
dfs(i);
stk.push_back(p);
}
int main()
{
int N, M, P;
cin>>N>>M>>P;
for(int k=0,i,j; k!=M; k++)
{
cin>>i>>j;
grafo[i].push_back(j);
}
dfs(0);
reverse(stk.begin(),stk.end());
prob[0]=1.0;
for(int& i : stk)
for(int& j : grafo[i])
prob[j]+=prob[i]/grafo[i].size();
cout<<distance(prob,max_element(prob+N-P,prob+N))<<endl;
return 0;
}
2 Mi Piace
Nonostante i testcase usati in gara fossero clementi, è possibile generare testcase per fare sbagliare anche quella soluzione. Esiste una soluzione sempre corretta?
scusate ma non capisco proprio perchè ottengo 0/100 con solo i casi esempio corretti
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int n, m, p, a, b;
vector<int> g[1000001], topo;
int visited[1000001];
double scivolo[1000001];
void topo_sort(int h){
visited[h]=1;
for(int x=0; x<g[h].size(); x++){
if(visited[g[h][x]]==0){
topo_sort(g[h][x]);
}
}
topo.push_back(h);
}
int main(){
fin >> n >> m >> p;
for(int x=0; x<m; x++){
fin >> a >> b;
g[a].push_back(b);
}
topo_sort(0);
reverse(topo.begin(), topo.end());
scivolo[0]=1.0;
for(int x=0; x<n; x++){
for(int y=0; y<g[topo[x]].size(); y++){
scivolo[g[topo[x]][y]]+=scivolo[x]/g[x].size();
}
}
double M=0;
int pos=0;
for(int x=n-p; x<n; x++){
if(scivolo[x]>M){
M=scivolo[x];
pos=x;
}
}
fout << pos;
}
Dovrebbe essere:
scivolo[g[topo[x]][y]]+=scivolo[topo[x]]/g[topo[x]].size()
Comunque il C++11 introduce i range-based loop, quindi in questi casi è conveniente usarli.
Io credevo che questa soluzione fosse sempre corretta, c’è un caso particolare che non considero?
2 Mi Piace
che sbadato che sono, grazie ancora @bortoz, per quanto riguarda i range-based loop sono abituato ad usarli con i set e i map ma forse è meglio che comincio ad utilizzarli più spesso.
Il programma che segue genera input per fare sbagliare il tuo programma
#include <bits/stdc++.h>
int main(int argc,char *argv[])
{
int N=atoi(argv[1]);
fprintf(stderr,"answer should be %d\n",2*N+2);
printf("%d %d 3\n",2*N+4,N-1+N+4);
for(int i=0;i<N;i++)
{
printf("%d %d\n",i*2,i*2+1);
if(i<N-1)printf("%d %d\n",i*2,i*2+2);
}
printf("%d %d\n",2*N-2,2*N);
printf("%d %d\n",2*N-2,2*N+2);
printf("%d %d\n",2*N,2*N+1);
printf("%d %d\n",2*N,2*N+3);
}
anche solo invocando ./generatore 5000 dovrebbe produrre un input dove il tuo programma sbaglierà.
1 Mi Piace
Utilizzando i long double stampa la risposta corretta 
2 Mi Piace
Qual’è il massimo x per il quale il tuo programma azzecca ./generatore x ?
Risulta veloce una semplice scansione del grafo a partire dal “launch pad” fino ad arrivare a tutte le piscine a patto di uscire da uno svincolo solo dopo che si è arrivati lì da tutti i suoi ingressi e avendo nel frattempo accumulato …
1 Mi Piace
Precisamente 16445, comunque un’opzione sarebba stata quella di usare le frazione ma dato che nel tuo generatore la probabilità arriva a 2^{-\frac{M}{2}}, va “un pochettino” in overflow.
struct fraction
{
__int128 num, den;
fraction() : num(0), den(1) {}
fraction(const fraction& x) : num(x.num), den(x.den) {}
void reduce() { int x=__gcd(num,den); num/=x; den/=x; }
fraction& operator=(const pair<int,int>& x) { num=x.first; den=x.second; return *this; }
fraction& operator+=(const fraction& x) { num=num*x.den+den*x.num; den*=x.den; reduce(); return *this; }
fraction operator/(const int x) { fraction n(*this); n.den*=x; n.reduce(); return n; }
bool operator<(const fraction& x) { return num*x.den<den*x.num; }
};
2 Mi Piace
I testcase evitano volutamente situazioni dove lo scarto tra due piscine è minore di 10^{-4} per ovviare ai problemi con floating point. Non volevamo che soluzioni diverse da quella della giuria fossero penalizzate per semplici questioni di arrotondamento che esulavano dal core del probema.
Come hai già dimostrato, la probabilità può decrescere esponenzialmente a ogni diramazione e quindi ogni speranza di memorizzare numeri così grandi è praticamente vana.
Esiste invece una soluzione che non soffre di questo problema?
La domanda si riduce al capire se possiamo distinguere tra due piscine con scarto arbitrariamente piccolo.
Direi che servirebbe una cosa di questo tipo per i numeri reali: https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic, che ovviamente esula del tutto dalla programmazione competitiva.