Solução escrita por Márcio Vitor
Conhecimentos prévios:
- Introdução a grafos
- Dijkstra
- Dijkstra com vértices auxiliares (para algumas subtarefas).
Subtarefa 2 ($X=2 \cdot 10^9$ e $Y=2 \cdot 10^9$) (8 pontos):
Como temos basicamente energia infinita (nossa energia é suficiente para usar todas as arestas do grafo mesmo no pior caso), basta verificar se é possível ir do $1$ ao $N$, uma forma de fazer isso é usando um $\texttt{dfs}$ marcando as posições alcançáveis e depois vendo se $N$ está marcado.
Complexidade: $\mathcal{O}(N+M)$
Subtarefa 3 ($Y = 0$) (9 pontos):
Como só podemos subir ou permanecer na mesma altura, seja $d = H[N]-H[1]$, se $d \lt 0$ ou $d \gt X$ não é possível.
Caso contrário, crie apenas as arestas que ligam um vértice de altura menor à algum de altura maior ou igual, e verifique se é possível chegar à $N$ assim como na subtarefa 2.
A complexidade fica: $\mathcal{O}(N+M)$
Subtarefa 4 ($N, X, Y \le 100$ e $M \le 200$) (15 pontos):
Para resolver essa subtarefa vamos criar vértices adicionais!
Vamos definir os vértices $(U, x, y)$, representando (vértice atual, energia de subir usada, energia de descer usada). Para cada um desses estados e para todo vizinho $V$ de $U$ ligue $(V,x+H[V]-H[U],y)$ a $(U,x,y)$ se $H[V] \ge H[u]$ caso contrário ligue $(V,x,y+H[U]-H[V])$ a $(U,x,y)$.
se um vértice $(U,x,y)$ é alcançável a partir de $(1,0,0)$ quer dizer que é possível chegar em $U$ com $X \ge x$ e $Y \ge y$, ou seja basta fazer um $dfs$ assim como na subtarefa 2, e então verificar se $(N,x,y)$ é alcançável para algum $x \le X$ e $y \le Y$.
Complexidade: $\mathcal{O}((N + M) \cdot X \cdot Y)$
Subtarefa 5 ($N, X \le 1000$ e $M \le 2000$) (24 pontos):
Vamos usar uma ideia similar a subtarefa 4, porém vamos tirar o $y$ do estado já que nessa subtarefa ele pode ser bem grande.
Defina o vértice apenas como: $(U,x)$, e seja $dist[U][x]$ = o mínimo de energia de descida para chegar à u gastando $x$ de energia de subir.
Para cada vértice $(U,x)$ e para cada vizinho $V$ de $U$ crie uma aresta com peso $0$ de $(U,x)$ à $(V,x+H[v]-H[u])$ se $H[V] \ge H[U]$ e $x+H[V]-H[U] \le X$ caso $H[V] \lt H[U]$ ligue uma aresta de $(U,x)$ à $(V,x)$ com peso $H[U]-H[V]$.
Depois para todo $(N,x)$ tal que $x \le X$ se algum $dp[N][x] \le Y$ a resposta é “S” caso contrário “N”.
Subtarefa 6 ($H_1=H_N$ e $X=Y$) (26 pontos):
A principal ideia dessa subtarefa é que como as alturas do inicio e do fim são iguais ambas energias terão mesmo gasto pois para toda vez que subimos temos que descer eventualmente.
Portanto podemos assumir que as arestas descendo não gastam energia (definindo estas com peso 0) as subindo terão o peso igual a diferença entre as alturas, assim basta achar a menor distância entre $1$ e $N$ seja ela $W$.
A resposta será “S” se $W \le X$ caso contrário será “N”.
Complexidade: $\mathcal{O}((N + M) \cdot log_2(N))$
Subtarefa 7:
Lema: Para qualquer caminho de 1 até N, se x é o total subido e y o total descido, então $x − y = H[N] − H[1]$.
Prova
Defina a variação de altura na $i$-ésima trilha como $\Delta_i = H[v_i] – H[v_{i-1}]$, para $1 \le i \le k$. Então \[ x = \sum_{i=1}^{k} \max(\Delta_i, 0), \qquad y = \sum_{i=1}^{k} \max(-\Delta_i, 0). \] Para qualquer inteiro $\Delta$ vale $\Delta = \max(\Delta,0) – \max(-\Delta,0)$ (se $\Delta \ge 0$ o segundo termo é $0$; se $\Delta < 0$ o primeiro é $0$). Logo \[ x – y = \sum_{i=1}^{k} \Delta_i = \sum_{i=1}^{k} \bigl( H[v_i] – H[v_{i-1}] \bigr). \] Escrevendo a soma por extenso, os termos intermediários se cancelam em pares: \[ \bigl(\cancel{H[v_1]} – H[v_0]\bigr) + \bigl(\cancel{H[v_2]} – \cancel{H[v_1]}\bigr) + \bigl(\cancel{H[v_3]} – \cancel{H[v_2]}\bigr) + \cdots + \bigl(H[v_k] – \cancel{H[v_{k-1}]}\bigr) \] onde cada $+H[v_j]$ do termo $j$ é cancelado pelo $-H[v_j]$ do termo $j+1$. Sobram apenas o primeiro $-H[v_0]$ e o último $+H[v_k]$: \[ x – y = H[v_k] – H[v_0] = H[N] – H[1]. \]
Ou seja $y = x – H[N] + H[1]$, e portanto basta fazer um $\texttt{Dijkstra}$ assim como na subtarefa 6, a resposta será “S” se $W \le X$ e $W – H[N] + H[1] \le Y$ caso contrário será “N”.
Complexidade: $\mathcal{O}((N + M) \cdot log_2(N))$