# Water park (waterslide)

**URL:** <https://forum.olinfo.it/t/water-park-waterslide/5024>\
**Category:** Aiuto\
**Created:** [23 Febbraio 2018, 4:49pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024 "2018-02-23T16:49:03Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [23 Febbraio 2018, 4:49pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/1 "2018-02-23T16:49:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [23 Febbraio 2018, 6:08pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/2 "2018-02-23T18:08:29Z")

</div>

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](https://en.wikipedia.org/wiki/Directed_acyclic_graph), 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](https://www.youtube.com/watch?v=ddTC4Zovtbc) è spiegato bene, comunque se a qualcuno dovesse servire lascio il mio codice:

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [23 Febbraio 2018, 6:16pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/4 "2018-02-23T18:16:27Z")

</div>

grazie mille @bortoz per l’aiuto

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [24 Febbraio 2018, 6:50am UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/5 "2018-02-24T06:50:38Z")

</div>

Nonostante i testcase usati in gara fossero clementi, è possibile generare testcase per fare sbagliare anche quella soluzione. Esiste una soluzione sempre corretta?

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [24 Febbraio 2018, 1:36pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/6 "2018-02-24T13:36:53Z")

</div>

scusate ma non capisco proprio perchè ottengo 0/100 con solo i casi esempio corretti

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [24 Febbraio 2018, 5:55pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/7 "2018-02-24T17:55:38Z")

</div>

> [@Luca25](#):
>
> scivolo[g[topo][y]]+=scivolo/g.size();

Dovrebbe essere:

`scivolo[g[topo[x]][y]]+=scivolo[topo[x]]/g[topo[x]].size()`

Comunque il C++11 introduce i [range-based loop](http://en.cppreference.com/w/cpp/language/range-for), quindi in questi casi è conveniente usarli.

> [@lukecavabarrett](#):
>
> Nonostante i testcase usati in gara fossero clementi, è possibile generare testcase per fare sbagliare anche quella soluzione.

Io credevo che questa soluzione fosse sempre corretta, c’è un caso particolare che non considero?

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [24 Febbraio 2018, 7:19pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/8 "2018-02-24T19:19:33Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [24 Febbraio 2018, 7:20pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/9 "2018-02-24T19:20:53Z")

</div>

Il programma che segue genera input per fare sbagliare il tuo programma

```auto
#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à.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [24 Febbraio 2018, 8:03pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/10 "2018-02-24T20:03:44Z")

</div>

Utilizzando i `long double` stampa la risposta corretta 😉

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [24 Febbraio 2018, 9:50pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/11 "2018-02-24T21:50:16Z")

</div>

Qual’è il massimo x per il quale il tuo programma azzecca `./generatore x` ?

---

<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:** [24 Febbraio 2018, 11:16pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/12 "2018-02-24T23:16:18Z")

</div>

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 …

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [25 Febbraio 2018, 10:11am UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/13 "2018-02-25T10:11:05Z")

</div>

> [@lukecavabarrett](#):
>
> Qual’è il massimo x per il quale il tuo programma azzecca ./generatore x ?

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.

```auto
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; }
};

```

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [25 Febbraio 2018, 3:52pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/14 "2018-02-25T15:52:55Z")

</div>

> [@lukecavabarrett](#):
>
> Nonostante i testcase usati in gara fossero clementi

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.

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [25 Febbraio 2018, 5:00pm UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/15 "2018-02-25T17:00:06Z")

</div>

Esiste invece una soluzione che non soffre di questo problema?

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [26 Febbraio 2018, 9:38am UTC](https://forum.olinfo.it/t/water-park-waterslide/5024/16 "2018-02-26T09:38:11Z")

</div>

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](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic), che ovviamente esula del tutto dalla programmazione competitiva.